ForHosting KIT · 数学

ポラードのp−1法

Q: 完全な素因数分解を返しますか？

いいえ。 一つの非自明な約数と余因子n/factor（小さい方を先）だけです。すべての素数べきが必要なら各片を素因数分解ツールでさらに分解してください。

素因数pのp − 1が滑らかなとき、合成数の因数を見つけます。1003を上限16で調べると17と59に分かれます。17 − 1が16だからです。何も出なければ上限を上げてください。ブラウザで無料で使えます。

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

無料で実行 API仕様を見る

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

計算例

入力した場合

N: 1003
境界値: 16

結果

因数: 17
余因子: 59
底: 2

ポラードのpマイナス1法は、合成数の法nに対し、少なくとも一つの素因数pについてpマイナス1が選んだ上限Bに関して滑らかであるとき、すなわちpマイナス1の素因数分解に現れるどの素数べきもB以下であるときに、非自明な約数を求める古典的な整数分解アルゴリズムです。初等整数論の学生、CTF競技者、暗号を学ぶ方は、RSAの法が滑らかなトーシェントを持つ素数を避けるべき理由を学ぶ場面でこのアルゴリズムに出会います。本機能は決定的な第1段階のポラードp−1探索を実行します。Bまでの素数べきの積を組み立て、小さな底をその指数でnを法としてべき乗し、そのべきマイナス1とnの最大公約数が真の約数であるときにそれを返します。

滑らかなp−1からポラードp−1が約数を見つける仕組み

合成整数nと正の滑らかさ上限Bを固定してください。ポラードの着眼点は単純です。pがnの素因数であり、pマイナス1を割るどの素数べきもB以下であれば、1からBまでの整数の最小公倍数はpマイナス1の倍数になります。

フェルマーの小定理により、pと互いに素な任意の底aはaのpマイナス1乗がpを法として1と合同であり、したがってその大きな最小公倍数へのべき乗もpを法として1と合同です。同じべきをnを法として計算し、結果から1を引いた値とnの最大公約数をとると、しばしばpまたは別の非自明な約数が得られます。

実装では最小公倍数を明示的には組み立てず、B以下の素数を篩い、各素数qについてBを超えない最大のqのべきへ走行中の累積値をnを法として上げます。各素数べきの段階のあと、累積値マイナス1とnのgcdを評価します。途中で非自明なgcdが得られれば直ちに返します。

gcdがnそのものに潰れた場合は、より細かい指数の回復走査で単一の素因数を切り分けることを試み、その底を諦める前に尽くします。底2の不運な位数が、本来B-滑らかな約数を隠さないよう、いくつかの小さな底を試します。本手法は完全な素因数分解アルゴリズムではなく、一つの非自明な約数と対応する余因子を返します。

完全な素因数分解が必要な呼び出し側は、各合成片を素因数分解ツールに渡すか、Bを上げて再実行できます。成功が保証されるのはp−1が滑らかな設定に限られ、pマイナス1の大きな素因数はより大きなBか、楕円曲線法や二次篩などの別アルゴリズムを要求します。

この分解法が役立つ場面

暗号の授業では、RSAやDiffie–Hellmanのパラメータ生成で滑らかな直前値を持つ素数が危険であることを示すためにポラードp−1を用います。nとBを受け付けるライブツールがあれば、講師は手書きのモジュラべき乗なしに授業で分割を示せます。

CTFや宿題プラットフォームには、1003と上限16のような古典的半素数に対して文書化された約数を返すか、小さすぎる上限を拒否して採点者が正しい約数と正しい失敗理由の両方を付けられる、決定的オラクルが必要です。旧来の鍵生成を監査するセキュリティ技術者は、候補法が本番に入る前にp−1が滑らかな約数を篩い分けられます。

nを桁制限内に保ち、nを割るある素数pについてpマイナス1の最大素因数を覆う十分なBを選べば、教育・CTFのwrite-up・軽量監査向けに再現可能な約数が、本格的な計算機代数スタックなしで得られます。

活用例

候補法の健全性確認

完全な素因数分解スイートを導入せずに、RSAやDiffie–Hellmanの候補法をデプロイ前にp−1が滑らかな約数について調べます。

よくある質問

ポラードのp−1素因数探索法とは何ですか？

