ForHosting KIT · 開発者向けツール

リュカ素数判定

Q: 成功結果は素数の証明になりますか？

はい。完全な因数分解が正しく、リュカの全条件を満たした場合、その結果は指定された n に対する決定的な素数証明です。

Q: なぜ底を指定する必要がありますか？

底は証明書に含まれる証人です。明示的に指定することで、原始根を無制限に探索せず、限定的かつ再現可能な検証を行えます。

Q: 底が条件を満たさない場合はどうなりますか？

その底は有効な証人ではありません。候補が合成数の場合と、別の適切な証人を持つ素数の場合があり、この失敗だけでは判別できません。

Q: 整数を文字列で入力するのはなぜですか？

10 進文字列なら、JavaScript の安全整数範囲を超える整数でも精度を失いません。同じ理由で出力にも文字列を使用します。

Q: 因数分解はどのように検証しますか？

記載された各因数を決定的に素数判定し、重複を拒否したうえで、すべての素数べきの積が n − 1 と正確に一致することを確認します。

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

API は 1 リクエスト当たり $0.002 です。ブラウザー版でも同じ純粋な計算を使用します。

このリュカ素数判定チェッカーは、簡潔な数学的証明書を再現可能な素数判定結果に変換します。奇数 n、候補となるリュカ証人、および n − 1 の完全な素因数分解をご指定ください。因数分解そのものを検証し、必要なモジュラべき乗と最大公約数を計算したうえで、リュカの定理の全条件が成立した場合に限って n を素数と証明します。10 進整数を文字列で扱うため、JavaScript の通常の安全整数範囲を超える値も正確に保持します。

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

無料で実行 API仕様を見る

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

完全な証明書をご用意ください

まず、証明する奇数を決め、n − 1 を完全に素因数分解してください。n と各素因数は正規形の 10 進文字列で入力します。文字列を使うことで、64 ビット上限まで値を正確に維持できます。各素因数は正の指数とともに一度だけ記載してください。たとえば n = 29 では、n − 1 = 28 = 2 の 2 乗 × 7 ですから、一覧には素因数 2 と指数 2、素因数 7 と指数 1 を指定します。さらに 1 < a < n を満たす底 a が必要です。この底が候補となるリュカ証人です。本チェッカーは証人を探索せず、明示的な入力を求めます。証明書の検証は高速で処理量が限定され、常に再現できますが、原始根の探索時間は入力によって変わるためです。証人がまだない場合は、別の原始根ツールで小さな底を試してから、得られた証明書を送信してください。空白、符号、先頭のゼロ、浮動小数点表記、重複した素数、合成数の因数、欠落した因数は自動修正せず拒否します。そのため、監査記録や自動処理にも適した厳密な証明書になります。

リュカの 2 条件をご確認ください

最初の計算では、a の n − 1 乗が n を法として 1 と合同であることを確認します。これはよく知られたフェルマー条件ですが、擬素数も通過し得るため、単独では素数を証明できません。決定的な第 2 段階では、n − 1 を割り切る相異なる各素数 q を用います。q ごとに、a の (n − 1) / q 乗を n を法として計算し、そこから 1 を引いた値と n の最大公約数が 1 であることを確認します。すべてに合格すれば、n を法とする a の乗法位数が正確に n − 1 であると分かります。n が素数でなければ、n を法とする元はこの位数を持てません。これがリュカの定理の核心です。返される検査記録には、相異なる q ごとの剰余と最大公約数が示され、指数も検証済み因数分解の一部として残ります。モジュラべき乗には、正確な BigInt 演算による繰り返し二乗法を使用します。したがって、浮動小数点の丸め、無作為な底、ネットワークサービス、確率的な信頼度には一切依存しません。

失敗と成功結果の読み方

成功応答は、単なる確率的素数という表示ではなく、素数証明書の検証結果です。n、認められた証人、フェルマー剰余を再掲し、n − 1 の相異なる素因数ごとに成功した最大公約数検査を列挙します。別のシステムで証明を再現する場合は、元の入力と応答を一緒に保存してください。失敗理由は意図的に具体化しています。因数の各べきの積が n − 1 と正確に一致しなければ、因数分解が不完全または誤っています。記載した因数が合成数の場合や、同じ素数を 2 回記載した場合は、積だけが一致しても不正な因数分解です。いずれかのモジュラ条件に失敗した場合、指定した底はリュカ証人ではありません。ただし、その失敗だけでは、n が合成数なのか、素数に不適切な底を組み合わせたのかを区別できません。素数と予想される数学的根拠がある場合は、正当な別の証人をお試しください。入力は 3 以上 2^64 − 1 以下の奇数に限定されるため、証明書の評価前に、記載された素因数を決定的に検証できます。API の料金は 1 リクエスト当たり $0.002 です。

活用例

生成した素数を検証

候補と生成時に得た因数分解を確認してから、その素数を別の厳密計算に使用できます。

証明書を再現

論文、演習問題、保存済み計算にあるリュカ証人を、明示された中間剰余とともに検証できます。

数論データを選別

信頼できるデータ集合へ素数候補を登録する前に、不完全な因数分解や無効な証人を排除できます。

よくある質問

成功結果は素数の証明になりますか？

はい。完全な因数分解が正しく、リュカの全条件を満たした場合、その結果は指定された n に対する決定的な素数証明です。

なぜ底を指定する必要がありますか？

底は証明書に含まれる証人です。明示的に指定することで、原始根を無制限に探索せず、限定的かつ再現可能な検証を行えます。

底が条件を満たさない場合はどうなりますか？

その底は有効な証人ではありません。候補が合成数の場合と、別の適切な証人を持つ素数の場合があり、この失敗だけでは判別できません。

整数を文字列で入力するのはなぜですか？

10 進文字列なら、JavaScript の安全整数範囲を超える整数でも精度を失いません。同じ理由で出力にも文字列を使用します。

因数分解はどのように検証しますか？

記載された各因数を決定的に素数判定し、重複を拒否したうえで、すべての素数べきの積が n − 1 と正確に一致することを確認します。

料金はいくらですか？

API は 1 リクエスト当たり $0.002 です。ブラウザー版でも同じ純粋な計算を使用します。

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/numth/lucas-primality-test

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

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

curl -X POST https://api.kit.forhosting.com/numth/lucas-primality-test \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":"29","base":"2","factors":[{"prime":"2","exponent":2},{"prime":"7","exponent":1}]}'

const res = await fetch("https://api.kit.forhosting.com/numth/lucas-primality-test", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "n": "29",
    "base": "2",
    "factors": [
      {
        "prime": "2",
        "exponent": 2
      },
      {
        "prime": "7",
        "exponent": 1
      }
    ]
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/lucas-primality-test",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "n": "29",
    "base": "2",
    "factors": [
        {
            "prime": "2",
            "exponent": 2
        },
        {
            "prime": "7",
            "exponent": 1
        }
    ]
},
)
task_id = res.json()["task_id"]

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

body := bytes.NewBufferString(`{"n":"29","base":"2","factors":[{"prime":"2","exponent":2},{"prime":"7","exponent":1}]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/lucas-primality-test", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "n": "29",
  "base": "2",
  "factors": [
    {
      "prime": "2",
      "exponent": 2
    },
    {
      "prime": "7",
      "exponent": 1
    }
  ]
}

レスポンス例

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

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

料金

1リクエストあたり$0.002

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

制限

`max_bits`	64
`max_factors`	64

エラー

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

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