ForHosting KIT · 数学

n乗剰余チェッカー

ある数が素数を法としてk乗剰余かどうかを判定します。2は法7で平方剰余です。2の3乗を7で割った余りが1になるからです。平方、立方、さらに高いべきも正確な整数計算で扱います。ブラウザで無料で使えます。

  • 無料
  • ブラウザで動作
  • 登録不要
  • データは端末の外に出ません
無料で実行 API仕様を見る
ご利用方法 ウェブAPIメールTelegramアプリ 近日

無料で実行

計算例

入力した場合
A
2
K
2
電力（W）
7
結果
A の法
2
Gcd
2
群の位数
6
判定指数
3

整数 a が素数 p を法とする k 乗剰余であるとは、ある整数 x について x の k 乗が a と p を法として合同であるときをいいます。この問いは二次剰余性（k が 2 の場合）を立方・高次べき、および競技整数論や入門暗号で用いる任意の正の指数へ一般化します。本機能は候補 a、正の指数 k、素数の法 p を受け取り、a を 0 から p−1 の範囲へ還元し、p が素数であることを確認したうえで、p 元体の乗法群に対する標準的な巡回群判定を適用します。a が p で割り切れるとき、k が 1 以上であれば答は常に肯定です。0 の正のべきは 0 だからです。

素数を法とする k 乗剰余の意味

素数の法 p と正整数 k を固定します。p を法とする剰余類は体をなし、その非零元は位数 p−1 の巡回乗法群をなします。p で割り切れない整数 a が p を法とする k 乗剰余であるのは、ちょうど a が、各非零類 x を x の k 乗へ写す写像の像に属するときです。

群が巡回であるため、その像は k と p−1 の最大公約数 d を指数にもつ一意の部分群であり、a がその部分群に属するのは a を (p−1)/d 乗した値が p を法として 1 と合同であるとき、かつそのときに限ります。この一度のモジュラべき乗がここで用いる判定手続きです。

a が p で割り切れるとき、x の k 乗が a と合同である合同式は、k が 1 以上なら常に x が 0 という自明解をもち、したがって 0 は常に k 乗剰余として扱います。特殊な場合は既知の道具に戻ります。

k が 2 で p が奇素数ならオイラーの二次剰余判定（ルジャンドル記号と同じ情報）となり、k が p−1 ならフェルマーの小定理により非零の a はすべて剰余です。教科書の答と自動テストがビット単位で一致するよう、厳密な整数のモジュラ演算のみを用います。

高次べき剰余の検査が実務で現れる場面

競技プログラマはモジュラ立方根や高次根の抽出を試みる前に高速なオラクルを必要とします。剰余ビットが偽なら x を探す意味がありません。暗号の学生は有限体におけるべき写像の像、インデックス計算の例、メッセージ類が k 乗かどうかで写像適用前の可否が決まる教材構成を検証します。

二次にはすでにルジャンドル記号やヤコビ記号を使う研究・演習パイプラインでも、ライブラリを切り替えずに立方や高次べきについて同じ可否答が必要になることがよくあります。二次剰余だけが必要なら専用の二次剰余・ルジャンドル記号ツールが引き続き使えます。本ページは素数法に対する一般的な k 乗判定です。

活用例

演習・競技での確認

自前のモジュラべき乗と gcd パイプラインを書かずに、整数論の演習で a が素数 p を法とする k 乗かどうかを判定します。

根の抽出前の事前フィルタ

素体上で立方根や高次根アルゴリズムを試みる前に、非剰余を早い段階で棄却します。

巡回群判定の授業

具体的な三つ組について gcd(k, p−1)、判定指数、剰余性を証明または反証するモジュラべきを学生に示します。

よくある質問

素数 p を法とする k 乗剰余とは何ですか？

整数 a が素数 p を法とする k 乗剰余であるとは、x^k ≡ a (mod p) をみたす整数 x が存在することです。本ツールは F_p* 上の巡回群判定でその事実を報告します。

