ForHosting KIT · 開発者向けツール

プロスの定理による素数判定と証人の検証

Q: 証人が不成立なら合成数だと証明できますか？

いいえ。通常は未確定です。証人から自明でない共通因数が見つかった場合だけ合成数と判定します。

Q: k と証人を文字列で入力するのはなぜですか？

10進文字列なら、JavaScript の安全な数値範囲を超える整数でも丸めずに保持できるためです。

Q: 合格した結果は確率的な判定ですか？

いいえ。プロス条件を確認した後の所定の合同式は、素数であることの証明になります。

Q: 証人は自動で選ばれますか？

いいえ。証人はお客様が指定し、この機能はその値を決定的に検査します。

プロス素数判定は、k × 2^n + 1 と表される数に、ご指定の証人を使ってプロスの定理を適用します。最初に k が正の奇数、n が正の整数、かつ k が 2^n より小さいことを確認します。次に必要なモジュラー累乗を整数演算で正確に求めます。合同条件が成立すればプロス数が素数であることの証明になり、成立しない場合は、因数が見つからない限り未確定として返します。

● Beta無料・ブラウザ内で実行

無料で実行 API仕様を見る

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

正しいプロス数と証人を入力します

プロス数は厳密に N = k × 2^n + 1 の形を持ち、k は正の奇数、n は正の整数で、k は 2^n よりも小さくなければなりません。これらの条件は一つも省略できません。この計算機では、大きな値が浮動小数点の丸めで変化しないように、k と証人を10進文字列として受け取ります。n には 1 から 10,000 までの整数をご入力ください。N を別に入力させず、定義するパラメータから計算するため、申告した数と k、n の不一致も起こりません。また、証人が厳密に 1 より大きく N より小さいことも確認します。k が偶数、値が正でない、または k が 2^n 以上の場合は、前提を満たさない数に定理を適用せず、プロス形式ではない入力としてエラーにします。返される数、指数、証人、剰余は、必要に応じて10進文字列になります。そのため、計算過程を監査し、任意精度演算に対応する別のツールへ正確なままコピーできます。

合同式が証明する内容を理解します

有効なプロス数 N に対し、プロスの定理は、a^((N−1)/2) が N を法として −1 と合同になる整数 a が存在すれば N は素数である、と述べています。入力した証人が a に相当します。計算機は巨大な通常の累乗を先に生成せず、繰り返し二乗法でモジュラー累乗を評価します。出力の `residue` は最小の非負剰余です。これが −1 のモジュラー表現である N−1 と等しい場合に限り、`passes_test` が true になります。そのとき `prime_proven` も true となり、判定は `prime` です。検証済みのプロス条件の下では、これは確率的な「おそらく素数」という推測ではなく、決定的な証明です。結果には正確な指数 (N−1)/2 も含まれるため、合同式を別の環境で独立して再現できます。アルゴリズムは整数演算だけを使い、証人を無作為に選んだり、表や外部サービスへ問い合わせたりしません。同じ入力には常に同じ結果が返り、定理で使われた重要な値をすべて確認できます。

不成立の証人を正しく扱います

証人から −1 が得られなくても、それだけで対象の数が合成数だとは証明できません。その証人がプロスの定理の十分条件を満たさなかった、という意味にとどまります。そのため、剰余が異なり、証人と N が互いに素である場合、計算機は `composite` ではなく `inconclusive` を返します。その後、数学的な根拠で選んだ別の証人を試すか、別の決定的素数判定法をご利用ください。ただし有用な例外があります。合同式を解釈する前に、証人と N の最大公約数を計算します。その値が真の因数なら、結果は確定的に `composite` となり、その因数も返します。この区別により、一方向の定理を誤って双方向の判定として扱うことを防げます。自動処理でも、`prime` は証明として受理し、因数を伴う `composite` は棄却し、`inconclusive` は失敗と決めつけず別の検査へ送る、という安全な分岐が可能です。

活用例

探索で得た候補を検証

生成した k と n の組を選択した証人で調べ、証明済み素数として記録する前に確認できます。

プロスの定理を学習

正確な指数とモジュラー剰余を示し、証明と未確定の証人との違いを説明できます。

決定的な工程検査を追加

浮動小数点を使わずにプロス条件を検証し、素数、合成数、未確定の結果を適切に振り分けます。

よくある質問

API リクエストの料金はいくらですか？

API リクエストごとに $0.002 です。このページのブラウザでも無料で計算できます。

プロス数になる条件は何ですか？

k × 2^n + 1 に等しく、k が正の奇数、n が正で、k < 2^n を満たす必要があります。

証人が不成立なら合成数だと証明できますか？

いいえ。通常は未確定です。証人から自明でない共通因数が見つかった場合だけ合成数と判定します。

k と証人を文字列で入力するのはなぜですか？

10進文字列なら、JavaScript の安全な数値範囲を超える整数でも丸めずに保持できるためです。

合格した結果は確率的な判定ですか？

いいえ。プロス条件を確認した後の所定の合同式は、素数であることの証明になります。

証人は自動で選ばれますか？

いいえ。証人はお客様が指定し、この機能はその値を決定的に検査します。

開発者向け — APIアクセス

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

エンドポイント

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

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

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

curl -X POST https://api.kit.forhosting.com/numth/proth-test \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"k":"3","n":3,"witness":"3"}'

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

import os, requests

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

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

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

リクエスト例

{
  "k": "3",
  "n": 3,
  "witness": "3"
}

レスポンス例

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

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

料金

1リクエストあたり$0.002

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

制限

`max_n`	10000
`max_decimal_digits`	3011

エラー

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

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