ForHosting KIT · 数学

Cipolla法の法平方根

Cipolla法は、平方剰余かどうかの判定だけでなく、奇素数を法とする平方根そのものを求めます。7を法とする2の平方根は3と4で、3の2乗の9を7で割ると余りは2です。ブラウザで無料で使えます。

無料
ブラウザで動作
登録不要
データは端末の外に出ません

無料で実行 API仕様を見る

ご利用方法ウェブAPIメールTelegramアプリ近日

計算例

入力した場合

A: 2
電力（W）: 7

結果

A の法: 2
根: 3, 4
根: 3
オメガ: 0

Cipolla のアルゴリズムは、奇素数を法とする平方根を求める古典的な数論の手法です。整数 a と奇素数 p を与えると、a が二次剰余であるときに x の二乗が a と p を法として合同となる整数 x を返します。暗号の宿題、競技プログラミング、合同算術の教材では、ルジャンドル記号による可否判定だけでなく、明示的な根がしばしば必要になります。

法平方根とは何か、Cipolla が適用されるとき

合同算術において、x の二乗が a と p を法として合同であるという合同式は、二乗が a と同じ剰余類に落ちる整数 x を求めます。p が奇素数のとき、理論的な答えは明快です。a が p で割り切れるなら唯一の根は零であり、そうでなければ零でない類のちょうど半分が二次剰余で、各剰余にはちょうど二つの根 r と p マイナス r があります。

ルジャンドル記号はどの場合かを示しますが r を構成しません。Cipolla のアルゴリズムは、p 個の元を持つ体の適切に選んだ二次拡大で働くことでその空白を埋めます。

omega の二乗から a を引いたものが p を法とする二次非剰余になるような補助整数 omega を選び、その非剰余の形式的な平方根を付けた omega を (p プラス 1) を 2 で割った指数までべき乗すると、基底体に戻り a の平方根になります。

古典的アルゴリズムとオイラーの判定基準が奇素数の法を前提とするため、p が合成数や偶数のときも失敗します。Tonelli–Shanks と比べ、Cipolla は教材デモや中程度の素数向けに実装が短く、p マイナス 1 の素因数分解を必要としません。

本機能は、安定して順序付けられた根と文書化されたエラー契約を備えた透明な Cipolla 経路を求める学生・教育者・スクリプトを対象とします。

Cipolla の法平方根が役立つ場面

競技プラットフォームや LMS 採点器には、空配列を成功と誤認しうるクライアント向けではなく、非剰余と合成法を拒否する決定的オラクルが必要です。Rabin 暗号や素数体上の点復元を導入する暗号ノートは、Tonelli–Shanks の隣に Cipolla の解説を欲しがることが多く、共有の純モジュールがブラウザデモとサーバ検査を同一に保ちます。

p を公開された素数上限内に保ち、順序付き roots 配列をテストで固定すれば、コンピュータ代数の全体スタックを埋め込まずに教育・自動化・エッジワーカー向けの再現可能な法平方根が得られます。

活用例

数論の授業と宿題

学生は a と奇素数 p を送り、返された順序付き根を手計算の Cipolla 手順や教科書の表と照合します。

暗号の教材デモとノート

重い代数ライブラリを取り込まず、Rabin 風や楕円曲線のノートでルジャンドル検査の隣に Cipolla を示せます。

よくある質問

なぜ p は奇素数でなければならないのですか？

Cipolla のアルゴリズムとオイラーの判定基準は奇素数に対して定義されます。偶数や合成の法は拒否され、非素数体が F_p のように振る舞うふりはしません。

ルジャンドル記号計算機とどう違いますか？

ルジャンドルは剰余性（−1、0、1）だけを報告します。本機能は存在するとき明示的な平方根を、Cipolla の拡大体べき乗で構成します。

7を法とする2の平方根はどう求めますか？

数に2、素数に7を入力すると、3と4の2つの根が返ります。3の2乗は9で、7で割ると余りが2になり、4は7から3を引いた値です。

aが平方剰余でない場合はどうなりますか？

根は返さず、その素数を法とする平方根が存在しないことを知らせます。奇素数を法とすると、0以外の剰余類のちょうど半分だけが平方剰余です。

Cipolla法とTonelli–Shanks法の違いは何ですか？

どちらも同じ根を求めます。Cipolla法は授業で追いやすく、pから1を引いた数を素因数分解する必要がありません。p個の元を持つ体を拡大した中で計算します。

開発者向け — APIアクセス

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

エンドポイント

POSThttps://api.kit.forhosting.com/numth/cipolla-algorithm

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/numth/cipolla-algorithm \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"a":2,"p":7}'

