ForHosting KIT · 数学

ポックリントン素数判定

Q: 因数部分が小さすぎるのはいつですか？

F² < n（分解n−1=F·RでF ≤ Rと同値）のときです。

Q: どの入力を送りますか？

必須はn（≥3）とfactors（積がFになる多重度付き素数配列）。任意でbasesに明示証人。

Q: certifiedがfalseならnは合成数ですか？

いいえ。 与えられたFとbasesの下で有効な証人が見つからなかっただけです。nはなお素数かもしれません。より多くの底、より大きなF、または別の素数判定を試してください。

Q: 証人の底は自分で選べますか？

はい。2以上の整数を、すべての素因数に共通の底ひとつか、異なる素因数ごとに順番どおりひとつずつ指定できます。指定しなければ2から200までの底を自動で探します。

n − 1の部分的な素因数分解から素数であることを証明します。31なら30の素因数2、3、5で分解済み部分が30となり、900は31以上なので、素因数ごとの証人で素数と確定します。ブラウザで無料で使えます。

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

無料で実行 API仕様を見る

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

計算例

入力した場合

N: 31
因数: 2, 3, 5

結果

N: 31
Nマイナス1: 30
F: 30
R: 1

ポックリントン–レーマー判定は、nマイナス1の部分素因数分解を厳密な素数証明書に変えます。試し割りだけや単一のフェルマー合同とは異なり、n−1のうち因数分解済み部分FがFの二乗がn以上になる程度に分かれていればよく、さらにFを割る各素数に対する短い合同の証人aが必要です。学生、暗号の指導者、数論ノートはこのポックリントン素数判定を使い、nの平方根まで篩うことなく小〜中規模の素数を証明します。候補nと積がFになる素数列を渡すと、エンジンはサイズ条件を確認し、底aを探索または検証し、因数部分が小さすぎるときは明確なエラーを返します。

ポックリントン–レーマー判定が述べること

nマイナス1をFとRの積として書き、Fはすでに分かっている素数で完全に素因数分解され、Rは残りのコファクターとします。古典的なポックリントンの定理は次を言います。

Fが十分大きくFの二乗が少なくともnであり、Fを割るすべての素数qについて、整数の底aが存在してaの(n−1)乗がnを法として1と合同であり、かつaの((n−1)/q)乗から1を引いた数とnの最大公約数が1ならば、nは素数です。直観的には、これら二つの合同条件によりaのnを法とする乗法的位数が各qの倍数になり、したがって位数はFの倍数になります。

Fがnの平方根より大きいことと合わせると、合成数nが通常の仕方で真の約数を隠せなくなります。これは単一のべき剰余だけを見るフェルマーの小定理より強く、擬素数に欺かれにくいです。またn−1の多くの素因数が既知のとき、nの完全分解やsqrt(n)までの試し割りより経済的です。

例えばnがProth数、安全素数の構成、あるいはn−1が分解しやすい演習用整数の場合です。本機能はそのチェックリストをそのまま実装します。

授業での証明、暗号デモ、自動化

数論の授業では、学習者がn−1を手で分解したあと31、61、97のような素数をポックリントン素数判定で証明し、不透明なis-primeボタンだけに頼らない練習ができます。ライブラリ作者はproperty testで、certifiedがtrueなら自前の素数判定が同じnで一致し、不十分なFは必ず「部分が小さすぎる」エラーになると断言できます。

無料ブラウザ経路は同一のsolve関数を実行します。nとfactorsは桁・個数制限内に保ち、JavaScriptの安全整数を超える値は文字列整数を優先し、certifiedを「ポックリントンが素数と証明した」権威ある真偽値として扱ってください。

n−1のごく一部しか分解できていないときは先に因数を増やすか一般的な素数判定を使い、本ランディングはポックリントン–レーマーの検索意図に専任し、SEO・例・応答形を焦点化したままにします。

活用例

宿題・試験用の素数証明書

学習者がn−1を分解し、nとFの素数を送ると、Fが十分大きいときポックリントン–レーマーの下でnが素数である証人を受け取れます。

コンテスト・LMSの自動採点

Fが小さすぎる場合や非素数の因数リストを拒否する決定論的証明書オラクルで数論の設問を採点し、静かな偽陽性を避けます。

よくある質問

ポックリントン素数判定とは何ですか？

部分素因数分解n−1=F·R（Fは完全分解、F²≥n）と、Fを割る各素数qに対する合同の証人aにより、nが素数であることを証明する判定基準です。

因数部分が小さすぎるのはいつですか？

