ForHosting KIT · 数学

合同 n 乗根計算機

素数を法とした数のk乗根をすべて求めます。17を法とした2の平方根は6と11で、昇順に並べて表示します。根が存在しない場合は、空の一覧ではなくはっきりした答えを返します。ブラウザで無料で使えます。

無料
ブラウザで動作
登録不要
データは端末の外に出ません

無料で実行 API仕様を見る

ご利用方法ウェブAPIメールTelegramアプリ近日

計算例

入力した場合

A: 2
K: 2
電力（W）: 17

結果

A の法: 2
根の数: 2
根: 6, 11
kとφの最大公約数: 2

素数 p を法とする整数 a の合同 k 乗根とは、x の k 乗が a と合同になるような剰余 x のことです。素数法での平方根は Tonelli–Shanks の解説に、立方根や高次根は有限体の代数に現れ、暗号の授業では根をすべて列挙するか、存在しないときに明確に拒否する信頼できるオラクルが必要です。本計算機は a、正の指数 k、素数法 p を受け取り、a を 0 から p−1 までの標準代表に還元し、その体における解の完全な昇順リストを返します。

合同 k 乗根とは何か、いつ存在するか

素体の乗法群では、零でない剰余はすべて p−1 を割り切る明確な位数を持ちます。x を k 乗する写像の像は k 乗剰余の集合です。零でない目標 a について、x の k 乗が a と合同である合同式が解を持つのは、d を k と p−1 の最大公約数として a の (p−1)/d 乗が 1 と合同であるときに限ります。

この条件が成り立つとき、相異なる非零根はちょうど d 個です。零剰余は特別で、任意の正の冪で 0 になるため、a が 0 と合同なら根は 0 のみです。合成数の法はこの巡回群の描像の外にあり、中国剰余定理による局所根の積を素体の答えであるかのように装わないよう拒否します。

学習者はルジャンドル記号の手計算で平方根に、円分コセットや離散対数の学習で高次根に、非立方剰余の立方根を求める課題で存在失敗に出会います。

本計算機がすべての根を求める手順

実装はまず k が正の整数であること、および公開上限内の素数 p であることを決定的 Miller–Rabin で確認します。a を p で還元したのち、零剰余の場合は根 0 のみを返します。非零の a では d = gcd(k, p−1) を計算し、上記の存在判定を適用します。

d が 1 のときは k の p−1 を法とする逆元を指数とする a の冪で一意の根を得ます（互いに素な指数の高速経路）。d が 1 より大きいときは p を法とする原始根 g を求め、baby-step giant-step で a の底 g の離散対数を復元し、k と y の線形合同式を p−1 を法として解きます。返却前に各根を合同冪乗で検証します。

a と k の絶対値は 1 兆まで、素数 p は約 10 億までで baby-step giant-step のメモリを実用に保ち、d が 1 万根を超える場合はクライアントを溢れさせず拒否します。

活用例

暗号と有限体の実験

教員と学生は小さな素数を法とする平方根や高次根をすべて列挙し、存在条件を確認し、例の剰余に k 乗根がないとき gcd(k, p−1) を調べられます。

競技プログラミングと合同代数

競技プログラマは手作りの Tonelli–Shanks や総当たりループの代わりに、決定的オラクルで x^k ≡ a (mod p) の解を照合できます。

よくある質問

p が素数でない場合は？

乗法群が巡回で存在判定が厳密になるよう、本計算機は素数法を必須とします。検証失敗は課金されません。

合同 n 乗根計算機はどのアルゴリズムを使いますか？

素数判定に Miller–Rabin、gcd(k,p−1)=1 のときは逆元指数、それ以外は原始根・baby-step giant-step 離散対数・線形合同式の求解です。すべて決定的です。

17を法とした2の平方根は何ですか？

6と11です。どちらも2乗して17で割ると余りが2になります。計算機は両方を昇順に並べ、根の個数とあわせて表示します。

根はいくつありますか？

根が存在する場合、その個数はkとp − 1の最大公約数とちょうど同じです。17を法とした2の平方根なら2つです。0の根は0だけで、根が1万個を超える場合は受け付けません。

k乗根が存在しない場合はどうなりますか？