const res = await fetch("https://api.kit.forhosting.com/numth/cipolla-algorithm", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "a": 2,
    "p": 7
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/cipolla-algorithm",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "a": 2,
    "p": 7
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/cipolla-algorithm", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"a":2,"p":7}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"a":2,"p":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/cipolla-algorithm", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "a": 2,
  "p": 7
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.cipolla_algorithm",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

料金

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

エラー

HTTP	コード	意味
`401`	`unauthorized`	APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
`402`	`insufficient_balance`	残高が不足しています。チャージ後に再度お試しください。
`404`	`unknown_type`	指定されたタスクタイプは存在しません。タイプ名を確認してください。
`429`	`rate_limited`	リクエストが多すぎます。しばらく待ってから再度お試しください。

技術的な注記

本機能は p が奇素数であることを検証し、非剰余を invalid_input で明確に拒否し、乱数による omega の抽選を使わない完全に決定的な Cipolla 構成を実行し、根が存在するときは両方の根を返します。

法平方根とは何か、Cipolla が適用されるとき

構成が失敗するのはちょうど a が非剰余のときであり、本エンドポイントは偽の根を捏造せず invalid_input と報告します。

入力契約、アルゴリズム手順、応答の形

a は p を法とする平方根を求めたい数、p は 3 以上 1 兆以下の奇素数です。a の絶対値は 1 兆を超えてはなりません。続いて x プラス y 倍の w の平方根という環で乗算し、omega プラス w の平方根を (p プラス 1) を 2 で割った指数まで正確な BigInt 合同乗算でべき乗します。例：a が 2、p が 7 なら根は 3 と 4 です。3 の二乗は 9 で 7 を法として 2 だからです。必須の整数フィールド二つを含む JSON 本体を POST してください。各フィールドは JSON 数値でも、符号付きの数字列でも構いません。欠落、非整数、範囲外、偶数の p、合成数の p はすべて invalid_input で失敗し課金されません。p が受理されると、ハンドラは a を 0 から p マイナス 1 の a_mod に還元します。a_mod が 0 なら応答は method が trivial_zero、omega が null の自明な根 0 です。そうでなければ a_mod のルジャンドル記号をオイラーの判定基準で計算し、マイナス 1 なら a は二次非剰余であり剰余類を名指すメッセージでタスクが失敗します。記号がプラス 1 のとき、アルゴリズムは omega の二乗から a_mod を引いたもののルジャンドルがマイナス 1 となる最小の非負 omega を走査します。この走査は決定的なので、同じ組は常に同じ証人を使います。体成分が平方根であり、API は順序付きの両根、より小さい優先の主根、証人 omega、method を cipolla、内部の二乗検査後に verified を true として返します。

Cipolla の法平方根が役立つ場面

二次剰余を扱う教室では、剰余性だけでは不十分であることを示し、拡大体のべきを手計算せず多数の剰余について実根を示すために本エンドポイントを呼べます。すでにルジャンドルやヤコビ記号を計算している研究ノートは、記号が 1 のときだけ根を要求でき、成功アイテムごとに $0.002 を払い検証失敗では課金されません。

連携の活用例

競技プログラミングと LMS 自動採点

採点器は法平方根の答えを検証し、非剰余と合成法を invalid_input で拒否し、実行間で omega を決定的に保ちます。

技術的な質問

Cipolla のアルゴリズムで法平方根を求めるには？

整数 a と奇素数 p を送ってください。成功時 API は r² ≡ a (mod p) を満たす根 r と p−r（a≡0 mod p のときは 0）と、拡大体で使った決定的 omega 証人を返します。

a が p を法とする二次剰余でない場合は？

タスクは invalid_input で失敗し、a が二次非剰余である旨のメッセージを返します。根は捏造されず、呼び出しは課金されません。

Cipolla 法平方根ツールの料金は？

ブラウザ版は無料です。API は成功した呼び出しごとに前払い KIT 残高から $0.002 を使い、無効入力は課金されません。

KITの完全なドキュメントを見る →

Cipolla法の法平方根

無料で実行

計算例

法平方根とは何か、Cipolla が適用されるとき

Cipolla の法平方根が役立つ場面

活用例

数論の授業と宿題

暗号の教材デモとノート

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

お使いのスタックから呼び出す

リクエスト例

レスポンス例

料金

エラー

技術的な注記

法平方根とは何か、Cipolla が適用されるとき

入力契約、アルゴリズム手順、応答の形

Cipolla の法平方根が役立つ場面

連携の活用例

競技プログラミングと LMS 自動採点

技術的な質問

ありがとう