Primzahl Prüfung und Faktorisierung

Eine Primzahl ist eine natürliche Zahl größer als 1, die keine positiven Teiler außer 1 und sich selbst hat. Die ersten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 ist die einzige gerade Primzahl: Jede andere gerade Zahl ist durch 2 teilbar und somit zusammengesetzt. Das macht 2 unter den Primzahlen einzigartig. Wie man prüft, ob eine Zahl eine Primzahl ist: Nur die Teilbarkeit durch Primzahlen bis zur Quadratwurzel prüfen. Um 97 zu testen: 2, 3, 5, 7 prüfen (√97 ≈ 9,8). Teilt keine davon glatt, ist sie prim. Unendlich viele Primzahlen: Euklid bewies um 300 v. Chr., dass es unendlich viele Primzahlen gibt. Die größte bekannte Primzahl hat über 40 Millionen Ziffern. Warum Primzahlen wichtig sind: RSA-Verschlüsselung (Online-Banking, E-Mail, HTTPS) beruht darauf, dass die Multiplikation zweier großer Primzahlen einfach ist, aber die Faktorisierung des Ergebnisses zurück in seine Primfaktoren rechnerisch nicht durchführbar ist.