Pollard p-1 Algorithm
Pollards p-1-Methode: Hat ein Primfaktor p ein B-glattes p-1, so verrät ein ggT mit a^(B!) mod n den Faktor.
Zweck
Zahlen bestimmter Formen unter einer Glättungsannahme faktorisieren; ein früher Faktorisierungsalgorithmus.
Mechanismus
Man wählt eine Schranke B und berechnet M=∏(q^e ≤ B für q prim), dann a=a^M mod n. Gilt p|n und p-1 ist B-glatt, so gilt a≡1 (mod p), und ggT(a-1,n) liefert p. Bei Misserfolg erhöht man B.
Anwendungsfälle
- Ganzzahlige Faktorisierung
- Zahlentheoretische Algorithmen
- Kryptoanalyse
Verwandte Tools
Teiler-Rechner
Factor Calculator — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG
Primzahl-Prüfer
Prime Checker — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG
Pollard-p-1-Faktorisierung
Pollard p-1 Factorization — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG