Theorie:
Wir haben im vorletzten Abschnitt gesehen, dass sich jede Zahl in ihre Primfaktoren zerlegen lässt. Das hat eine sehr nützliche Anwendung, nämlich beim Auffinden von Teilern.
Wie würde man vorgehen, wenn man Teiler einer Zahl, zum Beispiel \(819\) finden möchte? Naiv könnte man der Reihe nach alle möglichen natürlichen Zahlen kleiner als \(819\) durchprobieren, und überprüfen, durch welche sich \(819\) ohne Rest teilen lässt. Das ist entsprechend umständlich, man müsste schließlich über \(800\) mögliche Teiler ausprobieren.
Zum Glück gibt es eine etwas effizientere Methode: Man überprüft nur, durch welche Primzahlen sich \(819\) teilen lässt:
- Offensichtlich ist \(2\) kein Teiler, weil die Zahl ungerade ist.
- \(3\) ist ein Teiler, und \(819:3=273\). Um weitere Primfaktoren zu finden, genügt es nun \(273\) statt \(819\) zu untersuchen.
- \(3\) ist nochmal Teiler: \(273:3=91\). Wir arbeiten weiter mit \(91\).
- \(5\) ist kein Teiler von \(91\).
- \(7\) ist ein Teiler: \(91:7=13\).
- \(13\) ist eine Primzahl, und hat keine weiteren Teiler (außer \(1\) und sich selber).
Also ist \(819=3^2\cdot 7\cdot 13\). Da sich Primzahlen nicht weiter teilen lassen, besteht zwangsläufig jeder Teiler von \(819\) aus einem Produkt von Primzahlen einer Teilmenge der Primfaktoren \(\{3,7,13\}\). Dabei darf in einem Teiler kein Primfaktor öfter vorkommen als in der ursprünglichen Zahl. Für \(819\) bedeutet das, dass in jedem Teiler \(d\):
- der Faktor \(3\) höchsten \(2\) mal vorkommen darf, d.h. in der Primfaktorzerlegung von \(d\) darf entweder \(3\) oder \(3^2=9\) als Faktor vorkommen, nicht aber \(3^3=27, 3^4=81, \ldots\). Natürlich muss \(d\) auch gar nicht durch \(3\) teilbar sein.
- die Faktoren \(7\) und \(13\) jeweils höchstens einmal vorkommen dürfen.
Hat man die Faktorisierung von \(819\), so findet man leicht, dass beispielsweise \(3\cdot 13=39\) ein Teiler ist, aber \(17\) oder \(15=3\cdot 5\) bestimmt nicht.
Ist \(n\) eine natürliche Zahl, und \(d\) ein Teiler, so gilt: Ist \(p\) ein Primfaktor von \(d\), so ist \(p\) auch ein Primfaktor von \(n\).
Wie bestimmt man nun, ob eine gegebene Zahl eine Primzahl ist? Bei größeren Zahlen wird es zu mühsam, das Sieb des Eratosthenes durchzuführen - schließlich will man ja nicht alle Primzahlen bis zu dieser Zahl ermitteln. Ein anderes Vorgehen ist, der Reihe nach die Teilbarkeit durch Primzahlen zu testen (eine Liste der ersten Primzahlen ist hilfreich).
Eine Zahl \(n\in\mathbb N\) mit \(n\ge 2\) ist eine Primzahl genau dann, wenn sie durch keine Primzahl \(p\leq \sqrt n\) teilbar ist.
Es genügt also, nur für Primzahlen kleiner gleich \(\sqrt n\) zu testen - das macht das Testen viel einfacher.
Beispiel:
Testet man \(8431\) darauf, ob es eine Primzahl ist, genügt es, bloß die Teilbarkeit durch die Primzahlen kleiner gleich \(\sqrt{8431}\approx 92\) zu testen!
Das Zerlegen großer Zahlen (mit Hunderten Stellen) ist nach wie vor ein ungewöhnlich kompliziertes und aufwendiges Unterfangen, und man kennt nach wie vor keine sehr schnellen Algorithmen. Auf einem handelsüblichen PC kann das Faktorisieren einer \(200\)-stelligen Zahl Wochen oder sogar Monate dauern (Stand: 2015)! Die in der Kryptographie verwendeten Zahlen haben inzwischen oft mehrere \(1000\) Stellen, was es sogar für sehr schnelle Computer unmöglich macht, sie zu faktorisieren. Die Frage nach einer effizienten Faktorisierung ist nach wie vor unbeantwortet, und ein heißes Thema: Denn könnte man diese Zahlen faktorisieren, so könnte man Verschlüsselungen knacken!