原始根計算機
素数の最小の原始根を求めます。法7では3で、そのべきは0以外の6つの余りをすべて通りますが、2のべきは3つで繰り返します。p − 1の素数べきへの分解も表示されます。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- 電力（W）
- 7
- 原始根
- 3
- 位数
- 6
- 最大桁数
- 15
素数pを法とする原始根とは、pを法とする0でない剰余の乗法群の生成元です。平たく言えば、1からp-1の間のある整数gには、その連続するべきg、g²、g³…が、繰り返す前にpと互いに素なすべての剰余類を最終的に取り尽くすという性質があります。そのgは(Z/pZ)*の生成元であり、そのような最小の正のgが、学生、暗号研究者、コンテストの解答者が調べる古典的な数論の答えです。この計算機は素数の法pを受け取り、pが素数であることを検証し、p-1を因数分解し、群の位数とp-1の素数べき分解とともに最小の原始根を返します。この経路は完全に決定的です:固定された証人集合によるミラー・ラビン法、試し割りによる因数分解、法べき乗算はすべて、通信もランダム性も日付依存もありません。宿題や簡単な確認にはブラウザで無料でお使いいただけます。
原始根とは何か、結果に表示される内容
素数の法pに対して、剰余1、2、…、p-1の集合は位数p-1の巡回乗法群を形成します。整数gは、その群におけるgの位数がちょうどp-1のとき、pを法とする原始根です:0からp-2までのkについてgのk乗はすべてpを法として異なり、0でないすべての剰余を使い尽くします。すべての整数が生成元というわけではありません。
たとえば7を法として2のべきは繰り返す前にわずか3つの値しか巡らないため、2は原始根ではありませんが、3は6つの単位すべてを生成し最小の原始根です。原始根として提示される確率的な推測はなく、合成数の法に対する黙った代替措置もありません。古典的な意味での原始根は素数(そしてこのページでは扱わない少数の特殊な合成数の族)に対して定義されるためです。
素数を法とする生成元ではなく任意の整数の因数が必要な場合は、代わりに素因数分解の機能をお使いください。このページが答えるのは素数を法とする最小の生成元の問いのみです。
最小の原始根が学習・暗号・コードで果たす役割
学生は、巡回群、離散対数、素数位数の有限体の構造を学ぶときに原始根に出会います。ワークシートはしばしば小さな素数を法とする最小の生成元を求め、このページはその答えを、位数のテストを手計算で検証できるようp-1の裏付けとなる因数分解とともに返します。
コンテストの問題やプログラミング課題の文は、原始多項式の構築、離散対数表のインデックス作成、数論デモの播種のサブルーチンとして、しばしば最小の原始根を要求します。応用暗号学では、ディフィー・ヘルマンや関連する構成は大きな素数位数の部分群の生成元を必要とします。
活用例
宿題とコンテストの準備
教科書の演習、離散対数のドリル、最小の生成元を要求するプログラミングコンテスト向けに、素数を法とする最小の原始根を調べます。
決定的な暗号パラメータのテスト
法の位数の単体テスト、おもちゃの素数でのディフィー・ヘルマンのデモ、静的テーブルを埋め込まないCIアサーション向けに再現性のある生成元を生成します。
よくある質問
このアルゴリズムはランダム化されていますか?
いいえ。 素数性判定は決定的なミラー・ラビンの証人集合を使い、因数分解は試し割り、法のべき乗算は正確です。同じpは常に同じ根を返します。
送信できる最大の素数は?
pは最大15桁の10進数までです。それより大きい値は、桁数上限を超えたという明確なメッセージとともに失敗します。
p − 1の素因数が表示されるのはなぜですか？
判定にそれを使うからです。p − 1を割るすべての素数qについて、gの(p − 1)/q乗が法pで1にならなければ、gは原始根です。素因数があれば自分で確かめられます。
群の位数とは何ですか？
p − 1のことで、法pで0以外の余りがいくつあるかを表します。7なら位数は6で、原始根は繰り返す前にその6つの余りをすべて通ります。
2は法7の原始根ですか？
いいえ。2のべきは法7で3つの値だけを繰り返すため、6つの余りすべてには届きません。法7で最小の原始根は3です。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/numth/primitive-root \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"p":"7"}'const res = await fetch("https://api.kit.forhosting.com/numth/primitive-root", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"p": "7"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/primitive-root",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"p": "7"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/primitive-root", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"p":"7"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"p":"7"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/primitive-root", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"p": "7"
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.primitive_root",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
制限
max_digits | 15 |
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
フィクスチャや教育デモ、法pに関する再現性のある生成元が必要な暗号パラメータのノートブックを自動化する場合は、成功したリクエストごとに$0.002のAPIをご利用ください。
原始根とは何か、レスポンスに含まれる内容
このツールは、10進文字列としての素数p、最小の原始根、群の位数p-1、成功時には常にtrueとなる真偽値のis_primeフラグ、位数のテストに使われたp-1の整理された素数べき因数、そしてクライアントがバッチの前に検証できる公開されたmax_digitsの上限を返します。失敗のモードは明確です:pの欠落、非整数、分数、指数表記、2未満の値、15桁を超える値、そして合成数のpは、すべてinvalid_inputを発生させます。
素数の確認方法と最小の根の探索方法
先頭の任意のプラス記号は許可されますが、埋め込まれた空白、16進数のプレフィックス、指数表記は不正なセルが誤った生成元にすり替わることを防ぐため明確なメッセージとともに拒否されます。解析後、エンジンは15桁以内のすべての整数に十分であることが証明されている証人集合を使う決定的なミラー・ラビンの素数性テストを実行します。優先されるフィールドはJSON整数または10進文字列としてのpです。エイリアスprime、modulus、nも受け付けるため、フォームやクエリ文字列、スプレッドシートが同じ契約を再利用できます。テストが失敗すると、レスポンスはpが素数でないことを名指しするinvalid_inputになります。pが素数のとき、エンジンはホイール試し割りでp-1を因数分解し、その位数の異なる素因数qを収集し、g = 2、3、4…の中から、そのすべてのqについてgの(p-1)/q乗がpを法として1に合同でない最初の候補を探します。この古典的な基準は、gの位数がp-1であるための必要十分条件です。p=2という特殊なケースは、その群における唯一の単位である原始根1を返します。
最小の原始根が学習・暗号・コードで果たす役割
実運用のシステムは慎重に選ばれた安全素数と標準化された生成元を使いますが、宿題規模のパラメータを検証したり、法の位数ヘルパーの単体テストを書いたり、なぜある素数ではg=2が機能して他では機能しないのかを説明したりする際には、通常の素数に対する透明な計算機が今なお役立ちます。このページでは処理はすべてブラウザ内で完結し、API経由では成功した照会1件ごとに$0.002かかり、検証に失敗した場合は課金されず、レスポンスを返した後は何も保存されません。無料のインタラクティブな検証と、同一の結果を返す有料APIというこの分離はKITのtier Aカタログ全体の方針と一致しており、教室でのデモから自動パイプラインへ、数学的な結果を変えることなく移行できます。
連携の活用例
巡回群の指導
返された根のべきが(Z/pZ)*を使い尽くすことを示し、レスポンス中のp−1の因数分解を使って非生成元と対比します。
技術的な質問
原始根計算機の料金は?
このページのブラウザ上では無料です。API経由では成功したリクエストごとに$0.002かかり、無効な入力には課金されません。
pが素数でない場合はどうなりますか?
このツールは非素数をinvalid_inputで拒否します。この意味での古典的な原始根は素数の法に対して定義され、合成数のnは対象外です。
結果は常に最小の原始根ですか?
はい。エンジンはg = 2、3、4…と探索し、最初の生成元を返すため、根は正の剰余の中で最小です。