Lucas-Pseudoprim-Prüfer
Finden Sie die ungeraden zusammengesetzten Zahlen, die den Lucas-Test täuschen: Mit P gleich 1 und Q gleich −1 besteht die zusammengesetzte 323 den Test und ist die kleinste Fibonacci-Pseudoprimzahl. Angezeigt werden auch D, das Jacobi-Symbol und der geprüfte Index. Kostenlos in Ihrem Browser.
- Kostenlos
- Läuft in Ihrem Browser
- Ohne Anmeldung
- Ihre Daten bleiben auf Ihrem Gerät
Im Browser ausführen – kostenlos
Rechenbeispiel
- N
- 323
- P
- 1
- Q
- -1
- D
- 5
- Jacobi-Symbol
- -1
- Index von U
- 324
- U modulo n
- 0
Eine Lucas-Pseudoprimzahl ist eine ungerade zusammengesetzte ganze Zahl, die dennoch dieselbe Kongruenz der Lucas-U-Folge erfüllt, der jede Primzahl für gegebene Parameter P und Q genügen muss. Kryptografen, Studierende der Zahlentheorie und Entwickler von Primzahltests nutzen diese Prüfung, um echte Primzahlen von Zusammengesetzten zu trennen, die eine einzelne Lucas-Schicht täuschen — genau der Fehlermodus, den die Familie Baillie–PSW zusammen mit einem starken Fermat-Test abfangen soll. Dieser Prüfer nimmt n zusammen mit P und Q entgegen, bildet die Diskriminante D gleich P zum Quadrat minus vier Q, lehnt die Anfrage ab, wenn D ein perfektes Quadrat ist, berechnet das Jacobi-Symbol von D über n, wertet U am Index n minus dieses Symbol modulo n mit einer binären Verdopplungsleiter aus und meldet sowohl, ob die Kongruenz gilt, als auch, ob n zusammengesetzt ist.
Was eine Lucas-Pseudoprimzahl ist und wie der U-Test funktioniert
Die Lucas-Folgen U_k(P, Q) und V_k(P, Q) sind die ganzzahligen Rekursionen mit U_0 gleich null, U_1 gleich eins, V_0 gleich zwei, V_1 gleich P und dem gemeinsamen linearen Schritt X_k gleich P mal X_{k-1} minus Q mal X_{k-2}. Ihre charakteristische Diskriminante ist D gleich P zum Quadrat minus vier Q. Für eine ungerade ganze Zahl n größer als eins, die teilerfremd zu Q mal D ist, sei epsilon das Jacobi-Symbol von D über n, also plus eins oder minus eins.
Jede ungerade Primzahl p, die die Teilerfremdheit erfüllt, gehorcht U_{p minus epsilon} kongruent null modulo p. Eine positive ungerade zusammengesetzte Zahl n, die dieselbe Kongruenz noch erfüllt, heißt Lucas-Pseudoprimzahl mit Parametern P und Q. Der klassische Fibonacci-Fall nutzt P gleich eins und Q gleich minus eins, sodass U_k die Fibonacci-Folge ist und D fünf beträgt; die kleinste Fibonacci-Pseudoprimzahl ist dreihundertdreiundzwanzig.
Stärkere Varianten (extra-starke Lucas, Frobenius) ergänzen Bedingungen an V, doch diese Fähigkeit implementiert die standardmäßige reine U-Definition aus Lehrbüchern und Forschungsnotizen zu Lucas-Pseudoprimzahlen spezieller Typen. Zu wissen, ob ein Kandidat nur eine wahrscheinliche Primzahl oder eine echte Pseudoprimzahl ist, hilft Ihnen zu entscheiden, ob eine einzelne Lucas-Schicht für Ihr Risikobudget ausreicht oder ob Sie sie mit einem starken Basis-zwei-Test wie bei Baillie–PSW stapeln müssen.
Häufige Fragen
Was ist eine Lucas-Pseudoprimzahl mit Parametern P und Q?
Eine ungerade zusammengesetzte Zahl n, teilerfremd zu Q·D (D=P²−4Q), sodass U_{n−(D/n)}(P,Q) ≡ 0 (mod n), wobei (D/n) das Jacobi-Symbol ist. Primzahlen, die denselben Test bestehen, heißen nicht Pseudoprimzahlen.
Warum lehnt der Prüfer eine perfekt-quadratische Diskriminante ab?
Wenn D = P² − 4Q ein nichtnegatives perfektes Quadrat ist, entarten die Lucas-Folgen und die Primheitskongruenz ist nicht mehr sinnvoll.
Ist 323 eine Lucas-Pseudoprimzahl?
Ja. Mit P gleich 1 und Q gleich −1, dem Fibonacci-Fall, ist D gleich 5, das Jacobi-Symbol −1, und U am Index 324 ist durch 323 teilbar. Da 323 zusammengesetzt ist, ist sie eine Lucas-Pseudoprimzahl, die kleinste Fibonacci-Pseudoprimzahl.
Was passiert, wenn ich eine echte Primzahl wie 13 prüfe?
Sie besteht den Lucas-Test, wird aber nicht als Pseudoprimzahl markiert, denn eine Pseudoprimzahl muss zusammengesetzt sein. Das Ergebnis zeigt getrennt, ob die Kongruenz gilt und ob die Zahl zusammengesetzt ist.
Reicht der Lucas-Test allein als Beweis, dass eine Zahl prim ist?
Nein. Manche zusammengesetzte Zahlen bestehen eine einzelne Lucas-Stufe; deshalb kombiniert das Baillie–PSW-Verfahren sie mit einem starken Fermat-Test zur Basis 2. Diese Prüfung zeigt Ihnen, ob Ihr Kandidat zu diesen Zahlen gehört.
Verwandte Tools
Für Entwickler — API-Zugang
Alles auf dieser Seite ist auch per API verfügbar. Dieser Abschnitt richtet sich an Teams, die es in ihre eigenen Systeme einbinden möchten; alle anderen nutzen einfach das Tool oben.
Endpunkt
Authentifizierung per Bearer-Token. Ein einziger POST stellt die Aufgabe in die Warteschlange; das Ergebnis erhalten Sie per Webhook oder über einen signierten Link.
Aufruf aus Ihrem Stack
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)Beispiel-Anfrage
{
"n": "323",
"P": "1",
"Q": "-1"
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.lucas_pseudoprime_check",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}Die API arbeitet asynchron: Sie erhalten sofort eine task_id. Polling ist mit 1 Anfrage pro Sekunde erlaubt.
Preis
Der Preis steht auf der Seite – keine Tokens, keine Credits. Fehlgeschlagene Aufgaben werden nicht berechnet.
Fehler
| HTTP | Code | Bedeutung |
|---|---|---|
401 | unauthorized | Der API-Schlüssel fehlt oder ist ungültig – prüfen Sie den Authorization-Header (Bearer). |
402 | insufficient_balance | Ihr Guthaben reicht für diese Aufgabe nicht aus – Aufladungen verfallen nicht. |
404 | unknown_type | Unbekannter Aufgabentyp – prüfen Sie das Feld „type“ gegen den Katalog. |
429 | rate_limited | Zu viele Anfragen – warten Sie kurz; Polling ist mit 1 Anfrage pro Sekunde erlaubt. |
Technische Hinweise
Was eine Lucas-Pseudoprimzahl ist und wie der U-Test funktioniert
Ist D ein von null verschiedenes perfektes Quadrat, bricht die Binet-artige geschlossene Form zu einer reinen geometrischen Folge zusammen und die Folgen verlieren die arithmetischen Eigenschaften, die sie für Primzahltests nützlich machen; dieser Endpunkt lehnt solche Parameter daher mit invalid_input ab, statt eine sinnlose Null zurückzugeben.
Eingabevertrag, Antwortfelder und Fehlerverhalten
Eine echte Primzahl wie dreizehn mit denselben Parametern besteht den Lucas-Test, wird aber nicht als Pseudoprimzahl gekennzeichnet. Senden Sie einen JSON-Körper mit drei Pflicht-Ganzzahlfeldern: n, der ungerade Kandidat mindestens drei; P, der erste Lucas-Parameter; und Q, der zweite. Jedes Feld darf als JSON-Zahl oder als dezimale Ganzzahlzeichenkette ankommen. Nicht-Ganzzahlen, fehlende Felder, gerades n und n unter drei scheitern mit invalid_input und benennen das Problem. Bei Erfolg spiegelt der Körper n, P, Q und D als Dezimalzeichenketten; jacobi ist das Jacobi-Symbol von D über n als Zahl aus der Menge minus eins, null oder eins; u_index ist n minus jacobi, wenn das Symbol nicht null ist; u_mod_n ist U an diesem Index modulo n; gcd_ok ist wahr, wenn n teilerfremd zu Q mal D ist; passes_lucas_test ist genau dann wahr, wenn die U-Kongruenz unter den klassischen Bedingungen gilt; is_prime ist ein deterministisches Miller–Rabin-Urteil im unterstützten Bereich; und is_lucas_pseudoprime ist nur wahr, wenn n zusammengesetzt ist, gcd_ok gilt, das Jacobi-Symbol nicht null ist und die Kongruenz weiterhin gilt. Das Feld method ist stets die Zeichenkette lucas_u_sequence, damit Clients den Algorithmus in Protokollen verankern können. Beispiel: n gleich dreihundertdreiundzwanzig, P gleich eins, Q gleich minus eins liefert D gleich fünf, jacobi gleich minus eins, u_index gleich dreihundertvierundzwanzig, u_mod_n gleich null, is_prime falsch und is_lucas_pseudoprime wahr. Fehlgeschlagene Validierung wird nicht berechnet; erfolgreiche Aufrufe kosten den veröffentlichten Basispreis $0.002 auf dem API-Pfad.
Wo eine Lucas-Pseudoprim-API ihren Nutzen zeigt
Unterrichts- und Wettbewerbsplattformen brauchen ein deterministisches Orakel, das Fibonacci- und allgemeine Lucas-Pseudoprimzahlen korrekt markiert, ohne dass Studierende modularen Rekursionscode von Hand schreiben, der Vierundsechzig-Bit-Ganzzahlen überlaufen lässt. Inhaltsseiten, die für Lucas-Pseudoprim-Prüfer ranken, gewinnen ein Live-Werkzeug, dessen kostenloser Browserpfad dem bezahlten Automatisierungspfad auf demselben reinen Modul entspricht. Halten Sie n innerhalb der dokumentierten Zifferngrenze, pinnen Sie goldene Tripel für Ihre bevorzugten P und Q, und Sie erhalten reproduzierbare Lucas-PSP-Klassifikation für Hausaufgaben, LMS-Plugins und Edge-Worker, ohne ein eigenes Computeralgebrasystem aufzusetzen. Kryptografie-Lehrmaterial kann zeigen, dass ein einzelner algebraischer Test kein Primheitszertifikat ist, indem es ein Zusammengesetztes vorführt, das noch passes_lucas_test wahr zurückgibt, während is_prime falsch ist. Forschungsnotebooks, die Parameterfamilien nach neuen Lucas-Pseudoprimzahlen spezieller Typen durchsuchen, profitieren von einer kompakten Parse-API, die den vollständigen Zwischenzustand —D, Jacobi, Index und Rest— liefert, sodass gefiltert und geplottet werden kann, ohne quadratische Reziprozität neu zu implementieren. Weil die Implementierung pure parse der Stufe A ist, kostet jeder erfolgreiche Aufruf $0.002 ohne Modell-Tokens und ohne ausgehendes Netz.
Integrationsbeispiele
Unterrichtsübungen zu Fibonacci- und Lucas-PSP
Lassen Sie Studierende n mit P=1, Q=−1 (oder anderen Parametern) einreichen und is_lucas_pseudoprime gegen Lehrbuchlisten wie 323 prüfen.
Regressionstests von Primzahlbibliotheken
Pinnen Sie bekannte Lucas-Pseudoprimzahlen und Primzahlen in der CI, damit Ihre modulare U_k-Leiter nie von der klassischen Kongruenz abweicht.
Parametersuchen in der Forschung
Durchsuchen Sie Familien von P und Q nach zusammengesetzten n, die noch U_{n−ε} ≡ 0 (mod n) erfüllen, und nutzen Sie D, jacobi und u_mod_n in der Antwort.
Technische Fragen
Ist 323 eine Lucas-Pseudoprimzahl?
Ja für die Fibonacci-Parameter P=1, Q=−1 (D=5). Sie ist zusammengesetzt (17×19) und dennoch gilt U_{324} ≡ 0 (mod 323), also ist is_lucas_pseudoprime wahr.
Zählt eine echte Primzahl als Lucas-Pseudoprimzahl?
Nein. Echte Primzahlen, die die U-Kongruenz erfüllen, setzen passes_lucas_test und is_prime auf wahr, aber is_lucas_pseudoprime bleibt definitionsgemäß falsch.
Was kostet der Lucas-Pseudoprim-Prüfer?
Das Browser-Werkzeug ist kostenlos. API-Anfragen nutzen das vorausbezahlte KIT-Guthaben zu $0.002 pro erfolgreichem Aufruf; ungültige Eingaben werden nicht berechnet.