a: ganze Zahl
p: Primzahl
64 / 3 = 21 Rest 1
4 / 3 = 1 Rest 1
a = (x₁ + 2) ∙ (x₂ + 2)
a: zusammengesetzte Zahlen
x1, x2: beliebige ganze Zahlen
| x1 | x2 | a |
| 0 | 0 | 4 |
| 1 | 0 | 6 |
| 2 | 0 | 8 |
| 1 | 1 | 9 |
| 3 | 0 | 10 |
| 2 | 1 | 12 |
| 2 | 2 | 16 |
| 5 | 0 | 14 |
| 3 | 1 | 15 |
| zurück Home | Primzahlen | ||||||||||||||||||||||||||||||||
| allgemeines | Zahlen, die nur durch 1 und sich selbst teilbar sind: 1,2,3,5,7,11,13,17 ... | ||||||||||||||||||||||||||||||||
| Faktorisieren | Eine Zahl in Primzahlen zerlegen | Für große Zahlen ist die Zerlegung in Primzahlen sehr aufwendig. Die Multiplikation der Primzahlen ist vergleichsweise einfach. | Deshalb beruhen asymmetrische Schlüssel häufig auf Faktorisierung. | ||||||||||||||||||||||||||||||
| asymmetrische Schlüssel | RSA-Verfahren | Man wählt 2 große Primzahlen p und q. | Das Produkt p * q = n veröffentlicht man, die Faktoren hält man geheim. | ||||||||||||||||||||||||||||||
| Zum Verschlüsseln muss man lediglich das Produkt kennen. | Entschlüsseln kann man nur wenn man die Primfaktoren p und q weiss. | ||||||||||||||||||||||||||||||||
| kleiner Satz von Fermat | ap ≡ a (mod p) a: ganze Zahl p: Primzahl |
z.B 43 = 64 64 / 3 = 21 Rest 1 4 / 3 = 1 Rest 1 |
Geht nur mit Primzahlen. Test für große Primzahlen. | ||||||||||||||||||||||||||||||
| Mersenne-Primzahlen | darstellbar durch 2n-1 | Wenn 2n-1 eine Primzahl ist, dann ist n auch eine Primzahl. | |||||||||||||||||||||||||||||||
| zusammengesetzte Zahlen | Zahlen, die nicht Primzahlen sind. | Alle zusammengesetzten Zahlen lassen sich durch diese Formel
erzeugen: a = (x₁ + 2) ∙ (x₂ + 2) a: zusammengesetzte Zahlen x1, x2: beliebige ganze Zahlen |
Zahlenbeispiele:
| ||||||||||||||||||||||||||||||
| schwache Primzahlen | Verändert man irgendeine der Ziffern, dann haben sie Teiler. | Z.B. 294 001 | |||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||
Impressum Zuletzt geändert am 24.09.2022 7:09