F² < n（分解n−1=F·RでF ≤ Rと同値）のときです。

どの入力を送りますか？

必須はn（≥3）とfactors（積がFになる多重度付き素数配列）。任意でbasesに明示証人。

certifiedがfalseならnは合成数ですか？

いいえ。与えられたFとbasesの下で有効な証人が見つからなかっただけです。nはなお素数かもしれません。より多くの底、より大きなF、または別の素数判定を試してください。

証人の底は自分で選べますか？

はい。2以上の整数を、すべての素因数に共通の底ひとつか、異なる素因数ごとに順番どおりひとつずつ指定できます。指定しなければ2から200までの底を自動で探します。

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/numth/pocklington-test

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

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

curl -X POST https://api.kit.forhosting.com/numth/pocklington-test \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":31,"factors":[2,3,5]}'

const res = await fetch("https://api.kit.forhosting.com/numth/pocklington-test", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "n": 31,
    "factors": [
      2,
      3,
      5
    ]
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/pocklington-test",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "n": 31,
    "factors": [
        2,
        3,
        5
    ]
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/pocklington-test", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"n":31,"factors":[2,3,5]}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"n":31,"factors":[2,3,5]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/pocklington-test", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "n": 31,
  "factors": [
    2,
    3,
    5
  ]
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.pocklington_test",
  "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`	リクエストが多すぎます。しばらく待ってから再度お試しください。

技術的な注記

同じ純粋BigIntロジックが無料ブラウザと、成功リクエストあたり$0.002のAPI経路を支えます。

ポックリントン–レーマー判定が述べること

factorsの積がF、Rは(n−1)/F、サイズ条件F²≥nを強制し、Fの各相異なる素数qに証人aを付けます（2から自動探索、または任意のbases）。すべての素数が通ると、応答はcertifiedとis_primeをtrueにし、証人群を列挙するので、手計算や他システムで再検証できます。

入力契約、サイズエラー、証明書の読み方

factorsはn−1の因数分解済み部分Fの素数（多重度付き）です。任意のbasesは2以上の整数配列で、全素数共通の証人一つ、またはソート済み相異なる素数ごとの証人です。省略するとエンジンはaを2から200まで探索します。積Fがn−1を割り切れない場合、部分分解が一貫しないため失敗します。Fの二乗がnより真に小さい場合、「因数部分が小さすぎる」という意図的なハードエラーになります。完全なポックリントン通過は素数証明であり、証人探索の失敗だけでは合成であるとは言えません。POSTで必須整数n（3以上）と必須配列factorsを含むJSON本体を送ります。例：nが31、factorsが2,3,5（30=2·3·5）ならF=30、R=1でFの二乗は31を大きく上回ります。各要素は素数でなければならず、合成数はinvalid_inputで失敗し、偽の因数リストが証明書を装えません。成功時はn、n_minus_1、F、R、F_squared、floor_sqrt_n、相異なる素数、多重集合、素数ごとのa・べき剰余・gcd確認・okフラグを持つwitnesses配列を返します。booleanのcertifiedは全素数に有効な証人がいるときだけtrueで、is_primeはここではcertifiedを写します。料金はitem単位の成功呼び出しあたり定額$0.002で、検証失敗は課金されません。大きな整数は公開桁数制限内の十進文字列で送り、JSONの精度落ちを避けてください。

授業での証明、暗号デモ、自動化

コンテスト準備ツールは滑らかなn−1の候補を生成し、既知の因数をこのエンドポイントに渡し、返った証人を解答キー横の短い証明オブジェクトとして保存します。実装は純粋parseのtier Aなので、成功呼び出しは公開の$0.002のみで、モデルトークンも外向き通信もありません。

連携の活用例

暗号・CASノートでの固定検証

固定素数に対するポックリントンのgolden証明書を単体テストに固定し、各言語でmodPowとgcd確認を再実装しません。

技術的な質問

ポックリントン素数判定の料金は？

ブラウザ版は無料です。APIはプリペイドKIT残高から成功呼び出しあたり$0.002で、無効入力は課金されません。

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

ポックリントン素数判定

無料で実行

計算例

ポックリントン–レーマー判定が述べること

授業での証明、暗号デモ、自動化

活用例

宿題・試験用の素数証明書

コンテスト・LMSの自動採点

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

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

リクエスト例

レスポンス例

料金

エラー

技術的な注記

ポックリントン–レーマー判定が述べること

入力契約、サイズエラー、証明書の読み方

授業での証明、暗号デモ、自動化

連携の活用例

暗号・CASノートでの固定検証

技術的な質問

ありがとう