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.

Bei kleineren Zahlen kann man eine Primfaktorzerlegung oft direkt angeben. Bei größeren Zahlen sollte man systematisch vorgehen, um die Primfaktoren zu bestimmen. Bei noch größeren Zahlen ist es ratsam, die erforderlichen Berechnungen von einem Computer ausführen zu lassen - der kann das viel zuverlässiger und schneller.

Aufgabe 1

(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 divividiert 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 <= n 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 2

Teste die Funktion primfaktoren(n). Wie zeigt sich, dass die Ausgangszahl eine Primzahl ist?

Aufgabe 3

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 4

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 5

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 10⁴⁴-mal so lange wie bei der 12-stelligen Zahl - also etwa 10⁴⁴ 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.