空の一覧を返すのではなく、解がないことをはっきり知らせます。数論の教科書と同じく「解なし」として扱うため、成功した結果と取り違えることがありません。

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/numth/modular-nth-root

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

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

curl -X POST https://api.kit.forhosting.com/numth/modular-nth-root \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"a":2,"k":2,"p":17}'

const res = await fetch("https://api.kit.forhosting.com/numth/modular-nth-root", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "a": 2,
    "k": 2,
    "p": 17
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/modular-nth-root",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "a": 2,
    "k": 2,
    "p": 17
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/modular-nth-root", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"a":2,"k":2,"p":17}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"a":2,"k":2,"p":17}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/modular-nth-root", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "a": 2,
  "k": 2,
  "p": 17
}

レスポンス例

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

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

料金

1リクエストあたり$0.002

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

エラー

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

技術的な注記

p が合成数のとき要求は invalid_input で失敗し、(p−1) と k の最大公約数 d について a の (p−1)/d 乗が 1 と合同でない存在判定にも失敗し、空の成功リストは返しません。同じ純粋で決定的なモジュールが無料ブラウザツールと前払い API を駆動するため、授業デモと自動採点は根について食い違いません。

合同 k 乗根とは何か、いつ存在するか

非存在時に厳密な invalid_input を返すことは、「解なし」と述べる数論の用語に沿い、課金系が成功とみなしうる空リストとは異なります。

本計算機がすべての根を求める手順

整数フィールド a、k、p で能力を呼び出します。各解 y は根 g^y を与え、相異なる根は安定した API 契約のため昇順に並べます。

実用、制限、料金、提供形態

暗号のノートを読むとき、競技プログラミングの出力を確認するとき、有限体の課題を採点するときに平方根や高次根をすべて得たい場合はブラウザツールを使ってください。検証失敗、合成法、証明された非存在は残高を消費しません。受け付ける入力は絶対値最大 1 兆の整数 a、1 から 1 兆までの指数 k、2 から約 10 億までの素数 p（根数の安全上限付き）です。Tonelli–Shanks や離散対数ルーチンを埋め込まずに多数の合同根照会が必要なスクリプト、LMS プラグイン、研究ノートでは API を使ってください。成功した要求は 1 件あたり $0.002 の課金単位です。応答は a、k、p、還元済み a_mod、root_count、昇順 roots 配列、d に等しい gcd_k_phi、表示用 equation 文字列、アルゴリズム経路を示す method タグを返します。正確な合同算術を浮動近似より好む暗号サンドボックス、競技補助、代数的数論デモにエンドポイントを接続できます。単位は単一 item、エンジンは純粋 parse のため遅延は低く、無料 Web 経路は有料 API を第二のコード経路なしで反映します。

連携の活用例

課題チェッカーと研究ノート

自動採点とスクリプトは根集合を確認し、invalid_input で合成法を拒否し、中間積を文書化された整数範囲内に保てます。

技術的な質問

この API で合同 k 乗根を計算するには？

整数フィールド a、k（≥ 1）、素数 p を含む JSON を numth.modular_nth_root に送ってください。成功時は昇順配列 roots、root_count、a_mod、gcd_k_phi を返します。

k 乗根が存在しない場合は？

要求は invalid_input で失敗し、メッセージは判定 a^((p−1)/gcd(k,p−1)) ≢ 1 を引用します。非存在時に空の成功リストは返しません。

合同 n 乗根計算機は無料ですか？

ブラウザツールはお使いの端末で無料です。API 呼び出しは成功 1 件あたり $0.002 の前払い KIT 残高を使い、無効入力と非存在エラーは課金されません。

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

合同 n 乗根計算機

無料で実行

計算例

合同 k 乗根とは何か、いつ存在するか

本計算機がすべての根を求める手順

活用例

暗号と有限体の実験

競技プログラミングと合同代数

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

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

リクエスト例

レスポンス例

料金

エラー

技術的な注記

合同 k 乗根とは何か、いつ存在するか

本計算機がすべての根を求める手順

実用、制限、料金、提供形態

連携の活用例

課題チェッカーと研究ノート

技術的な質問

ありがとう