底の大きな滑らかなべきをnを法として計算しgcd(a^M − 1, n)を返す第1段階アルゴリズムです。選んだ上限Bに対してp−1がB-滑らかなとき因子pを見つけます。

約数が見つからないのはどんなときですか？

nが素数のとき、nのどの素因数pもp−1にBより大きい素因数を持つとき、または回復が真の約数を切り分けられないときです。

完全な素因数分解を返しますか？

いいえ。一つの非自明な約数と余因子n/factor（小さい方を先）だけです。すべての素数べきが必要なら各片を素因数分解ツールでさらに分解してください。

ポラードp−1の利用料金はいくらですか？

ブラウザツールは無料です。無効入力や失敗した上限は課金されません。

上限はどう選べばよいですか？

小さな値から始め、因数が出なければ上げてください。上限は、数の少なくともひとつの素因数pについて、p − 1のすべての素数べきを含む必要があります。2から50,000までの整数を指定できます。

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/numth/pollard-p-minus-one

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

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

curl -X POST https://api.kit.forhosting.com/numth/pollard-p-minus-one \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":"1003","bound":16}'

const res = await fetch("https://api.kit.forhosting.com/numth/pollard-p-minus-one", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "n": "1003",
    "bound": 16
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/pollard-p-minus-one",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "n": "1003",
    "bound": 16
},
)
task_id = res.json()["task_id"]

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

body := bytes.NewBufferString(`{"n":"1003","bound":16}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/pollard-p-minus-one", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "n": "1003",
  "bound": 16
}

レスポンス例

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

技術的な注記

上限が厳しすぎる場合、nが素数の場合、あるいはどの約数も手法に抵抗する場合、架空の約数を作らずinvalid_inputで失敗します。無料のブラウザ経路と有料APIは同じ純粋なBigIntモジュールを共有するため、宿題の照合と自動化が食い違うことはありません。

入力契約・応答形・失敗モード

例：nが1003、boundが16のとき、17マイナス1が16で16-滑らかなのでfactorは17、cofactorは59です。nが偶数なら第1段階の完全探索なしに因子2を直ちに返します。因子1やnでの静かな成功は、200応答を真の分割とみなす自動化を壊すため、この失敗は意図した製品設計です。必須フィールド二つを持つJSONオブジェクトをPOSTしてください。フィールドnは分解対象の整数で、安全なJavaScript整数、またはカンマ・空白・指数表記のない素の十進文字列であり、十進桁は少なくとも2・最大18です。フィールドboundは滑らかさ上限Bで、2から50000までの整数です。利便のため別名B、b、smoothness_bound、smoothnessを受け付けます。成功時、本体はnを十進文字列、boundを整数としてエコーし、factorとcofactorを小さい方を先にした十進文字列で報告し、約数を生んだ底と、固定文字列pollard_p_minus_oneに設定されたmethodを返します。欠落フィールド、非整数、2未満のn、公開範囲外のbound、18桁を超えるnはinvalid_inputで失敗し課金されません。第1段階がどの底でも真の約数を得られない場合——例えばnが素数、またはどの素因数pもpマイナス1にBより大きい素因数を持つ——ハンドラもinvalid_inputで失敗し、ポラードp−1が上限内に非自明な約数を見つけられなかった旨を伝え、Bを上げるか別のnを試すよう促します。

p−1約数APIが役立つ場面

一般の素因数分解ルーチンを既に持つノートブック著者でも、完全な素因数一覧ではなく手法そのものが題材なら、明示的なp−1エンドポイントが有用です。実装は純粋なparseのティアAのため、成功した各呼び出しはモデルトークンも外向きネットワークもなく公開の基本価格$0.002で、検証失敗は残高を消費しません。

連携の活用例

滑らかなp−1の授業デモ

半素数の一つの素因数についてp−1を覆う上限Bが非自明な分割を生む様子を、n=1003・B=16などの古典例で示します。

CTF・宿題の自動採点

Bが十分なときは約数を返し、上限が厳しすぎるときはinvalid_inputを返す決定的オラクルで、ポラードp−1の演習を採点します。

技術的な質問

APIが要求する入力は何ですか？

フィールドn（整数≥2、≤18桁）とフィールドbound（滑らかさBは2〜50000）です。別名にn向けnumber/value、bound向けB/smoothness_boundがあります。

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