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:

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)$

Technologieinfos: GeoGebra 3.2: Texte codieren, Listen bearbeiten, Restklassenarithmetik ...

Zurück zu Lernpfad Kryptographie