ForHosting KIT · 開発者向けツール

剰余における乗法位数計算機

乗法位数計算機は、a の k 乗が n を法として 1 と合同になる最小の正の指数 k を求めます。整数の底 a と法 n を入力すると、簡約した底、オイラーのトーシェント、乗法位数、合同式による直接の検算を表示します。この計算が定義されるのは a と n が互いに素の場合だけです。そのため、不適切な組には誤解を招く数値ではなく明確なエラーを返します。合同算術の演習、巡回部分群の分析、周期的なパターン、初等整数論にご活用いただけます。

● Beta無料・ブラウザ内で実行
ご利用方法 ウェブAPIメールTelegramアプリ 近日

乗法位数の意味

整数 a と n に対し、a の n を法とする乗法位数とは、a<sup>k</sup> を n で割った余りが 1 になる最小の正の整数 k です。「最小の正の整数」という条件が重要です。それより後の指数でも余りが 1 になる場合がありますが、乗法位数は合同式の乗法において単位元へ最初に戻る時点を表します。たとえば、2 の累乗を 9 で割った余りは 2、4、8、7、5、1 の順になるため、乗法位数は 6 です。この概念は、n を法とする可逆な剰余類のうち、a が生成する巡回部分群の大きさを示します。本計算機は処理の前に a を標準的な非負の剰余へ直すため、負の底や n より大きい底も一貫して扱えます。また、得られた乗法位数から検算値を計算して返します。検算値が 1 なら定義となる合同式を確認でき、候補の指数を縮小する処理によって、残る真の約数が同じ条件を満たさないことも保証されます。

互いに素である必要がある理由

n を法とする乗法位数が存在するのは、gcd(a, n) が 1 の場合だけです。これは単なる入力上の取り決めではありません。ある元の累乗が有限な単元群に属し、再び 1 に戻るためには、その元が n を法とする乗法逆元を持つ必要があります。a と n に共通因子がある場合、a の正の累乗にはその因子による割り切れ方が残るので、n を法として 1 と合同にはなりません。本計算機は最初にこの条件を調べ、満たされない場合は実際の最大公約数を示します。また、通常の乗法位数は自明でない剰余系で考えるため、法 n は 2 以上でなければなりません。公開されている範囲内なら、底には 0、負の整数、正の整数を指定できます。ただし 0 はどの許容された n とも互いに素ではないため、計算は成立しません。入力には小数や科学表記による近似値ではなく、正確な整数をご使用ください。最大公約数、素因数分解、合同式の累乗が依存する離散的な算術を正しく保てます。

最小の指数を求める方法

本計算機は、指数を 1 つずつ順番に試す方式ではありません。まず n を必要な範囲で素因数分解し、オイラーのトーシェント phi(n) を計算します。オイラーの定理により、gcd(a, n) が 1 なら a の phi(n) 乗は n を法として 1 と合同です。したがって、求める乗法位数は phi(n) の約数になります。次に phi(n) を素因数分解し、現在の候補をその素因数の 1 つで割っても合同式の累乗が 1 になるかを繰り返し調べます。1 になるたびに、より小さい値を新しい候補とします。どの素因数も取り除けなくなったとき、残った候補が乗法位数です。合同式の累乗には二乗法を用い、中間値を常に n を法として簡約するため、整数演算は一貫して正確です。特に乗法位数が大きい場合、正の指数をすべて調べる方法より大幅に高速です。試し割りの処理量に明確で決定的な上限を設けるため、入力は 1 兆までに制限しており、ブラウザーと自動 API 呼び出しの双方で安定してご利用いただけます。

整数論の演習を確認する

長い累乗列を手作業で並べずに、最小の指数、オイラーのトーシェント、簡約した剰余、最後の合同式をご確認いただけます。

巡回部分群を調べる

可逆な剰余が生成する部分群の大きさを求め、原始根を調べる際に、その乗法位数と phi(n) を比較できます。

合同式の周期パターンを分析する

漸化式、整除性、初等暗号の計算で、n を法とする反復乗算の正確な周期を求められます。

計算結果の乗法位数は何を表しますか?

a^k が n を法として 1 と合同になる最小の正の整数 k を表します。

なぜ a と n は互いに素でなければならないのですか?

gcd(a, n) が 1 の剰余だけが n を法として可逆であり、乗法位数を持つことができます。

底 a に負の整数を指定できますか?

はい。乗法位数を求める前に、a を n を法とする非負の剰余へ直します。

乗法位数は常にオイラーのトーシェント phi(n) と等しいですか?

いいえ。有効な入力では乗法位数は必ず phi(n) の約数ですが、a が n を法とする単元群全体を生成する場合に限り phi(n) と等しくなります。

API リクエストの料金はいくらですか?

API リクエスト 1 回の料金は $0.002 です。同じ決定的な計算をブラウザーでは無料でご利用いただけます。

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

POSThttps://api.kit.forhosting.com/numth/multiplicative-order

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

curl -X POST https://api.kit.forhosting.com/numth/multiplicative-order \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"a":2,"n":9}'
{
  "a": 2,
  "n": 9
}
{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.multiplicative_order",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

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

1リクエストあたり$0.002

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

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

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