Fermat Little Theorem
Kleiner fermatscher Satz: Ist p prim und gcd(a,p)=1, so gilt a^(p-1)≡1 (mod p); er fundiert Primzahltests und modulare Inverse.
Zweck
Eine schnelle Vereinfachung modularer Exponentiation und die theoretische Grundlage für Primzahltests liefern.
Mechanismus
a^(p-1)≡1 (mod p) impliziert a^(-1)≡a^(p-2) (mod p) (modulares Inverses). Fermat-Primzahltest: ein zufälliges a wählen und a^(n-1)≡1 (mod n) prüfen; ein Fehlschlag beweist, dass n zusammengesetzt ist. Allerdings bestehen Carmichael-Zahlen alle Fermat-Tests.
Anwendungsfälle
- Primzahltests
- Berechnung modularer Inverser
- Kryptografische Grundlagen
Verwandte Tools
Primzahl-Prüfer
Prime Checker — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG
Modulare Exponentiation
Modular Exponentiation — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG
Lucas-Primzahltest
Lucas Primality Test — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. Warnung: Die aktuelle Implementierung verwendet einfache Probedivision (äquivalent zu prime-checker), nicht den echten Lucas-Primalitätstest mit Lucas-Folgen. WERKZEUG