ForHosting KIT · 開発者向けツール

任意の底に対応したフェルマー擬素数チェッカー

Q: n が底 a に対するフェルマー擬素数となる条件は何ですか？

n が合成数であり、指定した底について a^(n-1) が n を法として 1 と合同になる必要があります。

Q: n が素数だとエラーになるのはなぜですか？

素数は通常フェルマーの合同式を満たしますが、擬素数という用語は合成数だけを対象とするためです。

Q: 真という結果は n が素数だと証明しますか？

いいえ。n が合成数であることはすでに確認済みです。真は、その合成数が特定の底で判定を通過したことを示します。

Q: n と a を文字列で入力する理由は何ですか？

10進文字列なら、通常のJavaScript数値の安全範囲を超えても、APIとブラウザーの間ですべての桁を保持できます。

Q: 料金はいくらですか？

APIは確認する1組につき $0.002 です。ブラウザーでは同じ計算を端末内で実行します。

フェルマー擬素数チェッカーは、合成数 n と底 a を受け取り、a の n−1 乗を n で割った余りを正確に計算し、その余りが 1 かどうかを示します。通過した合成数は、選んだ底に対するフェルマー擬素数です。つまり、実際には素数でないにもかかわらず、この特定の判定では素数のように振る舞います。結果を確認しやすいよう、最大公約数も併せて表示します。

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

無料で実行 API仕様を見る

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

通過という結果が実際に表すこと

フェルマーの小定理によると、n が素数で、a が n で割り切れない場合、a の n−1 乗を n で割った余りは 1 になります。しかし、その逆は常に正しいわけではありません。特定の底について同じ余りを返す合成数もあり、そのような数を、その底に対するフェルマー擬素数と呼びます。このチェッカーでは、n が合成数であることを必須条件とし、最初にその条件を検査してから合同式を厳密に評価します。passes_fermat_test と is_fermat_pseudoprime が真なら、入力した合成数が、その特定の底でフェルマー判定を通過したことを意味します。n が素数、素数らしい数、またはすべての底に対する擬素数であるという意味ではありません。底は判定内容の一部なので、結果とともに記録してください。返される余りが直接の算術的根拠となり、1 なら通過、それ以外なら不通過です。最大公約数からは、底と n が互いに素か、すでに因数関係が見えているかも確認できます。

計算の正確さを保つ仕組み

入力はどちらも10進文字列として扱うため、JavaScriptで安全に表現できる整数範囲を超えても、計算前に丸められることがありません。対応範囲の上限は符号なし64ビット整数の最大値であり、素数判定に明確で検証可能な境界を設けています。フェルマー判定の前には、この全範囲で十分な証人集合を使った決定的Miller–Rabin法を実行します。素数が検出された場合は入力エラーになります。素数は定理を満たしますが、定義上、擬素数にはなれないためです。有効な合成数では、巨大な a^(n-1) を直接作らず、繰り返し二乗法で剰余累乗を計算します。乗算のたびに n を法として簡約するため、中間値はBigIntで正確かつ限定された範囲に保たれます。gcd(a,n) はユークリッドの互除法で別に求めます。底には 2 <= a <= n - 2 という条件があります。乱数、時刻、ネットワーク、浮動小数点計算は使わないため、同じ入力からは必ず同じ結果が得られます。

学習や検証作業での使い方

代表的な例は n = 341、底 a = 2 です。341 は合成数ですが、2^340 は 341 を法として 1 と合同なので、判定を通過し、底2に対するフェルマー擬素数になります。底を変えると同じ合成数でも不通過になる場合があるため、1回のフェルマー判定を一般的な素数証明として使用することはできません。授業では、構造化された出力を使って定義と計算済みの余りを直接結び付けられます。テストスイートでは、数学ライブラリや実行環境固有の数値変換に依存せず、既知の擬素数と非擬素数の検査例を保存できます。調査では、n を固定したまま複数の有効な底を比較すると、証人の選択が結果に与える影響を確認できます。真という結果は、フェルマー判定の限界を示すものとして扱い、暗号やセキュリティ上重要なコードで素数と認める根拠にはしないでください。APIは1組の確認につき $0.002 で、ブラウザー版では同じ決定的計算を端末内で実行します。

活用例

代表的な擬素数を確認

341 のような既知の合成数が底2でフェルマー合同式を満たすことを確かめ、正確な余りを確認できます。

整数論の演習問題を作成

指定された合成数が特定の底に対する擬素数かを問う問題について、解答を検算できます。

算術実装をテスト

決定的な構造化結果を、剰余累乗や学習用素数判定コードの参照テストケースとして利用できます。

よくある質問

n が底 a に対するフェルマー擬素数となる条件は何ですか？

n が合成数であり、指定した底について a^(n-1) が n を法として 1 と合同になる必要があります。

n が素数だとエラーになるのはなぜですか？

素数は通常フェルマーの合同式を満たしますが、擬素数という用語は合成数だけを対象とするためです。

真という結果は n が素数だと証明しますか？

いいえ。n が合成数であることはすでに確認済みです。真は、その合成数が特定の底で判定を通過したことを示します。

n と a を文字列で入力する理由は何ですか？

10進文字列なら、通常のJavaScript数値の安全範囲を超えても、APIとブラウザーの間ですべての桁を保持できます。

料金はいくらですか？

APIは確認する1組につき $0.002 です。ブラウザーでは同じ計算を端末内で実行します。

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/numth/fermat-pseudoprime-check

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

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

curl -X POST https://api.kit.forhosting.com/numth/fermat-pseudoprime-check \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":"341","a":"2"}'

const res = await fetch("https://api.kit.forhosting.com/numth/fermat-pseudoprime-check", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "n": "341",
    "a": "2"
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/fermat-pseudoprime-check",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "n": "341",
    "a": "2"
},
)
task_id = res.json()["task_id"]

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

body := bytes.NewBufferString(`{"n":"341","a":"2"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/fermat-pseudoprime-check", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "n": "341",
  "a": "2"
}

レスポンス例

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

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

料金

1リクエストあたり$0.002

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

制限

max_digits 20

エラー

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

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