Primes

Primzahlen faszinieren mich schon immer - wenig überraschend habe ich schon etliche Programme diesbezüglich geschrieben und einige möchte ich euch hier vorstellen. Außerdem möchte ich euch einige "Optimierungsverfahren" bei der Suche nach Primzahlen näherbringen.

Wie ist also eine Primzahl definiert?

Eine Primzahl ist eine natürliche Zahl, die nur durch 1 und sich selbst ohne Rest teilbar. 1 ist keine Primzahl, da es in der offiziellen Definition heißt, dass die beiden Teiler verschieden sein müssen.

Wie lauten die ersten Primzahlen?

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,
101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,

Gibt es eine folge, die diese Zahlen beschreibt?

Vielleicht ;-) Solltest du sie entdecken, so berichte bitte mir als ersten davon :-) Bisher wurde jedenfalls keine Möglichkeit gefunden Primzahlen vorherzusagen.

Wie kann man überprüfen ob eine Zahl p prim ist?

Ganz einfach: indem man sie durch alle Zahlen von 2 bis p-1 zu dividieren versucht und den Rest betrachtet (diesen "Vorgang" nennt man modulo). Ist dieser bei einer einzigen Division ungleich 0, so handelt es sich um keine Primzahl. Aber diese Methode ist wohl nicht sehr effektiv. Tatsächlich braucht man nur durch Zahlen zwischen 2 und sqrt(p) modulo rechnen um zu zeigen dass es eine Primzahl ist oder nicht. Das kommt daher, dass eine Nicht-Primzahl n immer zwei natürliche Teiler hat: a und b. also gilt a * b = n. Ist nun a < sqrt(n), so muss b > sqrt(n) sein, da b = sqrt(n)² / a. Und n ist ja kleiner als sqrt(a). Man kann dies natürlich noch auf anderem Wege beweisen, doch so ist es zumindest für mich "logisch nachvollziehbar" :-)

Hilft es die Primzahlen zu speichern? Wie kann ein Computer helfen?

Wenn man alle Primzahlen bestimmen möchte, ist es zunächst am klügsten sich alle bisherigen Primzahlen zu merken, denn streng genommen muss man nur die Teilbarkeit durch Primzahlen prüfen, die kleiner sind als sqrt(p). Hat man nun allerdings eine große Menge an Primzahlen berechnet, so ist es nicht mehr möglich alle Primzahlen im Speicher zu behalten. Zum Beispiel braucht eine 32-Bit-Zahl 4 Byte Speicher - damit kommt man bis 2^32 - 1 = 4.294.967.295. Ein moderner Computer mit 4GB Arbeitsspeicher (RAM) kann damit etwa 4.294.967.296 Primzahlen speichern. Es gibt da zwar noch die Auslagerungsdatei, aber dann wird der Vorgang sowieso sehr langsam...

Möchte man nur eine einzige Zahl prüfen, ob sie eine Primzahl ist, so lässt man den Computer am einfachsten zunächst durch 2 testen, anschließend durch alle ungeraden Zahlen bis zur Wurzel der zu testenden Zahl. Es gibt noch komplexere Testfolgen (als ungerade Zahlen) um dies weiter zu optimieren und sich Divisionen zu sparen, aber in den meisten Fällen wird die Berechnung nach wenigen Millisekunden abgeschlossen sein.

Wie sind Primzahlen ungefähr verteilt? Gibt es eine höchste Primzahl?

Primzahlen sind zu beginn sehr häufig und haben die Tendenz immer seltener zu werden. Jedoch kann die Häufigkeit nie 0 werden - es gibt also keine höchste Primzahl.

Wofür sind Primzahlen eigentlich so wichtig?

Naja, die erste Anwendung die man heutzutage in der Schule lernt ist wohl die Primfaktorenzerlegtung. Dabei findet man heraus, durch welche Primzahlen eine Zahl teilbar ist. Anschließend kann man den ggT (größten gemeinsamen Teiler) bzw. das kgV (kleinste gemeinsame Vielfache) bestimmen, was zum Kürzen von Brüchen praktisch sein kann.

Seit kurzem (1970) aber sind Primzahlen auch für die asymmetrische Verschlüsselung am Computer sehr wichtig, da quasi jeder Datenaustausch zwischen Computern abgefangen werden kann. Siehe dazu das Diffie-Hellman-Verfahren, sowie das RSA Verfahren. Dabei werden zwei sehr große Primzahlen multipliziert und es wird ausgenutzt, dass die Faktorisierung einer Nicht-Primzahl mit modernen Algorithmen sehr viel Zeit in Anspruch nehmen kann, wenn man die Primzahlen nicht kennt. Wie das genau funktioniert lernt man zum Beispiel in der Lehrveranstaltung "Diskrete Mathematik".

Wie speichert man Primzahlen effizient ab?

Eine Primzahlenlücke ist die Differenz zweier aufeinander folgenden Primzahlen. Meiner Meinung nach speichert man am besten zunächst die erste Primzahl und ab dann nur mehr Primzahlenlücken. Wenn man Primzahlen in mehrere Dateien speichert, kann man für jede Datei die maximale Länge der Primzahlenlücken definieren. Eine Primzahlenlücke ist nämlich immer eine sehr sehr sehr viel kleinere Zahl als die Primzahl selbst. Man könnte also weniger Bits für die Speicherung einer Primzahl aufwenden. Da diese Lücke nie 0 sein kann, empfielt es sich noch die zu speichernde Zahl um 1 zu verringern um die Ersparnis um "einen Millimeter" zu erhöhen :-)