Prime Number
Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist; sie ist der Baustein der Zahlentheorie, und jede ganze Zahl zerfällt eindeutig in Primfaktoren.
Zweck
Als Bausteine der ganzen Zahlen dienen, Grundlage der Zahlentheorie und Kryptografie (RSA).
Mechanismus
Eine natürliche Zahl größer als 1, deren einzige Teiler 1 und sie selbst sind. Fundamentalsatz der Arithmetik: Jede ganze Zahl zerfällt eindeutig in Primfaktoren. Primzahltests: Probedivision, Miller-Rabin (probabilistisch), AKS (deterministisch, aber langsam). Es gibt unendlich viele Primzahlen (Beweis von Euklid).
Anwendungsfälle
- RSA-Schlüsselgenerierung
- Diffie-Hellman-Parameter
- Primzahlgrößen von Hashtabellen
- Forschung in der Zahlentheorie
Beispiele
- Eingabe
The first 10 primesOutput2,3,5,7,11,13,17,19,23,292 is the only even prime
Häufige Fehler
- Using small primes for RSA moduli
- Use large primes (≥1024 bits)
Verwandte Begriffe
Modular Arithmetic
Modulare Arithmetik nimmt Reste nach Ganzzahloperationen und hält Ergebnisse in [0, n); sie ist die Grundlage der Zahlentheorie und Kryptographie. GLOSSAR
BigInteger
BigInteger ist ein Ganzzahltyp mit beliebiger Genauigkeit, der nicht an eine feste Wortbreite gebunden ist, und dient Berechnungen jenseits des nativen Integerbereichs (etwa Kryptographie und Kombinatorik). GLOSSAR
GCD
Der ggT (größter gemeinsamer Teiler) ist die größte positive ganze Zahl, die zwei oder mehr ganze Zahlen teilt, effizient berechnet mit dem euklidischen Algorithmus. GLOSSAR