ForHosting KIT · 数学

指定した底によるソロベイ・シュトラッセン素数判定

13を底2で調べると、2つの剰余がどちらも12になるため、13は底2に対する確率的素数と判定されます。一致しなければ合成数であることが証明されます。ブラウザで無料で使えます。

  • 無料
  • ブラウザで動作
  • 登録不要
  • データは端末の外に出ません
ご利用方法 ウェブAPIメールTelegramアプリ 近日
入力した場合
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からも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

POSThttps://api.kit.forhosting.com/numth/solovay-strassen-test

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"}'
{
  "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リクエストまでです。

1リクエストあたり$0.002

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

max_digits1000
HTTPコード意味
401unauthorizedAPIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
402insufficient_balance残高が不足しています。チャージ後に再度お試しください。
404unknown_type指定されたタスクタイプは存在しません。タイプ名を確認してください。
429rate_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組を評価します。

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