Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen gezeigt.
| — |
wiki:primzahlen [2013/07/12 17:32] (aktuell) |
||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| + | ~~NOCACHE~~ | ||
| + | ======Primzahlen====== | ||
| + | (zu {{:tmwiki:tm.jpg?222}}) | ||
| + | |||
| + | ===== 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: | ||
| + | |||
| + | <note> | ||
| + | **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</tex> mod //p// | ||
| + | </note> | ||
| + | |||
| + | 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**. | ||
| + | |||
| + | <note> | ||
| + | **Der Satz von Euler** | ||
| + | Sind //a// und //n// zwei natürliche teilerfremde Zahlen, dann gilt: | ||
| + | |||
| + | <tex>a^{\Phi(n)} \equiv 1</tex> mod //n// | ||
| + | |||
| + | <tex>\Phi(n)</tex> 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) | ||
| + | </note> | ||
| + | |||
| + | **Beispiele:** | ||
| + | |||
| + | <tex>\Phi(12) = 4</tex>, teilerfremde Zahlen sind {1, 5, 7, 11}\\ | ||
| + | <tex>\Phi(13) = 12</tex>, teilerfremde Zahlen sind {1,2,3,4,5,6,7,8,9,10,11,12}\\ | ||
| + | <tex>\Phi(14) = 6</tex>, 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</tex> | ||
| + | |||
| + | 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)</tex> | ||
| + | |||
| + | Zurück zu **Lernpfad** [[Kryptographie]] | [[GeoGebra32_Texte_Listen_Modulo|GeoGebra 3.2: Texte codieren, Listen bearbeiten, Restklassenarithmetik ...]] | ||
