Pollard-p−1-Faktorisierung
Findet einen Faktor einer zusammengesetzten Zahl, wenn eine ihrer Primzahlen p ein glattes p − 1 hat: 1003 mit Schranke 16 zerfällt in 17 und 59, denn 17 − 1 ist 16. Erscheint nichts, erhöhen Sie die Schranke. 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
- 1003
- Schranke
- 16
- Faktor
- 17
- Kofaktor
- 59
- Basis
- 2
Die p-minus-eins-Methode von Pollard ist ein klassischer Algorithmus zur Zerlegung ganzer Zahlen, der einen nichttrivialen Faktor eines zusammengesetzten Moduls n findet, wenn mindestens ein Primfaktor p von n die Eigenschaft hat, dass p minus eins glatt bezüglich einer gewählten Schranke B ist — jede Primzahlpotenz in der Zerlegung von p minus eins ist höchstens B. Studierende der elementaren Zahlentheorie, CTF-Teilnehmende und Kryptografie-Lernende begegnen diesem Algorithmus, wenn sie verstehen, warum RSA-Moduli Primzahlen mit glatten Totienten vermeiden müssen. Diese Fähigkeit führt eine deterministische Stufe-eins-Suche nach Pollard p−1 aus: Sie bildet das Produkt der Primzahlpotenzen bis B, erhebt eine kleine Basis zu diesem Exponenten modulo n und liefert den ggT dieser Potenz minus eins mit n, sobald der ggT ein echter Faktor ist.
Wie Pollard p−1 aus glattem p−1 einen Faktor findet
Fixieren Sie eine zusammengesetzte ganze Zahl n und eine positive Glattheitsgrenze B. Pollards Beobachtung ist einfach: Ist p ein Primteiler von n und jede Primzahlpotenz, die p minus eins teilt, höchstens B, dann ist das kleinste gemeinsame Vielfache der ganzen Zahlen von eins bis B ein Vielfaches von p minus eins. Nach dem kleinen Satz von Fermat gilt für jede zu p teilerfremde Basis a, dass a hoch p minus eins kongruent eins modulo p ist, und daher ist a erhoben zu diesem großen kgV ebenfalls kongruent eins modulo p.
Dieselbe Potenz modulo n zu berechnen und den größten gemeinsamen Teiler des Ergebnisses minus eins mit n zu bilden, liefert oft p oder einen anderen nichttrivialen Faktor. In der Praxis baut die Implementierung das volle kgV nie explizit; sie siebt die Primzahlen bis B und erhebt für jede Primzahl q den laufenden Akkumulator zur höchsten Potenz von q, die B nicht überschreitet, alles modulo n. Nach jedem Primzahlpotenzschritt wertet sie den ggT des Akkumulators minus eins mit n aus.
Ein intermediärer nichttrivialer ggT wird sofort zurückgegeben. Kollabiert der ggT zu n, versucht ein feinerer Erholungsgang über kleinere Exponenten, einen einzelnen Primfaktor zu isolieren, bevor diese Basis aufgegeben wird. Mehrere kleine Basen werden erprobt, damit unglückliche Ordnungen der Basis zwei einen ansonsten B-glatten Faktor nicht verbergen.
Die Methode ist kein vollständiger Faktorisierungsalgorithmus: Sie liefert einen nichttrivialen Faktor und den passenden Kofaktor. Wer die vollständige Primfaktorzerlegung braucht, kann jedes zusammengesetzte Stück in ein Primfaktor-Werkzeug speisen oder B anheben und erneut laufen. Erfolg ist nur im glatten p−1-Szenario garantiert; große Primfaktoren von p minus eins erzwingen ein größeres B oder einen anderen Algorithmus wie die Elliptische-Kurven-Methode oder das quadratische Sieb.
Wann sich diese Zerlegungsmethode lohnt
Kryptografie-Kurse nutzen Pollard p−1, um zu zeigen, warum Primzahlen mit glatten Vorgängern bei der RSA- und Diffie–Hellman-Parametererzeugung gefährlich sind; ein Live-Werkzeug, das n und B akzeptiert, lässt Lehrkräfte eine Spaltung im Unterricht zeigen, ohne modulare Exponentiation von Hand zu schreiben. Capture-the-Flag- und Hausaufgabenplattformen brauchen ein deterministisches Orakel, das entweder einen dokumentierten Faktor für klassische Semiprimzahlen wie eintausenddrei mit Schranke sechzehn liefert oder zu kleine Schranken ablehnt, damit Bewerter sowohl korrekte Faktoren als auch korrekte Fehlschlussfolgerungen bewerten können.
Sicherheitstechniker, die veraltete Schlüsselerzeugung prüfen, können Kandidatenmoduli auf Faktoren mit glattem p−1 untersuchen, bevor sie die Produktion erreichen. Notebook-Autoren, die bereits eine allgemeine Primfaktorroutine haben, profitieren dennoch von einem expliziten p−1-Endpunkt, wenn die Lektion die Methode selbst und nicht die vollständige Faktorenliste ist. Halten Sie n innerhalb der Zifferngrenze, wählen Sie B groß genug, um den größten Primfaktor von p minus eins für irgendeinen Primteiler p von n abzudecken, und Sie erhalten reproduzierbare Faktoren für Lehre, CTF-Write-ups und leichte Audits, ohne einen vollen Computer-Algebra-Stack aufzubauen.
Anwendungsfälle
Hygiene von Kandidatenmoduli
Untersuchen Sie RSA- oder Diffie–Hellman-Kandidatenmoduli auf Faktoren mit glattem p−1 vor dem Deployment, ohne eine volle Faktorisierungssuite zu importieren.
Häufige Fragen
Was ist die Pollard-p−1-Faktorisierungsmethode?
Es ist ein Stufe-eins-Algorithmus, der eine große glatte Potenz einer Basis modulo n berechnet und gcd(a^M − 1, n) zurückgibt. Er findet einen Faktor p, wenn p−1 für die gewählte Schranke B B-glatt ist.
Wann findet die Methode keinen Faktor?
Wenn n prim ist, wenn jeder Primfaktor p von n einen Primteiler von p−1 größer als B hat, oder wenn die Erholung keinen echten Faktor isolieren kann.
Liefert sie die vollständige Primfaktorzerlegung?
Nein. Sie liefert einen nichttrivialen Faktor und den Kofaktor n/factor (kleinerer zuerst). Zerlegen Sie jedes Stück weiter mit einem Primfaktor-Werkzeug, wenn Sie alle Primzahlpotenzen brauchen.
Welche Schranke sollte ich wählen?
Beginnen Sie klein und erhöhen Sie, wenn kein Faktor erscheint. Die Schranke muss jede Primzahlpotenz in p − 1 für mindestens einen Primfaktor p Ihrer Zahl abdecken. Erlaubt ist jede ganze Zahl von 2 bis 50.000.
Wie viele Stellen darf die Zahl haben?
Bis zu 18 Stellen, als ganze Zahl ohne Punkte, Kommas oder Leerzeichen. Gerade Zahlen liefern sofort den Faktor 2, und eine Primzahl ergibt keinen Faktor, weil es nichts zu zerlegen gibt.
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/pollard-p-minus-one \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":"1003","bound":16}'const res = await fetch("https://api.kit.forhosting.com/numth/pollard-p-minus-one", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": "1003",
"bound": 16
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/pollard-p-minus-one",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": "1003",
"bound": 16
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/pollard-p-minus-one", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":"1003","bound":16}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":"1003","bound":16}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/pollard-p-minus-one", 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": "1003",
"bound": 16
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.pollard_p_minus_one",
"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
Ist die Schranke zu eng, n prim oder jeder Faktor resistent, schlägt die Aufgabe mit invalid_input fehl, statt einen Faktor zu erfinden. Der kostenlose Browserpfad und die bezahlte API teilen dasselbe reine BigInt-Modul, sodass Hausaufgabenprüfungen und Automatisierung nie voneinander abweichen.
Eingabevertrag, Antwortform und Fehlerfälle
Beispiel: n gleich eintausenddrei und bound gleich sechzehn liefert Faktor siebzehn und Kofaktor neunundfünfzig, weil siebzehn minus eins sechzehn ist, was sechzehn-glatt ist. Ist n gerade, wird der Faktor zwei sofort ohne volle Stufe-eins-Suche zurückgegeben. Senden Sie per POST ein JSON-Objekt mit zwei Pflichtfeldern. Das Feld n ist die zu faktorisierende ganze Zahl: eine sichere JavaScript-Ganzzahl oder eine einfache Dezimalzeichenkette ohne Kommas, Leerzeichen oder wissenschaftliche Notation, mit mindestens zwei und höchstens achtzehn Dezimalziffern. Das Feld bound ist die Glattheitsgrenze B, eine ganze Zahl von zwei bis fünfzigtausend; die Aliase B, b, smoothness_bound und smoothness werden der Bequemlichkeit halber akzeptiert. Bei Erfolg spiegelt der Körper n als Dezimalzeichenkette und bound als Ganzzahl wider und meldet factor und cofactor als Dezimalzeichenketten mit dem kleineren Faktor zuerst, die Basis, die den Faktor lieferte, sowie method auf die feste Zeichenkette pollard_p_minus_one gesetzt. Fehlende Felder, Nicht-Ganzzahlen, n unter zwei, bound außerhalb des veröffentlichten Bereichs und n mit mehr als achtzehn Ziffern scheitern mit invalid_input und werden nicht berechnet.
Wo eine p−1-Faktor-API ihren Nutzen hat
Weil die Implementierung reines Parse der Stufe A ist, kostet jeder erfolgreiche Aufruf den veröffentlichten Grundpreis $0.002 ohne Modell-Tokens und ohne ausgehendes Netz, und fehlgeschlagene Validierung verbraucht nie Guthaben.
Integrationsbeispiele
Unterrichtsdemos zu glattem p−1
Zeigen Sie, wie eine Schranke B, die p−1 eines Primfaktors einer Semiprimzahl abdeckt, eine nichttriviale Spaltung liefert, mit Klassikern wie n=1003 und B=16.
CTF- und Hausaufgaben-Autokorrektur
Bewerten Sie Pollard-p−1-Übungen mit einem deterministischen Orakel, das den Faktor liefert, wenn B ausreicht, und invalid_input, wenn die Schranke zu eng ist.
Technische Fragen
Welche Eingaben verlangt die API?
Das Feld n (Ganzzahl ≥ 2, ≤ 18 Ziffern) und das Feld bound (Glattheit B von 2 bis 50000). Aliase umfassen number/value für n und B/smoothness_bound für bound.
Was kostet die Pollard-p−1-Faktorisierung?
Das Browser-Werkzeug ist kostenlos. API-Anfragen nutzen vorausbezahltes KIT-Guthaben zu $0.002 pro erfolgreichem Aufruf; ungültige Eingabe und fehlgeschlagene Schranken werden nicht berechnet.