Dies ist eine alte Version des Dokuments!
Inhaltsverzeichnis
| Zurück zu: 5.Klasse » Zahlen, Mengen, Aussagen | Lernpfad Kryptographie | Technologie-Tipps zu Primfaktorzerlegung, Teilbarkeit mit Technologie | ||
Primzahlen
5, S.8 - 9
Primfaktorzerlegung
Primzahlen …
Was wir schon kennen:
- Primzahlen p haben nur zwei Teiler: 1 | p und p | p.
- Jede natürliche Zahl lässt sich als Produkt von Primzahlen scheiben - diese Primfaktorzerlegung ist bis auf die Reihenfolge der Faktoren eindeutig.
Wichtige Sätze aus der Primzahllehre
Für die Kryptographie benötigen wir u.A. folgende Sätze:
Für jede Primzahl p und jede natürliche Zahl a mit 0 < a < p gilt:
mod p
Es gibt auch Zahlen, die keine Primzahlen sind, sich aber dennoch zu einem Teil der Basen a wie Primzahlen verhalten und somit den kleinen Satz von Fermat erfüllen. Solche Nichtprimzahlen nennen wir fermatsche Pseudoprimzahlen.
mod n
ist die Anzahl der zu n teilerfremden natürlichen Zahlen (also die Anzahl aller Zahlen < n, deren größter gemeinsamer Teiler mit n gleich 1 ist)
Beispiele:
, teilerfremde Zahlen sind {1, 5, 7, 11}
, teilerfremde Zahlen sind {1,2,3,4,5,6,7,8,9,10,11,12}
, teilerfremde Zahlen sind {1,3,5,9,11,13}
Zu einer Primzahl p sind alle Zahlen von 1 bis (p-1) teilerfremd. Daraus folgt:
Für prime Moduln p geht der Satz von Euler daher in den kleinen Satz von Fermat über.
Für das Produkt zweier Primzahlen p und q gilt weiters:
