Algebra

Primzahlen

Primzahlen sind alle natürlichen Zahlen mit genau zwei Teilern. Die Eins ist damit keine Primzahl, die Zwei ist die einzige gerade Primzahl. Bereits Euklid hat bewiesen, dass es unendlich viele Primzahlen gibt. Ebenfalls bewiesen ist, dass es in der Folge der Primzahlen beliebig große Lücken gibt.

Primzahlzwillinge sind zwei Primzahlen mit der Differenz 2, wie zum Beispiel 10007 und 10009 oder 1000018709 und 1000018711.

Aus programmtechnischen Gründen können immer nur Bereiche von maximal 50000 Zahlen auf einmal nach Primzahlen durchsucht werden. Ist die Differenz zwischen oberer und unterer Grenze größer als 50000, wird der Bereich automatisch abgeschnitten.

Beispiel

Primzahlen zwischen 1000000000 und 1000001000
1000000007 1000000009 1000000021 1000000033 1000000087 
1000000093 1000000097 1000000103 1000000123 1000000181 
1000000207 1000000223 1000000241 1000000271 1000000289 
1000000297 1000000321 1000000349 1000000363 1000000403 
1000000409 1000000411 1000000427 1000000433 1000000439 
1000000447 1000000453 1000000459 1000000483 1000000513 
1000000531 1000000579 1000000607 1000000613 1000000637 
1000000663 1000000711 1000000753 1000000787 1000000801 
1000000829 1000000861 1000000871 1000000891 1000000901 
1000000919 1000000931 1000000933 1000000993 
      49 Primzahlen

Anwendung

Bei der RSA-Verschlüsselung (Public-Key-Kryptographie) wird das Produkt aus großen Primzahlen als öffentlicher Schlüssel verwendet. Der private Schlüssel besteht aus den dazugehörenden Primfaktoren. Die Sicherheit des Verfahrens beruht darauf, dass selbst mit den heutigen technischen Möglichkeiten die Faktorisierung eines genügend großen Schlüssels nicht praktikabel ist.

Siehe auch:

Primfaktorzerlegung
Wikipedia: Primzahlen
www.Primzahlen.de
www.matheass.de