 |
|||
| HSG |
|
Aufgabe 1
Erstelle für folgende Liste von Primzahlen eine Tabelle, wie lange jeweils eine Primfaktorzerlegung dauert.
primzahlen = [11,
101,
1009,
10007,
100003,
1000003,
10000019,
100000007,
1000000007,
10000000019,
100000000003,
1000000000039,
10000000000037,
100000000000031,
1000000000000037,
10000000000000061,
100000000000000003,
1000000000000000003,
10000000000000000051,
100000000000000000039]
Eine mögliche Lösung könnte unter Benutzung von krypto0.py so aussehen.
>>> import time >>> zeiten = [] >>> for x in primzahlen: t1 = time.time() F = primfaktoren(x) t2 = time.time() dt = t2 - t1 zeiten.append(dt) print(F,dt) [11] 3.48091125488e-05 [101] 3.981590271e-05 [1009] 5.19752502441e-05 [10007] 7.48634338379e-05 [100003] 0.000165939331055 [1000003] 0.000465869903564 [10000019] 0.00144600868225 [100000007] 0.00445890426636 [1000000007] 0.0151109695435 [10000000019] 0.0510239601135 [100000000003] 0.162130832672 [1000000000039] 0.184911966324 [10000000000037] 0.591362953186 [100000000000031] 1.85889196396 [1000000000000037] 5.94947719574 [10000000000000061] 18.837854147 [100000000000000003] 59.5337159634 [1000000000000000003] 200.291700125
In diesem Zusammenhang interessiert mal wieder, wie man unter Linux eine laufende Berechnung hart abbrechen kann.
mk@x2:~$ ps ax|grep python 2045 ? S 0:00 /usr/bin/python /usr/share/system-config-printer/applet.py 2095 ? S 0:00 /usr/bin/python /usr/lib/system-service/system-service-d 2498 ? Rl 3:16 /usr/bin/python3.1 /usr/bin/idle-python3.1 -n 2603 pts/0 S+ 0:00 grep python mk@x2:~$ kill 2498 mk@x2:~$
Es ist interessant, die Verhältnisse aufeinanderfolgender Zeiten zu bilden.
>>> f = [round(zeiten[i+1]/zeiten[i],2) for i in range(1,len(zeiten)-1)] >>> f [1.31, 1.44, 2.22, 2.81, 3.1, 3.08, 3.39, 3.38, 3.18, 1.14, 3.2, 3.14, 3.2, 3.17, 3.16, 3.36] >>>
Welche Rechenzeiten sind für die Zahlen
10000000000000000051 100000000000000000039 1000000000000000000117 1451985073868057639624096704831
zu erwarten, die sich - bis auf die letzte Zahl - an obige anschliessen? Überprüfe an mindestens zwei Zahlen die Vermutung.
Satz 7, Der Satz von Fermat
p Primzahl, (a,p) = 1 ⇒ ap-1 ≡ 1(p)
Beweis: Der Satz folgt aus dem Satz von Euler, wenn man φ(p) = p-1 bedenkt. Das wiederum gilt, weil eine Primzahl p zu allen Zahlen a, 1 ≤ a < p teilerfremd ist. ∎
Fermat-Test
Der Satz von Fermat bietet eine Möglichkeit, eine ungerade Zahl n als zusammengesetzt zu erkennen, ohne einen Primfaktor zu kennen. Eine gerade Zahl ist mit Ausnahme von 2 keine Primzahl.
def Fermattest(n,a=2):
"""
true, falls a 'bezeugen' kann, dass n zusammengesetzt ist, false sonst
"""
return modpower(a,n-1,n) != 1
Tests
>>> for i in range(1,3000): n = 2*i+1 F = primfaktoren(n) ft = Fermattest(n) if len(F) > 1 : # keine Primzahl if not ft: print(n, primfaktoren(n),Fermattest(n)) 341 [11, 31] False 561 [3, 11, 17] False 645 [3, 5, 43] False 1105 [5, 13, 17] False 1387 [19, 73] False 1729 [7, 13, 19] False 1905 [3, 5, 127] False 2047 [23, 89] False 2465 [5, 17, 29] False 2701 [37, 73] False 2821 [7, 13, 31] False 3277 [29, 113] False 4033 [37, 109] False 4369 [17, 257] False 4371 [3, 31, 47] False 4681 [31, 151] False 5461 [43, 127] False >>> for i in range(1,3000): n = 2*i+1 F = primfaktoren(n) ft = Fermattest(n) if len(F) == 1 : # Primzahl if ft: print(n, primfaktoren(n),Fermattest(n)) >>>
Die Tests zeigen, dass es in den ungeraden Zahlen 3, ..., 5999 eine kleine Menge von Zahlen gibt, die die Aussage des Satzes von Fermat erfüllen, ohne Primzahlen zu sein. Umgekehrt wurde - natürlich - keine Primzahl unter 6000 gefunden, die fälschlich als zusammengesetzt getestet wird. So gilt etwa:
>>> 11*31 341 >>> Fermattest(341) False >>> 2**340%341 1 >>> 3**340%341 56 >>>
Die 2 konnte 341 nicht als zusammengesetzt entlarven, was aber mit 3 gelingt. Zur Erinnerung: (3,341) = 1, angenommen 341 ist Primzahl, dann folgt nach dem kleinen Satz von Fermat, dass 3340≡1(341) gelten muss. Das ist aber nicht der Fall, also muss die Annahme, dass 341 eine Primzahl ist, falsch sein.
Miller-Rabin-Test
Auf www.inf-schule.de gabe es mal eine Python-Version des gegenüber dem einfachen Fermattest wesentlich verbesserten Miller-Rabin-Tests.
In einem ersten Schritt wird bei dem Test, aus der zu untersuchenden Zahl n eine Darstellung \[d \cdot 2^j = n-1 \text{ , d ungerade, } j > 0 \] hergeleitet. Mit anderen Worten: n-1 wird, sooft es geht, durch 2 dividiert, n-1 = 2⋅2⋅ ... ⋅2⋅d
Wir testen das an paar Beispielen:
>>> n = 257 >>> j = 0 >>> d = n-1 >>> while d%2 == 0: d = d//2 j = j+1 >>> j 8 >>> d 1 >>> d*2**j 256 >>> n = 1001 >>> j = 0 >>> d = n-1 >>> while d%2 == 0: d = d//2 j = j+1 >>> j 3 >>> d 125 >>> n = 561 >>> j = 0 >>> d = n-1 >>> while d%2 == 0: d = d//2 j = j+1 >>> j 4 >>> d 35 >>> d*2**j 560 >>> n = 1009 >>> j = 0 >>> d = n-1 >>> while d%2 == 0: d = d//2 j = j+1 >>> j 4 >>> d 63 >>> d*2**j 1008 >>>
In einem zweiten Schritt wird nun zu einem a < n-1 eine Liste \( [ (a^d) \text{ mod n}, (a^{d \cdot 2}) \text{ mod n}, (a^{d \cdot 4}) \text{ mod n}, (a^{d \cdot 8}) \text{ mod n}, ..., (a^{d \cdot 2^j}) \text{ mod n} ] \) aufgestellt. Die Liste hat die Eigenschaft, dass außer dem ersten Element jedes Element das Quadrat modulo n des vorangehenden ist.
>>> a = 2 # willkürlich gewählt >>> n=257 >>> j = 8 >>> d = 1 >>> [a**(d*2**i)%n for i in range(j+1)] [2, 4, 16, 256, 1, 1, 1, 1, 1] >>> n = 1001 >>> j = 3 >>> d = 125 >>> [a**(d*2**i)%n for i in range(j+1)] [32, 23, 529, 562] >>> n=561 >>> j = 4 >>> d = 35 >>> [a**(d*2**i)%n for i in range(j+1)] [263, 166, 67, 1, 1] >>> n = 1009 >>> j = 4 >>> d = 63 >>> [a**(d*2**i)%n for i in range(j+1)] [192, 540, 1008, 1, 1]
Immer, wenn diese Liste auf eine 1 endet, weiß man, dass an-1≡1(n) gilt. Das ist nach dem kleinen Satz von Fermat ein Indiz dafür, dass n eine Primzahl ist. Umgekehrt weiß man sicher, dass n keine Primzahl ist, wenn die Liste auf eine Zahl ≠ 1 endet. Taucht in der Liste vorher schon mal 1 oder auch -1 auf, so braucht man nicht weitersuchen, der letzte Eintrag wird eine 1 sein. Eine nähere Erläuterung dazu findet man in dem wikipedia-Artikel.
Folgende Funktion MPprim benutzt die gewonnenen Erkenntnisse.
Es sei nochmal daran erinnert, dass die Bindungsstärke von '%' geringer als die von '*' ist, sodass a*a%n = (a*a)%n gilt. Vorsicht, (a+b)%n ist im Allgemeinen nicht a+b%n.
def MRprim(a,n):
"""
True, falls n bezueglich zur Basis a den Miller-Rabin-Test besteht,
False sonst, False bedeutet also, dass n sicher keine Primzahl ist,
True bedeutet, dass n mit einer Wahrscheinlichkeit von mindestens
3/4 eine Primzahl ist
"""
j = 0
d = n-1
while d%2 == 0:
d = d//2
j = j+1
apot = modpower(a,d,n) # erster Listeneintrag
print(apot) # DEBUG
if (apot == 1) or (apot == -1):
return True
else:
while j > 0:
apot = apot*apot%n
print(apot) # DEBUG
if (apot == 1) or (apot == -1):
return True
j = j-1
return False
Tests
>>> MRprim(2,257) 2 4 16 256 1 True >>> MRprim(2,1001) 32 23 529 562 False >>> MRprim(2,561) 263 166 67 1 True >>> MRprim(3,561) 78 474 276 441 375 False >>> MRprim(2,1009) 192 540 1008 1 True
Am Beispiel der Zahl 561 sieht man, dass MRprim auch mit einer gewissen Wahrscheinlichkeit versagen kann. Diese Wahrscheinlichkeit beträgt laut Literatur höchstens 1/4. Die Wahrscheinlichkeit, dass MRprim für zwei verschiedene a versagt, beträgt dann nur noch 1/4*1/4 = 1/16. Führt man also den MRprim-Test mehrfach hintereinander aus, so erhält man einen schnellen Test, der trotzdem (fast) zuverlässig ist.
def MRTest(n,t=20):
"""
es wird an t verschieden Basen der MRprim-Test durchgefuehrt,
passiert n alle Tests, so ist es mit einer Fehlerwahrscheinlichkeiten
von (1/4)**t (0.25**20 = 9.095e-13) eine Primzahl,
n darf nicht 0 oder 1 sein
"""
basen = []
while len(basen) < t:
a = random.randint(2,n-2)
while a in basen:
a = random.randint(2,n-2)
basen.append(a)
# print(basen) # DEBUG
if not MRprim(a,n):
return False
return True
Tests
>>> import time >>> for x in primzahlen: t1 = time.time() w = MRTest(x) t2 = time.time() print(x,w,t2-t1) 11 True 0.000257015228271 101 True 0.000634908676147 1009 True 0.000817060470581 10007 True 0.000940084457397 100003 True 0.00124001502991 1000003 True 0.0013530254364 10000019 True 0.00157499313354 100000007 True 0.00179290771484 1000000007 True 0.00197100639343 10000000019 True 0.00229096412659 100000000003 True 0.00254011154175 1000000000039 True 0.00275588035583 10000000000037 True 0.00296115875244 100000000000031 True 0.00347709655762 1000000000000037 True 0.00355195999146 10000000000000061 True 0.00410103797913 100000000000000003 True 0.00408506393433 1000000000000000003 True 0.00438499450684 >>> MRTest(1451985073868057639624096704831) True
Primzahlgeneratoren
def primzahl(u,o):
"""
gibt zufaellig eine Primzahl p mit u <= p <= o zurueck
"""
n = random.randint(u,o)
while not MRTest(n):
n = random.randint(u,o)
return n
def nextprime(g):
"""
gibt die kleinste Primzahl p >= g zurueck
"""
n = g
while not MRTest(n):
n = n + 1
return n
Tests
>>> primzahl(100,1000) 883 >>> for x in [10**i for i in range(1,20)]: print(nextprime(x)) 11 101 1009 10007 100003 1000003 10000019 100000007 1000000007 10000000019 100000000003 1000000000039 10000000000037 100000000000031 1000000000000037 10000000000000061 100000000000000003 1000000000000000003 10000000000000000051
Zusatzaufgabe
Teste MRTest an den Zahlen von RSA-129.
'altes' Delphi-Programm
begin
u := StrToInt(eUnten.Text); o := StrToInt(eOben.Text);
repeat
n := u+random(o-u);
primfak(n,p,h);
until p[1] = n;
ePrim.text := IntToStr(n);
end;
Links
- RSA-Kryptosystem - wikipedia