1.19.4.6.1: Informatik » Kryptologie » Das RSA-Verfahren » Primzahlalgorithmen » Station - Primzahltest
Primzahlen sind bekanntlich natürliche Zahlen größer als 1, die nur durch 1 und sich selbst (ohne Rest) teilbar sind.
Beispiele:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
Aus der Primzahleigenschaft ergibt sich direkt ein einfacher Algorithmus, mit dem man bei einer natürlichen Zahl n überprüfen kann, ob es sich um eine Primzahl handelt.
(a) Formuliere den Algorithmus in Struktogrammform.
(b) Implementiere und teste den Algorithmus.
(c) Entwickle Möglichkeiten zur Verbesserungen des einfachen Algorithmus.
Für die Praxis benötigt man effiziente Testverfahren, die auch bei großen Zahlen (mit mehr als 600 Stellen) schnell ein Ergebnis liefern.
Im Folgenden betrachten wir erst ein einfaches Testverfahren:
def primzahl(n):
""" überprüft, ob n eine Primzahl ist:
>>> primzahl(24)
False
"""
if n <= 2:
if n < 2:
prim = False
else:
prim = True
else:
if n % 2 == 0:
faktorgefunden = True
else:
faktorgefunden = False
t = 3
while t*t <= n and not faktorgefunden:
if n % t == 0:
faktorgefunden = True
else:
t = t + 2
prim = not faktorgefunden
return prim
# Test
n = 1974110059
from time import *
t1 = clock()
ergebnis = primzahl(n)
t2 = clock()
t = t2 - t1
print("primzahl(", n, ") = ", ergebnis)
print("Rechenzeit: ", t)
(a) Führe den Primzahltest erst mit kleinen Zahlen durch.
(b) Führe den Primzahltest auch mit einer größeren Primzahl durch, z. B. p = 1451985073868057639624096704831. Was stellst du fest?
Um genaueren Aufschluss über das Laufzeitverhalten des Primzahltests zu erhalten, werden jetzt systematische Laufzeitmessungen durchgeführt.
primzahlen = [
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]
from time import *
for p in primzahlen:
t1 = clock()
ergebnis = primzahl(p)
t2 = clock()
t = t2 - t1
print("Primzahl: ", p, "Rechenzeit: ", t)
Man erhält z.B. die folgenden Ergebnisse:
>>> Primzahl: 11 Rechenzeit: 5.86666741164e-06 Primzahl: 101 Rechenzeit: 8.3809534452e-06 Primzahl: 1009 Rechenzeit: 1.50857162014e-05 Primzahl: 10007 Rechenzeit: 3.54793695847e-05 Primzahl: 100003 Rechenzeit: 0.000101968266917 Primzahl: 1000003 Rechenzeit: 0.000324342898329 Primzahl: 10000019 Rechenzeit: 0.00104817791088 Primzahl: 100000007 Rechenzeit: 0.00332500359683 Primzahl: 1000000007 Rechenzeit: 0.0105655886432 Primzahl: 10000000019 Rechenzeit: 0.0407208178693 Primzahl: 100000000003 Rechenzeit: 0.140259725747 Primzahl: 1000000000039 Rechenzeit: 0.447675891768 Primzahl: 10000000000037 Rechenzeit: 1.41919042783 Primzahl: 100000000000031 Rechenzeit: 4.55093566361 Primzahl: 1000000000000037 Rechenzeit: 14.3208156344 Primzahl: 10000000000000061 Rechenzeit: 45.2250185429 Primzahl: 100000000000000003 Rechenzeit: 144.197546336 ...
(a) Führe diese Messungen selbst durch. Beachte, dass du mit einem anderen Rechner wohl auch andere Messergebnisse erhälst.
(b) Versuche, anhand der Messergebnisse eine Gesetzmäßigkeit herauszufinden: Wenn n sich in etwa verzehnfacht, dann ... .
(c) Mit einer gefundenen Gesetzmäßigkeit kannst du jetzt abschätzen, wie lange es ungefähr dauert, bis p = 1451985073868057639624096704831 als Primzahl erkannt wird.
(d) Beim RSA-Verfahren benötigt man heute Primzahlen mit über 600 Stellen. Solche Primzahlen werden erzeugt, indem man Zahlen dieser Größenordnung zufällig erzeugt und dann testet, ob sie Primzahlen sind. Beurteile, ob sich einfache Testverfahren wie das oben gezeigte für diese Vorgehensweise eignen.
In der Praxis benutzt man heute oft sogenannte probabilistische Testverfahren, da sie sehr effizient arbeiten.
Probabilistischen Testverfahren funktionieren nach dem folgenden Prinzip:
Bei Übergabe einer natürlichen Zahl n erhält man als Rückgabe entweder n ist keine Primzahl
oder
n ist wahrscheinlich eine Primzahl
.
Diese Testverfahren liefern also keine absolute Gewissheit, wenn sie das Ergebnis n ist wahrscheinlich eine Primzahl
produzieren. Die übergebene Zahl n kann mit einer bestimmten Wahrscheinlichkeit auch keine Primzahl
sein. Allerdings ist diese Wahrscheinlichkeit sehr gering, so dass man die Unsicherheit oft in Kauf nimmt.
Eines dieser probabilistischer Testverfahren ist das Miller-Rabin-Verfahren, das im Folgenden getestet werden soll. Beachte, dass die Wiederholungszahl 20 (s.u.) die Fehlerwahrscheinlichkeit beeinflusst. Setzt man diese Wiederholungszahl auf einen größeren Wert, so nimmt die Fehlerwahrscheinlichkeit ab.
import random
def miller_rabin_pass(a, n):
d = n - 1
s = 0
while d % 2 == 0:
d = d >> 1
s = s + 1
a_to_power = pow(a, d, n)
if a_to_power == 1:
return True
for i in range(s-1):
if a_to_power == n - 1:
return True
a_to_power = (a_to_power * a_to_power) % n
return a_to_power == n - 1
def miller_rabin_test(n):
for repeat in range(20):
a = 0
while a == 0:
a = random.randrange(n)
if not miller_rabin_pass(a, n):
return False
return True
# Test
primzahlen = [
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]
from time import *
for p in primzahlen:
t1 = clock()
ergebnis = miller_rabin_test(p)
t2 = clock()
t = t2 - t1
print("Primzahl: ", p, "Rechenzeit: ", t)
Quelle: Miller-Rabin primality test (Python)
Man erhält die folgenden Ergebnisse:
>>> Primzahl: 11 Rechenzeit: 0.000118730173807 Primzahl: 101 Rechenzeit: 0.000144990494602 Primzahl: 1009 Rechenzeit: 0.000217904789575 Primzahl: 10007 Rechenzeit: 0.000181866689761 Primzahl: 100003 Rechenzeit: 0.000280761940414 Primzahl: 1000003 Rechenzeit: 0.00031400638908 Primzahl: 10000019 Rechenzeit: 0.000371276237622 Primzahl: 100000007 Rechenzeit: 0.000415974655997 Primzahl: 1000000007 Rechenzeit: 0.000454527041845 Primzahl: 10000000019 Rechenzeit: 0.000569346104044 Primzahl: 100000000003 Rechenzeit: 0.000617117538682 Primzahl: 1000000000039 Rechenzeit: 0.000658184210563 Primzahl: 10000000000037 Rechenzeit: 0.000720482631172 Primzahl: 100000000000031 Rechenzeit: 0.000901511225589 Primzahl: 1000000000000037 Rechenzeit: 0.000982527108892 Primzahl: 10000000000000061 Rechenzeit: 0.00114316204993 Primzahl: 100000000000000003 Rechenzeit: 0.00111746045936 Primzahl: 1000000000000000003 Rechenzeit: 0.0011973588822 Primzahl: 10000000000000000051 Rechenzeit: 0.00138956208121 Primzahl: 100000000000000000039 Rechenzeit: 0.00151862876427 Primzahl: 1000000000000000000117 Rechenzeit: 0.00166445735422 Primzahl: 10000000000000000000009 Rechenzeit: 0.00163987322411 Primzahl: 100000000000000000000117 Rechenzeit: 0.0019804192991 Primzahl: 1000000000000000000000007 Rechenzeit: 0.0020670224847 Primzahl: 10000000000000000000000013 Rechenzeit: 0.00199578438042 Primzahl: 100000000000000000000000067 Rechenzeit: 0.00229358759284 Primzahl: 1000000000000000000000000103 Rechenzeit: 0.00245701618502 Primzahl: 10000000000000000000000000331 Rechenzeit: 0.00275649558813 Primzahl: 100000000000000000000000000319 Rechenzeit: 0.003038374989
Vergleiche die Ergebnisse mit denen zum einfachen Testverfahren oben. Führe selbst auch entsprechende Tests durch.
27.01.2011 ### KB