離散対数ソルバー
13を法として2の何乗が5になるかを問うと、答えは9です。2^9 ≡ 5 (mod 13)だからです。底、目標、素数の法を入れると、確かめられる等式付きで最小の指数が分かります。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- G
- 2
- H
- 5
- 電力（W）
- 13
- X
- 9
- 方程式
- 2^9 ≡ 5 (mod 13)
離散対数問題とは、与えられた底 g を x 乗したものが素数 p を法として目標値 h と合同になるような整数 x を求める問題です。これは Diffie–Hellman 鍵交換や ElGamal 暗号、そして代数的暗号論の多くの教科書的演習を支えています。この機能は古典的な baby-step giant-step アルゴリズムを実装しています。すなわち、平方根時間で行う決定的な探索であり、最小の非負指数を復元するか、あるいは h が p を法とする乗法群において g の冪ではないことを証明します。
離散対数が求めるもの
整数 g、h、素数 p が与えられたとき、p を法とする底 g に対する h の離散対数とは、g の x 乗が p を法として h に合同となる任意の整数 x のことです。解が存在する場合、0 から p−2 までの範囲における最小の非負の代表元はその範囲を固定すれば一意に定まり、それがこのツールの返す値です。
通常の実数の対数とは異なり、任意の素数に対して機能する初等的な閉じた公式は存在しません。慎重に選ばれた大きな素数について x を復元することが困難であることこそが、離散対数暗号が有用である理由そのものです。しかし教育や小さなパラメータでの実験においては、やはり正しく検査可能なソルバーが必要です。
素数の仮定を検証し、入力を標準的な剰余系へ簡約し、体系的に探索し、検証可能な指数を出力するか解が存在しないことを明確に述べるものです。純粋な剰余算術であり、発見的手法もネットワーク呼び出しもありません。
baby-step giant-step が x を見つける仕組み
baby-step giant-step 法は、未知の指数を x = i × m + j と書き換えます。ここで m はおよそ群の位数 p−1 の平方根であり、i と j はどちらも 0 から m まで動きます。
アルゴリズムはまず、すべての baby 値 g の j 乗（mod p）を剰余をキーとするハッシュマップに格納し、次に目標値に g の m 乗の剰余逆元を繰り返し掛けながら giant ステップを進め、各中間剰余をマップで検索します。一致すれば i と j の両方が得られ、したがって x が求まります。
この手法は √p のオーダーの乗算とマップエントリを使うため、この機能では素数の法を約 1 兆付近で上限としています。探索の前に、ソルバーは p に対して決定的な Miller–Rabin 素数判定を実行します。
入力、上限、料金、そして解が存在しない場合
法の上限内であれば、大きな整数を表す数字列も受け付けます。もし h が g によって生成される（p を法とする）巡回部分群に含まれない場合——たとえば g が真部分群のみを生成し h がその外側にある場合——ソルバーは誤った x を捏造する代わりに、solved を false とし、指数を null として説明的なメッセージを返します。
入力が整った形式であり、数学的な答えが「対数は存在しない」というものであるため、この結果はクライアントエラーではなく計算の成功です。検証に失敗した場合は課金されません。ブラウザ内のツールは同一のライブラリをアカウント不要で無料で実行します。
この結果は、宿題の確認、暗号ライブラリのための既知解テストの生成、あるいは実際のプロトコル設計でパラメータを拡大する前の部分群所属の調査に利用できます。
活用例
宿題や試験の検証
学生や指導者は 2^x ≡ 5 (mod 13) のような離散対数の演習を確認し、指数と、解答用の印刷可能な合同式の両方を受け取れます。
暗号コードの既知解テスト
ライブラリの作者は小さな素体のインスタンスを CI に投入し、剰余冪や逆元のヘルパーが独立した BSGS 参照実装と一致し続けるようにします。
部分群所属の実験
研究者は小さな素数を法として候補となる底や目標値を試し、本番規模のパラメータへ進む前に h が g の生成する部分群に含まれるかどうかを確認します。
よくある質問
どのアルゴリズムを使っていますか？
baby-step giant-step 法（Shanks）です。p に対する決定的な素数判定の後、g^x ≡ h (mod p) を満たす最小の非負の x を、おおよそ O(√p) の時間とメモリで見つけます。
指数が存在しない場合はどうなりますか？
短いメッセージとともに solved: false と x: null が返ります。これは（h が g の冪ではない mod p という）妥当な数学的結果であり、課金エラーや検証エラーではありません。
2^x ≡ 5 (mod 13)はどう解きますか？
底に2、目標に5、素数の法に13を入れます。答えは9で、2の9乗を13で割ると余りが5になり、それより小さい指数ではそうなりません。
法が素数でない場合はどうなりますか？
探索は始まりません。最初に法が素数かどうかを確かめ、合成数なら意味のない指数を返さずに、分かりやすいメッセージで断ります。
素数の法はどこまで大きくできますか？
約1兆までです。宿題やプロトコルの説明、小さな実験には十分で答えもすぐ出ますが、実際の暗号を守る非常に大きな素数向けではありません。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/numth/discrete-log \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"g":2,"h":5,"p":13}'const res = await fetch("https://api.kit.forhosting.com/numth/discrete-log", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"g": 2,
"h": 5,
"p": 13
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/discrete-log",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"g": 2,
"h": 5,
"p": 13
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/discrete-log", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"g":2,"h":5,"p":13}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"g":2,"h":5,"p":13}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/discrete-log", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"g": 2,
"h": 5,
"p": 13
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.discrete_log",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
制限
max_p | 1000000000007 |
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
整数 g、h、素数の法 p の 3 つを入力すると、解、簡約された剰余、そして解が存在する場合は検証式を含む構造化された JSON の回答が返されます。
離散対数が求めるもの
それがこのエンドポイントの契約です。API パスは POST /numth/discrete-log で、ブラウザのランナーは同一の同型ライブラリを実行するため、無料のローカル実行と有料の API 結果は一致します。
baby-step giant-step が x を見つける仕組み
宿題やプロトコルの解説、小さな部分群のストレステストには十分大きく、それでいて Worker 上でメモリと遅延が予測可能な範囲に収まるよう制限されています。p が合成数であれば、素体の乗法群ではない構造の中で対数をでっち上げるのではなく、invalid_input として呼び出しは失敗します。0 から p−1 の範囲外の底や目標値は p を法として簡約され、レスポンスは簡約後の g、h、p を返すので、呼び出し側は実際に解かれたインスタンスを正確に監査できます。
入力、上限、料金、そして解が存在しない場合
必須フィールドは g（底）、h（目標剰余）、p（素数の法）です。クライアントエラーが対象とするのは、フィールドの欠落、非整数、許容範囲外の法、そして合成数の p です。API の料金は、成功したリクエスト 1 件につき item 単位で一律 $0.002 です。
技術的な質問
この API で離散対数を解くにはどうすればよいですか？
整数 g、h、素数 p を離散対数エンドポイントに POST します（または無料のブラウザフォームを使います）。レスポンスには solved、存在する場合の指数 x、簡約された剰余、そして検証式が含まれます。
p が素数でない場合はどうなりますか？
リクエストは invalid_input で失敗します。このツールは素体の乗法群における離散対数を定義しており、合成数を法として黙って動作することはありません。
API の料金はいくらですか？
ブラウザツールは無料です。API はプリペイドの KIT 残高から、成功したリクエスト 1 件につき $0.002 を課金します。無効な入力は課金されません。サブスクリプションは不要です。