Hintergrundwissen
Primzahlen, Definition und Grundlagen
Definition: Eine Primzahl ist eine natürliche Zahl >1, die nicht in zwei kleinere Faktoren zerlegt werden kann. ("Primzahlen sind unzerlegbar").
Bemerkung: 4 Primzahlen sind kleiner als 10, 25 Primzahlen sind kleiner als 100
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Primzahlen mit Maple oder Mathematica erzeugen:
MAPLE: A000040 := n->ithprime(n); [ seq(ithprime(i), i=1..100) ];
MATHEMATICA Table[ Prime[n], {n, 1, 60} ]
Fundamentalsatz der Arithmetik: Jede natürliche Zahl n ist (bis auf die Reihenfolge) eindeutig als Produkt von Primzahlen darstellbar
n = p1 * ... * ps
Bemerkung: Nach dem Fundamentalsatz der Arithmetik existiert zu jeder natürlichen Zahl eine eindeutige Primfaktorzerlegung. In der Praxis ist es jedoch schwer, hinreichend grosse natürliche Zahlen in ihre Primfaktoren zu zerlegen. Diese Schwierigkeit macht man sich z.B. bei der RSA-Verschlüsselungsmethode zu nutze. Den aktuellen Stand dokumentiert der RSA-Faktorisierungswettbewerb. Dort sind auf die Faktorisierung zusammengesetzter Zahlen in zwei Primfaktoren Preisgelder ausgesetzt. So hat es noch keiner geschafft, die folgende Zahl (RSA-704) zu faktorisieren:
74 03756 34795 61712 82804 67960 97429 57314 25931 88889 23128 90849 36232 63897 27650 34028 26627 68919 96419 62511 78439 95894 33050 21275 85370 11896 80982 86733 17327 31089 30900 55250 51168 77063 29907 23963 80786 71008 60969 62537 93465 05637 96359