Primzahlen

(zu tm.jpg)

Primfaktorzerlegung

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:

Der kleine Satz von Fermat

Für jede Primzahl p und jede natürliche Zahl a mit 0 < a < p gilt:

tex:a^{p-1} \equiv 1 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.

Der Satz von Euler Sind a und n zwei natürliche teilerfremde Zahlen, dann gilt:

tex:a^{\Phi(n)} \equiv 1 mod n

tex:\Phi(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:

tex:\Phi(12) = 4, teilerfremde Zahlen sind {1, 5, 7, 11}
tex:\Phi(13) = 12, teilerfremde Zahlen sind {1,2,3,4,5,6,7,8,9,10,11,12}
tex:\Phi(14) = 6, teilerfremde Zahlen sind {1,3,5,9,11,13}

Zu einer Primzahl p sind alle Zahlen von 1 bis (p-1) teilerfremd. Daraus folgt: tex:\Phi(p) = p - 1

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: tex:\Phi(p \cdot q) = (p - 1) \cdot (q-1)

Zurück zu Lernpfad Kryptographie | GeoGebra 3.2: Texte codieren, Listen bearbeiten, Restklassenarithmetik ...