ForHosting KIT · 数学

二次非剰余一覧 mod p

奇素数を法として、決して平方にならない余りをすべて一覧にします。法7では平方は1、2、4なので、非剰余は3、5、6です。個数は常に(p − 1)/2となり、結果の確認に使えます。ブラウザで無料で使えます。

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

無料で実行 API仕様を見る

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

計算例

入力した場合

電力（W）: 7

結果

非剰余: 3, 5, 6
数量: 3
剰余の個数: 3
期待される個数: 3

奇素数 p を法とする二次非剰余とは、合同式 x の二乗が a に合同になる整数解が存在しない、零でない剰余類 a のことです。任意の奇素数について、零でない剰余類のちょうど半分が剰余、残り半分が非剰余になるため、非剰余の一覧は単なる可否判定ではなく、構成的で完備な答えになります。学生、競技プログラマー、暗号を学ぶ方は、より重いモジュラー平方根の手続きに進む前に、表、ルジャンドル記号の抜き打ち確認、教材例のために集合全体を必要とすることが多いです。本機能は奇素数 p を一つ受け取り、素数性を検証し、決定的な走査で各平方類を印付け、1 から p 引く 1 までの非剰余の昇順リストと理論上の個数を返します。

二次非剰余と、リストが 1..p−1 の半分になる理由

奇素数 p を固定します。p で割り切れない各整数 a について、多項式 X の二乗から a を引いたものは、p を法とする整数体において根を二つ持つか、まったく持たないかのいずれかです。根を持つ類が零でない二次剰余、持たない類が二次非剰余です。

零は常に平方（零の二乗）であり、教科書では通常、零でない剰余と非剰余の分割とは別に扱います。乗法構造が完全な均衡を強制します。位数 p 引く 1 の乗法群上で x を x の二乗へ送る写像は、指数 2 の部分群への 2 対 1 写像であり、したがって剰余はちょうど (p 引く 1) を 2 で割った個数、非剰余も同数になります。

古典的な小表が個数を確認します。7 を法とすれば零でない平方は 1, 2, 4 なので非剰余は 3, 5, 6 です。11 を法とすれば非剰余は 2, 6, 7, 8, 10 です。

ルジャンドル記号は同じ分割をプラス 1 またはマイナス 1 として符号化しますが、単一の記号では集合全体を列挙できません。教材スライド、性質ベーステストのフィクスチャ、宿題の解答キーのために完全なリストが必要なときは、平方を一度走査して補集合を取る方法が透明で構成的です。

完全な非剰余リストが実務で現れる場面

数論の講義では、17 を法とするすべての二次非剰余を列挙せよ、あるいは小さな素数間で剰余表を比較せよといった問題が出ます。競技プログラマーは、ハッシュ試験用の非剰余をサンプリングする生成器や、素朴な平方根予想への反例を作るときに、集合をオラクルとして使います。

暗号を学ぶ学生は、二次相互律、オイラーの判定、剰余構造に依存する Rabin 風の暗号を学ぶ前に、非剰余集合の大きさに関する教科書の主張を検証します。モジュラー算術ヘルパー向けの性質テストを書く技術者は、控えめな上限までのすべての奇素数について、自前の剰余探索の補集合がこのリストと一致することを主張できます。

同じ p は常に同じ nonresidues 配列を返します。検証失敗は残高を消費しません。一般の法に対する一つの a についてルジャンドル記号だけ、あるいは可否だけが必要な場合は、剰余・記号の姉妹ツールを優先してください。

本ランディングは奇素数に対する完全な非剰余リスト専用です。

活用例

宿題の解答キーと表

小さな奇素数を法とする二次非剰余の完全な昇順リストを、CRT ソルバーを作らずに演習・スライド・採点キー向けに生成します。

競技と性質テストのオラクル

局所の剰余探索と本非剰余リストが、テスト範囲内のすべての奇素数について 1..p-1 の分割を成すことを検証します。

暗号コースの例題

