Faktorisierung

In der heutigen Stunde haben wir zu Beginn kurz über das neue Schulnetzwerk geredet. Im Anschluss haben wir mit der Faktorisierung von Primzahlen weitergemacht, mit der wir vor den Ferien begonnen hatten. Dabei geht es um die Darstellung einer Zahl n in möglichst kleine Primfaktoren.

Beispiel 1: 16 = 2 * 2 * 2 * 2

Beispiel 2: 104 = 2 * 2 * 13

Im Anschluss, haben wir uns einen Code angeschaut der die Faktorisierung übernimmt. Dabei ist es wichtig zu wissen, das der größte Faktor NICHT größer sein kann als die Wurzel der untersuchten Zahl n.

Zu Beginn initialisiert man die Liste „faktoren“, in der man später die Faktoren speichert . Dann übergibt man die zu untersuchende Zahl n der Hilfsvariabel z. Wenn z größer als 1 ist, teilt man z solange durch i, bis z durch i ohne Rest teilbar ist oder i größer als die Wurzel von z ist(i wird nach jedem Durchlauf natürlich um 1 größer). Kommt man zu keinem Ergebnis, so übergibt man z p und hängt p in die Liste „faktoren“. Kommt man zu einem Ergebnis, so übergibt man i der Variable p und hängt diese an „faktoren“.

def primfaktoren(n):

    faktoren = []
    z = n
    while z > 1:
        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
        faktoren = faktoren + [p]
        z = z // p
    return faktoren

Diese Methode ist derzeit noch besonders wichtig um zum Beispiel Webseiten zu verschlüsseln. Bei dieser Methode nimmt man eine 1000 – stellige Zahl die aus 2 Primzahlen besteht. In jedem Browser kann man die jeweilige Zahl der Webseite transparent einsehen, indem man in der Suchleiste auf das Schlosssymbol klickt.

Hier kann man im unteren Teil den Schlüssel sehen

Das herausfinden dieser Primzahlen ist mit heutigen mitteln viel zu langwierig und daher nahezu unmöglich. Um zu zeigen wie lang dies dauert, kann man mit unserem Programm einen Test schreiben indem man zum Beispiel diese Testzahlen untersucht.

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]

Dies sind die Ergebnisse bis zur Zahl 100000000000000003. Bei dieser brauchte das Programm knapp 2 Minuten.

Zahl: 11
Primfaktoren: [11]
Rechenzeit: 0.006286800000000037

Zahl: 101
Primfaktoren: [101]
Rechenzeit: 1.0400000000021503e-05

Zahl: 1009
Primfaktoren: [1009]
Rechenzeit: 1.5700000000007375e-05

Zahl: 10007
Primfaktoren: [10007]
Rechenzeit: 1.8400000000029504e-05

Zahl: 100003
Primfaktoren: [100003]
Rechenzeit: 6.089999999997486e-05

Zahl: 1000003
Primfaktoren: [1000003]
Rechenzeit: 0.00021569999999998535

Zahl: 10000019
Primfaktoren: [10000019]
Rechenzeit: 0.0006327999999999889

Zahl: 100000007
Primfaktoren: [100000007]
Rechenzeit: 0.0021724000000000188

Zahl: 1000000007
Primfaktoren: [1000000007]
Rechenzeit: 0.007190499999999989

Zahl: 10000000019
Primfaktoren: [10000000019]
Rechenzeit: 0.03761429999999999

Zahl: 100000000003
Primfaktoren: [100000000003]
Rechenzeit: 0.0984739

Zahl: 1000000000039
Primfaktoren: [1000000000039]
Rechenzeit: 0.33958559999999993

Zahl: 10000000000037
Primfaktoren: [10000000000037]
Rechenzeit: 1.1127182999999998

Zahl: 100000000000031
Primfaktoren: [100000000000031]
Rechenzeit: 3.5182312

Zahl: 1000000000000037
Primfaktoren: [1000000000000037]
Rechenzeit: 11.394075699999998

Zahl: 10000000000000061
Primfaktoren: [10000000000000061]
Rechenzeit: 36.06607939999999

Zahl: 100000000000000003
Primfaktoren: [100000000000000003]
Rechenzeit: 111.5369196

Schreibe einen Kommentar