指定した底によるソロベイ・シュトラッセン素数判定
13を底2で調べると、2つの剰余がどちらも12になるため、13は底2に対する確率的素数と判定されます。一致しなければ合成数であることが証明されます。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- N
- 13
- 1つ目のテキスト
- 2
- Gcd
- 1
- ヤコビ記号
- -1
- オイラー剰余
- 12
- 期待される剰余
- 12
ソロベイ・シュトラッセン素数判定は、指定した1つの底に対して奇数が素数らしく振る舞うかを調べます。底のヤコビ記号を候補数を法として計算し、その底を候補数から1を引いた値の半分だけべき乗して、両者を候補数を法として比較します。結果は合成数であることを確定する証人、またはその底に関して確率的素数であるという判定です。入力を10進文字列として扱うため、大きな整数も浮動小数点の丸めを受けず正確に保持されます。
比較が示す内容
奇素数 n と、n で割り切れない任意の底 a について、オイラーの規準は、a の (n - 1) / 2 乗が法 n で a のルジャンドル記号と合同になることを示します。ヤコビ記号はこの記号計算を奇数の合成数候補へ拡張するため、n の素因数分解を知らなくても効率よく計算できます。
ソロベイ・シュトラッセン法では、モジュラーべき乗と剰余として表したヤコビ記号を比較します。1 は 1 のまま、-1 は n - 1 として扱います。不一致なら、n が合成数であることが数学的に証明されます。
一致が示す内容はそれより弱く、選択した底で検査を通過したことだけです。最初の比較を通過した合成数でも、別の有効な底では不合格になる場合があります。応答には両方の剰余、ヤコビ値、最大公約数が含まれるため、説明のない真偽値ではなく、判定根拠を直接確認できます。
入力の選択と検証
n と a は符号なし10進文字列で指定してください。候補 n は3以上の奇数でなければなりません。偶数または3未満の値は、この検査の対象外なので入力エラーになります。
底は 1 < a < n を満たす必要があります。互いに素かどうかを事前に確認する必要はありません。この機能が gcd(a, n) を計算し、自明でない共通因数があれば直ちに合成数と判定します。
計算量に明確な上限を設けるため、各入力は10進で1,000桁までです。曖昧な解釈を防ぐため、符号、空白、小数点、指数表記、先頭のゼロは受け付けません。底を手動で選ぶ場合は、証拠を強めるため複数の異なる底を使用してください。
この機能は底を無作為に選びません。そのため実行結果は常に再現可能であり、どの証人を検査したかを監査記録や学習例に正確に残せます。
活用例
教科書の証人を確認
問題文に示された候補数と底をそのまま使い、ソロベイ・シュトラッセン法の演習を再現できます。
擬素数の挙動を調査
合成数候補がある底では合格し、別の底では不合格になる様子を、すべての中間値とともに比較できます。
再現可能な事前検査を構築
追加の底やより強い素数判定手順を適用する前に、単一の底による決定的な結果を記録できます。
よくある質問
合格すれば n が素数だと証明できますか?
いいえ。 指定した底に関して n が確率的素数であることだけを示し、別の底で合成数と証明される場合があります。
n が3以上の奇数でなければならないのはなぜですか?
ここで使用するヤコビ記号の比較は3以上の奇数候補を対象としています。
a と n に共通因数がある場合はどうなりますか?
返される gcd が共通因数を示し、ヤコビ比較を合格とはせず n を合成数に分類します。
底は無作為に選ばれますか?
いいえ。 お客様が底を指定するため、計算は決定的で再現可能です。
ソロベイ・シュトラッセン判定で扱える数の大きさはどれくらいですか?
それぞれの数は最大1,000桁の10進数まで入力できます。入力したとおりに丸めずに正確に扱うため、非常に大きな候補数でも小さな数と同じ厳密な比較が行われます。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/numth/solovay-strassen-test \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":"561","a":"2"}'const res = await fetch("https://api.kit.forhosting.com/numth/solovay-strassen-test", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": "561",
"a": "2"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/solovay-strassen-test",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": "561",
"a": "2"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/solovay-strassen-test", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":"561","a":"2"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":"561","a":"2"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/solovay-strassen-test", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"n": "561",
"a": "2"
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.solovay_strassen_test",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
制限
max_digits | 1000 |
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
比較が示す内容
そのため分類名は probable_prime_to_base です。
入力の選択と検証
通常の JSON 数値ではすべての大きな整数を正確に表現できないため、文字列形式が重要です。
結果を適切に解釈する方法
false の場合、classification は composite となり、指定した底が候補数は素数ではないことの証明になります。課題やプロトコルでソロベイ・シュトラッセン法が必要な場合は、独立に選んだ複数の底で検査を繰り返し、各合格を証明ではなく追加の確率的証拠として扱ってください。新しいセキュリティ重視のシステムでは、手動で選んだ1つの底だけに依存せず、適切な反復回数と検証済みの乱数性を備えた、明確に規定された現代的な素数判定手順を使用してください。passes フィールドは、指定された組についてソロベイ・シュトラッセンの合同式が厳密に成立するかを示します。true の場合は probable_prime_to_base であり、prime ではありません。詳細フィールドでは、gcd が共通因数、jacobi_symbol が -1、0、1 のいずれか、euler_residue が計算済みモジュラーべき乗、expected_residue が法 n の範囲に正規化したヤコビ値を示します。API リクエストには公開基本料金 $0.002 が適用され、同じ決定的計算をブラウザーでも対話的に利用できます。
技術的な質問
n と a を JSON 数値ではなく文字列にする理由は何ですか?
10進文字列なら JavaScript の安全な数値範囲を超える整数も正確に保持でき、暗黙の丸めを防げます。
API リクエストの料金はいくらですか?
基本料金は1リクエスト当たり $0.002 です。1回で候補数と底の1組を評価します。