inf-schule | Primzahlalgorithmen » Station

Station - Primzahltest

Einfache Testverfahren

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, ...

Aufgabe 1

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.

Praktischer Einsatz von einfachen Testverfahren

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)

Aufgabe 2

(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
...

Aufgabe 3

(a) Führe diese Messungen selbst durch. Beachte, dass du mit einem anderen Rechner wohl auch andere Messergebnisse erhältst.

(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.

Praktischer Einsatz probabilistischer Testverfahren

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)

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

Aufgabe 4

Vergleiche die Ergebnisse mit denen zum einfachen Testverfahren oben. Führe selbst auch entsprechende Tests durch.