ルジャンドル記号の符号だけでなく具体的な類が必要な Rabin 風や二次相互律の教材デモ向けに非剰余をサンプリングします。

よくある質問

p を法とする二次非剰余とは何ですか？

奇素数 p について、p で割り切れない整数 a は、x² ≡ a (mod p) を満たす整数 x が存在しないとき二次非剰余です。本ツールはそのような a を 1..p-1 のすべてについて昇順で返します。

なぜ p は奇素数でなければならないのですか？

サイズ (p−1)/2 ずつの、零でない剰余と非剰余の古典的分割は奇素数について述べられます。

対応する p の大きさは？

p は 3 から 100,000 までの整数で、かつ奇素数でなければなりません。

料金はいくらですか？

ブラウザツールは無料でローカル実行されます。無効な入力は課金されません。

法11の二次非剰余は何ですか？

2、6、7、8、10です。0以外の10個の余りのちょうど半分の5個で、どの奇素数でも同じように半分になります。

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/numth/quadratic-nonresidues-list

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

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

curl -X POST https://api.kit.forhosting.com/numth/quadratic-nonresidues-list \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"p":7}'

const res = await fetch("https://api.kit.forhosting.com/numth/quadratic-nonresidues-list", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "p": 7
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/quadratic-nonresidues-list",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "p": 7
},
)
task_id = res.json()["task_id"]

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

body := bytes.NewBufferString(`{"p":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/quadratic-nonresidues-list", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "p": 7
}

レスポンス例

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

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

料金

1リクエストあたり$0.002

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

制限

`min_p`	3
`max_p`	100000

エラー

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

技術的な注記

二次非剰余と、リストが 1..p−1 の半分になる理由

本エンドポイントが実装するのはまさにそれです。純整数演算、安定した JSON キー、文書化されたサイズ上限内での決定的な試し割り以外の外部ライブラリや確率的素数判定への依存はありません。

入力契約、制限、応答フィールド

値は 3 以上 100000 以下であり、実際に奇素数でなければなりません。例として p が 7 のとき nonresidues 配列は 3, 5, 6 で count は 3 です。奇素数の法である単一の整数フィールド p を送ってください。任意の別名 prime、modulus、mod も同じ意味で受け付けます。偶数、9 や 15 のような合成数、素数 2、非整数、欠落した入力はすべて invalid_input で検証に失敗し、課金されません。成功時のペイロードには p、1 から p 引く 1 までで p を法として平方でない各 a の昇順リスト nonresidues、その長さに等しい count、零でない二次剰余の個数 residue_count、(p 引く 1) を 2 で割った値に等しい expected_count が含まれます。正しい奇素数では count、residue_count、expected_count がこの半数の恒等式で一致し、スクリプトから API を使うときの自己検査として有用です。空オブジェクト、小数文字列、文書化された上限を超える値は、フィールド名を示す英語メッセージで拒否されます。同一の純関数が無料のブラウザツールと有料 API 経路を駆動するため、教室での実演と継続的インテグレーションのフィクスチャが同じ素数で静かに食い違うことはありません。

完全な非剰余リストが実務で現れる場面

決定的な JSON リストは手書き格子の off-by-one 誤りを除きます。本機能は純 parse エンジンであるため、モデルのドリフト、外部 API キー、保存状態はありません。API 料金は成功した項目あたり公開ベースの $0.002 です。

技術的な質問

非剰余はいくつありますか？

ちょうど (p−1)/2 個です。応答フィールド count と expected_count がこの値を報告し、residue_count も零でない剰余について一致します。

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

二次非剰余一覧 mod p

無料で実行

計算例

二次非剰余と、リストが 1..p−1 の半分になる理由

完全な非剰余リストが実務で現れる場面

活用例

宿題の解答キーと表

競技と性質テストのオラクル

暗号コースの例題

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

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

リクエスト例

レスポンス例

料金

制限

エラー

技術的な注記

二次非剰余と、リストが 1..p−1 の半分になる理由

入力契約、制限、応答フィールド

完全な非剰余リストが実務で現れる場面

技術的な質問

ありがとう