ForHosting KIT · 数学

離散対数のベビーステップ・ジャイアントステップ計算機

2の9乗を13で割ると余りは5なので、法13での底2に対する5の離散対数は9です。底、目標、法を入力すれば、法が素数でも合成数でも指数を求められます。ブラウザで無料で使えます。

  • 無料
  • ブラウザで動作
  • 登録不要
  • データは端末の外に出ません
ご利用方法 ウェブAPIメールTelegramアプリ 近日
入力した場合
G
2
H
5
N
13
結果
X
9
方程式
2^9 ≡ 5 (mod 13)

このベビーステップ・ジャイアントステップ計算機は、g の x 乗が n を法として h と合同になる非負整数 x を求めます。素体だけを扱う計算機とは異なり、事前に式を簡約するため、合成数の法や互いに素でない底にも対応します。結果には正規化した剰余と読みやすい検算式が含まれます。指定した生成元から目標値へ到達できない場合は、意味の曖昧な空の結果ではなく、明確な入力エラーを返します。

合同式を正確に指定します

3個の整数を指定してください。g は生成元または底、h は目標値、n は法です。計算機は g^x が n を法として h と合同になる非負整数 x を探索します。

負の底と目標値も受け付け、計算前にゼロ以上 n 未満の標準的な剰余へ正規化します。応答には正規化後の値が再掲されるので、元の入力が範囲外でも、実際に解いた式を確認できます。法は2以上で、公開されている上限以内なら素数でも合成数でも構いません。

通常の規約に従い、g^0 は n を法として1となるため、最初に指数ゼロを調べます。したがって、1と合同な目標値には直ちに x がゼロと返されます。成功時の応答には x、正規化した各項、方式名、読みやすい検算式が含まれます。

手作業での確認にも、自動テストのアサーションにもそのまま利用できます。

小さなステップと巨大なステップの仕組み

単純な探索では指数を順番に試すため、法に比例する回数の剰余乗算が必要になる場合があります。ベビーステップ・ジャイアントステップ法は、メモリを使って探索を高速化します。探索範囲の平方根に近い幅を選び、底の連続する小さな累乗をベビーステップとして表に保存します。

次に、その幅ずつ目標値を移動するジャイアントステップを調べます。同じ剰余が見つかれば、2個の添字を組み合わせて指数を復元できます。表の大きさと移動回数はいずれも n の平方根程度です。

この実装は決定的であり、候補の無作為抽出、乱数シード、外部サービス、時刻を一切使用しません。互いに素でない入力では、先に拡張方式を適用します。指数のずれと乗数を保持しながら共通因数を1個ずつ除去し、目標値へ到達不能と判明すれば直ちにエラーにします。

簡約後の底に逆元が存在する状態になってから表探索を行い、最後にずれを加算します。得られた指数は、応答前に別の剰余累乗計算で検証します。

上限と解がない場合

離散対数は常に存在するとは限りません。g の累乗が n を法とする剰余の一部だけを巡回し、h が生成される列に含まれないことがあります。null の項目を探さず、標準エラーコードで処理できます。

不正な整数、欠落した項目、範囲外の法も同じエラー分類となり、より具体的なメッセージが付きます。アルゴリズムはメモリ内に表を作るため、計算量は簡約後の法の平方根に従って増加します。上限によって過大なメモリ確保を防ぎ、実行時間を制限しています。

学習、テストベクトル、数学パズル、診断には適度な値をご利用ください。実用暗号の群は意図的に上限よりはるかに大きいため、秘密の復元には使えません。

剰余算の演習を検算

授業用の式を確認し、問題へ代入して確かめられる指数と読みやすい合同式を取得します。

決定的なテストベクトルを作成

合成数の法や共通因数を含む場合も含め、剰余累乗コード向けの既知解を生成します。

法は素数でなければなりませんか?

いいえ。 拡張簡約により、素数と合成数の法に対応し、g と n が共通因数を持つ多くの場合も処理できます。

どの指数が返されますか?

非負の指数を探索し、ゼロを明示的に処理したうえで、BSGS により検証済みの解を返します。

法に上限があるのはなぜですか?

この方式は平方根規模の時間とメモリを使います。上限によりハッシュ表と実行時間を予測可能にします。

指数が存在しない場合はどうなりますか?

底のべき乗はnを法とする余りの一部しか通らないことがあり、目標に届かない場合があります。そのときは空の答えではなく、指数が存在しないことをはっきり知らせます。

指数を1つずつ試すより速いのはなぜですか?

直接探すと法の大きさほどの手順が必要になることがあります。この方法は小さなべき乗の表を作り、大きな歩幅で進むため、どちらもnの平方根程度で済みます。

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

POSThttps://api.kit.forhosting.com/numth/baby-step-giant-step

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

curl -X POST https://api.kit.forhosting.com/numth/baby-step-giant-step \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"g":2,"h":5,"n":13}'
{
  "g": 2,
  "h": 5,
  "n": 13
}
{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.baby_step_giant_step",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

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

1リクエストあたり$0.002

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

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

合同式を正確に指定します

入力には JSON 整数のほか数字の文字列も使用できるため、クライアント言語で値を安全に表しにくい場合にも便利です。

上限、失敗、API の扱い方

その場合、この機能は指数が存在しない旨を示す invalid_input エラーを返します。これは意図した仕様であり、解がないときに後続処理を停止したいワークフローで役立ちます。ブラウザーと API は同じ純粋な計算処理を実行します。自動 API 処理は1項目あたり $0.002 で、ネットワーク依存の計算や不確定な結果はありません。

到達不能な目標値を検出

目標値が g の累乗列に含まれない場合、標準の invalid_input エラーで処理を停止します。

離散対数が存在しない場合はどうなりますか。

invalid_input で失敗し、指定値に対応する指数が存在しないことをメッセージで通知します。

API 呼び出しの料金はいくらですか。

1項目につき $0.002 です。ブラウザーでも同じ純粋なライブラリを使って対話的に計算できます。

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