Station - Faktorisierung
Primzahlen - Bausteine der natürliche Zahlen
Eine der wichtigsten Eigenschaften von Primzahlen ist, dass sie als Bausteine der natürlichen Zahlen angesehen werden können.
Satz: Jede natürliche Zahl lässt sich als Produkt von Primzahlen schreiben. Diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig.
Beispiel: Die Zahl 260 kann wie folgt mit Primzahlen aufbaut werden:
260 = 2*2*5*13 = 22*5*13
Man nennt die Primzahlen, die in einer Produktdarstellung einer gegebenen Zahl vorkommen, auch Primfaktoren der Zahl.
Das Faktorisierungsproblem
Das Faktorisierungsproblem besteht darin, eine vorgegebene Zahl in ein Produkt aus Primfaktoren zu zerlegen.
Aufgabe 1
Das Faktorisieren einer Zahl n ist das Gegenteil der Multiplikation der Primfaktoren, aus denen n aufgebaut ist. Man geht in der Mathematik und Informatik davon aus, dass die Faktorisierung schwieriger ist als die Multiplikation.
Teste diese Vermutung mit dem folgenden Tool:
Aufgabe 2
(a) Bei kleineren Zahlen kann man eine Primfaktorzerlegung oft direkt angeben. Bestimme eine Primfaktorzerlegung von n = 48 und n = 100. (Primzahlen werden grün markiert)
= × × × × × × ✔
(b) Bei größeren Zahlen sollte man systematisch vorgehen, um die Primfaktoren zu bestimmen. Bestimme eine Primfaktorzerlegung von n = 221 und n = 585.
(c) Entwickle zunächst einen Algorithmus zur Primfaktorzerlegung.
Beschreibe in einem ersten Schritt in Worten das Verfahren, das du zur Primfaktorzerlegung von
Zahlen benutzt. Beschreibe das Verfahren anschließend mit einem Struktogramm.
Entwickle dann ein Programm zur Primfaktordarstellung.
Hinweis: In Python bietet es sich an, eine Funktion primfaktoren(n)
zu erstellen, die die Liste der Primfaktoren zurückgibt.
Ein einfaches Faktorisierungsverfahren
Ein einfaches Faktorisierungsverfahren basiert auf dem Verfahren der Probedivision: Wenn n die vorgegebene natürlich Zahl bezeichnet, dann dividiert man probeweise n der Reihe nach durch alle Zahlen von 2 aufwärts, bis die Division aufgeht oder die Wurzel aus n als Grenze erreicht wird. Wenn auf diese Weise ein Primfaktor gefunden wird, so wird er in einer Liste zur Verwaltung sämtlicher Primfaktoren aufgenommen. Die Ausgangszahl wird durch den Primfaktor dividiert und das Verfahren wird mit dem Quotienten analog durchgeführt. Das Verfahren endet, wenn die zu überprüfende Zahl eine Primzahl ist. Diese wird dann ebenfalls in der Liste der Primfaktoren aufgenommen.
Die folgende Übersicht verdeutlicht das Verfahren am Beispiel n = 51.
# Übergabe
n = 51
# Initialisierung
faktoren = [] {faktoren -> []}
z = n {z -> 51}
# Probedivisionen
z % 2 -> 1
z % 3 -> 0
# Aktualisierung
p = 3 {p -> 3}
faktoren = faktoren + [p] {faktoren -> [3]}
z = z // p {z -> 17}
# Probedivisionen
z % 2 -> 1
z % 3 -> 2
z % 4 -> 1
z % 5 -> 2
# Aktualisierung
p = z {p -> 17}
faktoren = faktoren + [p] {faktoren -> [3, 17]}
z = z // p {z -> 1}
# Rückgabe
[3, 17]
Allgemein beschreiben lässt sich das Verfahren mit dem folgenden Algorithmus:
ALGORITHMUS primfaktoren(n):
initialisiere die Liste faktoren: faktoren = []
initialisiere die Hilfsvariable z: z = n
SOLANGE z > 1:
bestimme den kleinsten Primfaktor p von z mit Probedivisionen
füge p in die Liste faktoren ein
z = z // p
Rückgabe: faktoren
Implementierung des Verfahrens
Das Verfahren kann wie folgt als Funktion in Python implementiert werden:
def primfaktoren(n):
""" zerlegt eine Zahl in ihre Primfaktoren
>>> primfaktoren(24)
[2, 2, 2, 3]
"""
faktoren = []
z = n
while z > 1:
# bestimme den kleinsten Primfaktor p von z
i = 2
gefunden = False
while i*i <= z and not gefunden:
if z % i == 0:
gefunden = True
p = i
else:
i = i + 1
if not gefunden:
p = z
# füge p in die Liste der Faktoren ein
faktoren = faktoren + [p]
z = z // p
return faktoren
Aufgabe 3
Teste die Funktion primfaktoren(n). Wie zeigt sich, dass
die Ausgangszahl eine Primzahl ist?
Aufgabe 4
Bestimme mit der Funktion primfaktoren(n) die Primfaktorzerlegung der beiden Zahlen
484639526894037745950720 und 565765434324543216797351.
Was stellst du fest? Stelle eine Vermutung auf, warum es hier zu einem unterschiedlichen Laufzeitverhalten
kommt.
Laufzeiten messen
Das folgende Testprogramm zeigt, wie man in Python die Laufzeit messen kann.
Beachte, dass die Funktion primfaktoren(n) im Modul faktorisierung.py
definiert ist.
from faktorisierung import primfaktoren
from time import *
n = 4563421773
t1 = clock()
ergebnis = primfaktoren(n)
t2 = clock()
t = t2 - t1
print("Zahl: ", n)
print("Primfaktoren:", ergebnis)
print("Rechenzeit: ", t)
Um Gesetzmäßigkeiten herauszufinden, sollte man beim Testen systematisch vorgehen.
Zunächst ist es günstig, sich auf Zahlen eines bestimmten Typs zu beschränken. Viele Probedivisionen muss das Verfahren durchführen, wenn die zu verarbeitende Zahl eine Primzahl ist. Dann muss die zu verarbeitende Zahl durch alle Zahlen von 2 bis zur Wurzel der Zahl dividiert werden.
Interessiert man sich für den Zusammenhang zwischen der Größe der vorgegebenen Zahl und der Laufzeit, sollte man die zu untersuchenden Zahlen systematisch vergrößern. Wir werden im Folgenden die vorgegebene Zahl immer (in etwa) um eine 10er-Potenz (d.h. eine Dezimalstelle) vergrößern. Als Testzahlen werden der Reihe nach die jeweils kleinsten Primzahlen genommen, die größer als die nächste 10er-Potenz ist.
from faktorisierung import primfaktoren
from time import *
testzahlen = [
11,
101,
1009,
10007,
100003,
1000003,
10000019,
100000007,
1000000007,
10000000019,
100000000003,
1000000000039,
10000000000037,
100000000000031,
1000000000000037,
10000000000000061,
100000000000000003,
1000000000000000003,
10000000000000000051,
100000000000000000039,
1000000000000000000117,
10000000000000000000009,
100000000000000000000117,
1000000000000000000000007,
10000000000000000000000013,
100000000000000000000000067,
1000000000000000000000000103,
10000000000000000000000000331,
100000000000000000000000000319]
for z in testzahlen:
t1 = clock()
ergebnis = primfaktoren(z)
t2 = clock()
t = t2 - t1
print("Zahl: ", z)
print("Primfaktoren:", ergebnis)
print("Rechenzeit: ", t)
print()
Aufgabe 5
Führe die Laufzeitmessungen durch. Entscheide selbst, wann du die Ausführung der Berechnungen abbrichst. Warum solltest du während der Messreihe keine anderen Programme starten und verwenden?
Gesetzmäßigkeiten herausfinden
Folgende Messergebnisse erhält man, wenn man systematische Laufzeitmessungen durchführt. Beachte, dass die Messergebnisse vom benutzten Rechner abhängen. Deine Messergebnisse werden sich daher wohl von den hier gezeigten unterscheiden.
>>>
Zahl: 11
Primfaktoren: [11]
Rechenzeit: 8.93968367488e-06
Zahl: 101
Primfaktoren: [101]
Rechenzeit: 1.31301603975e-05
Zahl: 1009
Primfaktoren: [1009]
Rechenzeit: 2.6260320795e-05
Zahl: 10007
Primfaktoren: [10007]
Rechenzeit: 6.67682624468e-05
Zahl: 100003
Primfaktoren: [100003]
Rechenzeit: 0.000212317487278
Zahl: 1000003
Primfaktoren: [1000003]
Rechenzeit: 0.000668520719812
Zahl: 10000019
Primfaktoren: [10000019]
Rechenzeit: 0.00217876853064
Zahl: 100000007
Primfaktoren: [100000007]
Rechenzeit: 0.00702519454288
Zahl: 1000000007
Primfaktoren: [1000000007]
Rechenzeit: 0.0223148472781
Zahl: 10000000019
Primfaktoren: [10000000019]
Rechenzeit: 0.0867154903766
Zahl: 100000000003
Primfaktoren: [100000000003]
Rechenzeit: 0.286610449093
Zahl: 1000000000039
Primfaktoren: [1000000000039]
Rechenzeit: 0.906267137304
Zahl: 10000000000037
Primfaktoren: [10000000000037]
Rechenzeit: 2.88270213114
Zahl: 100000000000031
Primfaktoren: [100000000000031]
Rechenzeit: 9.1279123464
Zahl: 1000000000000037
Primfaktoren: [1000000000000037]
Rechenzeit: 28.5701070946
Zahl: 10000000000000061
Primfaktoren: [10000000000000061]
Rechenzeit: 91.2736900919
Aufgabe 6
Kannst du anhand der Zahlen bereits erste Zusammenhänge erkennen? Kannst du anhand der Zusammenhänge Prognosen erstellen, wie lange man wohl bis zum nächsten Ergebnis warten muss.
Gesetzmäßigkeiten beschreiben
Die Messergebnisse weisen (in etwa) folgende Regelmäßigkeit auf:
Wenn man die Anzahl der Stellen der Ausgangszahl um 2 erhöht, dann
erhöht sich die Laufzeit um den Faktor 10.
Jede zusätzliche Stelle bei der Ausgangszahl führt also dazu,
dass die Laufzeit mit dem Faktor √10 multipliziert wird.
Es handelt sich hier um ein exponentielles Wachstumsverhalten, das man
mathematisch mit einer Exponentialfunktion beschreiben kann:
Wenn k die Anzahl der Stellen der Ausgangszahl angibt,
dann erhält man eine Laufzeit vom Typ L(k) = c*(√10)k
mit einer Konstanten c.
Prognosen erstellen
Wie lange dauert es im ungünstigsten Fall, wenn man eine natürliche Zahl mit 100 Stellen in ihre Primfaktoren zerlegen möchte?
Wenn man das Laufzeitverhalten eines Algorithmus / Programms mit einer Gesetzmäßigkeit beschreiben kann, dann lässt sich diese Gesetzmäßigkeit benutzen, um Prognosen zu erstellen.
Beim vorliegenden Programm zur Primfaktorzerlegung benötigt man etwa 1 Sekunde, um eine 12-stellige Zahl im ungünstigten Fall zu faktorisieren. Wenn die Zahl z.B. 100 Stellen haben soll, also 88 Stellen mehr als eine 12-stellige Zahl, so benötigt man nach der gefundenen Gesetzmäßigkeit 1044-mal so lange wie bei der 12-stelligen Zahl - also etwa 1044 Sekunden. Das ist eine Zeit, die weit jenseits jeglicher Vorstellungsmöglichkeiten liegt.
Schnelle Faktorisierungsverfahren und RSA
Die Sicherheit des RSA-Verfahrens hängt davon ab, ob eine Primfaktorzerlegung effizient durchgeführt werden kann. Das oben beschriebene einfache Faktorisierungsverfahren leistet keine effiziente Primfaktorzerlegung. Es gibt durchaus Verfahren, die das Faktorisierungsproblem besser lösen als unser einfaches Verfahren. Es ist jedoch noch kein Algorithmus entwickelt worden, der das Faktorisierungsproblem mit nicht-exponentieller Zeitkomplexität löst. Alle bisher entwickelten Algorithmen sind demnach - im Fall großer Ausgangszahlen - praktisch nicht anwendbar. Ob es jemals Algorithmen geben wird, die das Faktorisierungsproblem mit nicht-exponentieller Zeitkomplexität lösen werden, ist nicht bekannt.
