Lucas偽素数チェッカー
Lucas判定をすり抜ける奇数の合成数を見つけます。Pを1、Qを−1にすると、合成数323は判定を通過し、最小のフィボナッチ偽素数になります。判別式D、ヤコビ記号、使った添字も表示します。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- N
- 323
- P
- 1
- Q
- -1
- D
- 5
- ヤコビ記号
- -1
- Uの添字
- 324
- nを法とするU
- 0
Lucas 偽素数とは、与えられたパラメータ P と Q に対して素数が従うべき Lucas 数列 U の合同式を、なお満たしてしまう奇数の合成数です。暗号技術者、数論の学習者、素数判定の実装者は、この検査によって真の素数と、Lucas の一層だけを欺く合成数とを切り分けます。それは強い Fermat 判定と組み合わせたとき、Baillie–PSW 系が捉えようとする失敗様式そのものです。本チェッカーは n と P・Q を受け取り、判別式 D を P の二乗から四倍の Q を引いた値として構成し、D が完全平方のときは要求を拒否し、D の n に対する Jacobi 記号を計算し、二進倍化はしごで指数 n からその記号を引いた位置の U を n で割った余りを求め、合同が成り立つかと n が合成数かの両方を報告します。
Lucas 偽素数とは何か、U 判定の仕組み
Lucas 数列 U_k(P, Q) と V_k(P, Q) は、U_0 を 0、U_1 を 1、V_0 を 2、V_1 を P とし、共通の線形漸化式 X_k を P 倍の X_{k-1} から Q 倍の X_{k-2} を引いた値で定義する整数列です。特徴判別式は D で、P の二乗から四倍の Q を引いたものです。
1 より大きい奇数 n が Q と D の積と互いに素であるとき、epsilon を D の n に対する Jacobi 記号（+1 または −1）とします。互いに素条件を満たす奇数素数 p はすべて U_{p マイナス epsilon} が p を法として 0 に合同になります。
同じ合同をなお満たす正の奇数合成数 n を、パラメータ P・Q の Lucas 偽素数と呼びます。古典的な Fibonacci の場合は P が 1、Q が −1 なので U_k は Fibonacci 数列、D は 5 となり、最小の Fibonacci 偽素数は 323 です。
より強い変種（超強 Lucas、Frobenius）は V への条件を加えますが、本能力は教科書や特殊型 Lucas 偽素数の研究ノートで使われる標準の U のみ定義を実装します。
候補が単なる確率的素数なのか真の偽素数なのかを知ることで、リスク予算に対して Lucas 一層で足りるか、Baillie–PSW のように強い base-2 判定と重ねるべきかを判断できます。
よくある質問
パラメータ P・Q の Lucas 偽素数とは何ですか？
Q·D と互いに素な奇数合成数 n（D=P²−4Q）で、U_{n−(D/n)}(P,Q) ≡ 0 (mod n) を満たすものです。(D/n) は Jacobi 記号です。同じ判定に通る素数は偽素数とは呼びません。
なぜ完全平方の判別式を拒否するのですか？
D = P² − 4Q が非負の完全平方のとき Lucas 数列は退化し、素数合同は意味を失います。
323はLucas偽素数ですか？
はい。Pを1、Qを−1とするフィボナッチの場合、Dは5、ヤコビ記号は−1で、添字324のUは323で割り切れます。323は合成数なのでLucas偽素数であり、フィボナッチ偽素数の中で最小です。
13のような本当の素数を入れるとどうなりますか？
Lucas判定は通過しますが、偽素数とは表示されません。偽素数は合成数でなければならないからです。合同式が成り立つかどうかと、合成数かどうかを別々に示します。
Lucas判定だけで素数だと言い切れますか？
いいえ。Lucas判定を1回だけなら通過する合成数があるため、Baillie–PSWでは底2の強いフェルマー判定と組み合わせます。この判定で、候補がそうした合成数かどうかを確かめられます。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/numth/lucas-pseudoprime-check \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":"323","P":"1","Q":"-1"}'const res = await fetch("https://api.kit.forhosting.com/numth/lucas-pseudoprime-check", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": "323",
"P": "1",
"Q": "-1"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/lucas-pseudoprime-check",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": "323",
"P": "1",
"Q": "-1"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/lucas-pseudoprime-check", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":"323","P":"1","Q":"-1"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":"323","P":"1","Q":"-1"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/lucas-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": "323",
"P": "1",
"Q": "-1"
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.lucas_pseudoprime_check",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
Lucas 偽素数とは何か、U 判定の仕組み
D が 0 でない完全平方のとき、Binet 型の閉形式は単なる等比数列に退化し、素数判定に有用な算術的性質を失うため、本エンドポイントはそのようなパラメータを invalid_input で拒否し、意味のない 0 は返しません。
入力契約、応答フィールド、エラー挙動
n は少なくとも 3 の奇数候補、P は第 1 の Lucas パラメータ、Q は第 2 です。解析後、ハンドラは D を P の二乗から四倍の Q を引いた値として作り、D が 0 を含む非負の完全平方なら数列が退化するため例外を投げます。同じパラメータの素数 13 は Lucas 判定に通りますが偽素数とはラベルされません。必須の整数フィールド 3 つを持つ JSON 本体を POST してください。各フィールドは JSON 数値または十進整数文字列で渡せます。整数でない値、欠落フィールド、偶数の n、3 未満の n は問題を明示して invalid_input になります。成功時、本体は n・P・Q・D を十進文字列で返し、jacobi は D の n に対する Jacobi 記号を −1・0・1 の数として、u_index は記号が非零のとき n から jacobi を引いた値、u_mod_n はその指数での U を n で割った余り、gcd_ok は n が Q と D の積と互いに素なら真、passes_lucas_test は古典条件で U 合同が成り立つときのみ真、is_prime は対応範囲での決定的 Miller–Rabin 判定、is_lucas_pseudoprime は n が合成で gcd_ok が真、Jacobi が非零、かつ合同がなお成り立つときのみ真です。method フィールドは常に文字列 lucas_u_sequence で、クライアントがログにアルゴリズムを固定できます。例：n が 323、P が 1、Q が −1 なら D は 5、jacobi は −1、u_index は 324、u_mod_n は 0、is_prime は偽、is_lucas_pseudoprime は真です。検証失敗は課金されず、成功した呼び出しは API 経路で公開の基本価格 $0.002 です。
Lucas 偽素数 API が活きる場面
教室や競技プラットフォームには、学習者が 64 ビット整数を溢れさせる合同漸化コードを手書きしなくても、Fibonacci および一般の Lucas 偽素数を正しく付ける決定的オラクルが必要です。lucas 偽素数チェッカーで検索上位を狙うコンテンツサイトは、同じ純モジュール上で無料ブラウザ経路と有料自動化が一致するライブツールを得ます。暗号教材は、passes_lucas_test が真で is_prime が偽の合成数を示し、単一の代数的判定が素数証明でないことを説明できます。特殊型の新しい Lucas 偽素数を探すためにパラメータ族を走査する研究ノートは、D・Jacobi・指数・剰余という中間状態を返す小さな parse API の恩恵を受け、二次相互律を再実装せずにフィルタと作図ができます。実装は parse の tier A 純関数なので、成功呼び出しは毎回 $0.002 で、モデルトークンも外向きネットワークもありません。
連携の活用例
Fibonacci・Lucas 偽素数の教室演習
学習者に P=1, Q=−1（または他のパラメータ）で n を提出させ、教科書の一覧（例：323）に対して is_lucas_pseudoprime を確認させます。
素数判定ライブラリの回帰テスト
既知の Lucas 偽素数と素数を CI に固定し、モジュラな U_k はしごが古典合同からずれないようにします。
研究用パラメータ掃引
P と Q の族を走査し、なお U_{n−ε} ≡ 0 (mod n) を満たす合成数 n を探します。応答の D・jacobi・u_mod_n を利用できます。
技術的な質問
323 は Lucas 偽素数ですか？
Fibonacci パラメータ P=1, Q=−1（D=5）でははい。合成数（17×19）でありながら U_{324} ≡ 0 (mod 323) なので is_lucas_pseudoprime は真です。
真の素数は Lucas 偽素数に数えますか？
いいえ。U 合同を満たす真の素数は passes_lucas_test と is_prime を真にしますが、定義により is_lucas_pseudoprime は偽のままです。
Lucas 偽素数チェッカーの料金は？
ブラウザツールは無料です。API 要求は前払い KIT 残高から成功呼び出しごとに $0.002 です。無効入力は課金されません。