なぜ p は素数でなければなりませんか？

判定手続きは、p を法とする乗法群が位数 p−1 の巡回群であることに依拠し、これは素数の法で成り立ちます。

可否の答はどのように計算されますか？

d = gcd(k, p−1) とします。a が p で割り切れないとき、a が k 乗剰余であるのは a^((p−1)/d) ≡ 1 (mod p) のとき、かつそのときに限ります。

2は法7で立方剰余ですか？

いいえ。3と6の最大公約数は3なので、2の2乗を調べると法7で1ではなく4になります。つまり、3乗して余り2になる整数はありません。

aは負の数やpより大きな数でもよいですか？

はい。絶対値で1兆まで入力できます。判定の前にaは0からp − 1までの余りに直されます。aがpの倍数なら、答えは常に「はい」です。

関連ツール

平方剰余チェッカー数学二次非剰余一覧 mod p数学合同 n 乗根計算機数学原始根計算機数学べき剰余計算機数学フェルマーの小定理計算機数学逆元モジュロ計算機数学ルジャンドル記号 (a/p)数学

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/numth/power-residue-check

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

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/numth/power-residue-check \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"a":2,"k":3,"p":7}'

リクエスト例

{
  "a": 2,
  "k": 3,
  "p": 7
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.power_residue_check",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

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

料金

1リクエストあたり$0.002

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

エラー

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

技術的な注記

素数を法とする k 乗剰余の意味

本エンドポイントは浮動小数の根や近似べきを作りません。

入力契約・素数検査・応答フィールド

整数 a、k、p を送ってください。指数 k は 1 以上かつ 1 兆以下でなければなりません。一方 1 は任意の素数について常に k 乗剰余です。非整数、必須欠落、1 未満の指数は明確な英語メッセージで検証失敗となります。法 p は 2 以上 1 兆以下の素数である必要があり、9 や 15 のような合成数は invalid_input で拒否され、フィールド名と p が素数でない旨のメッセージが返り、課金されません。候補 a は負でも p より絶対値が大きくてもよく（同じ 1 兆の上限まで）、検査前に a_mod として 0 以上 p 未満の半開区間へ還元されます。成功時のペイロードには常に a、k、p、a_mod、真偽値 is_power_residue、k と p−1 の gcd、p−1 に等しい group_order、短い英語の interpretation 文字列が含まれます。a_mod が非零のときは、criterion_exp（その gcd で割った (p−1)）と、a_mod をその指数で p を法としてべき乗した criterion_value も報告され、剰余ビットが真のときちょうど 1 になります。任意フィールドに null を埋めることはなく、零剰余の場合は判定対を単に省略します。手計算で再現できる古典例：a=2、k=3、p=7 では 3 と 6 の gcd は 3 なので判定指数は 2、2 の二乗は 7 を法として 4 であり 1 ではないため、2 は 7 を法とする立方剰余ではありません。同じ純粋関数が無料ブラウザと有料 API 経路の両方を動かします。

高次べき剰余の検査が実務で現れる場面

教員は「3 が 11 を法とする 5 乗剰余か」「13 を法とする立方剰余類は何か」といった問題を出し、手書き表ではなく決定的な JSON 答を望みます。本機能は純粋な parse エンジンであるためモデルの揺らぎも外部 API キーも保存状態もなく、同じ三つ組は常に同じ真偽値と判定値を返します。API 料金は成功 1 件あたり公開基準の $0.002 で、検証失敗は残高を消費しません。

技術的な質問

0 は k 乗剰余とみなされますか？

はい。すべての k ≥ 1 について 0^k ≡ 0 (mod p) なので、a_mod = 0 は常にべき剰余であり、判定指数フィールドは省略されます。

料金はいくらですか？

ブラウザツールは無料でローカル実行です。API 要求は成功 1 件あたり $0.002 の KIT 前払い残高を使い、無効入力は課金されません。

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