Lucas-Lehmer-Test

Antranias, https://pixabay.com/photo-250025/

Mit diesem Lucas-Lehmer-Test kann man überprüfen ob einen Mersenne-Zahl eine Primzahl ist. Nochmal zu Erinnerung: Eine Mersenne-Zahl \(M_n\) ist eine Zahl der Form

\[M_n=2^n-1.\]

Grundlage für den Lucas-Lehmer-Test ist ein Satz der 1930 von Derrick Lehmer bewiesen wurde. Der Satz geht ursprünglich auf Arbeiten von Édouard Lucas aus dem Jahr 1878 zurück.

Satz
Sei \(M_p\) eine Mersenne-Zahl und p prim. Weiterhin seien \(S_1=4\) und \(S_{k+1}=S_k^2-2 \mod{M_p}\). Dann gilt: \(M_p\)  ist genau dann eine Primzahl, wenn \(S_{p-1}=0\)

In Python ist der Test relativ einfach umzusetzen, da Python von Haus aus den Umgang mit großen Zahlen unterstützt. Die Größe der Zahl ist nur durch den Speicherplatz beschränkt. Die folgende Funktion erwartet als Eingabe eine Primzahl p. Zunächst wird überprüft ob die Zahl p eine Sophie-Germain-Primzahl mit \(p\equiv 3(mod 4)\) ist. Falls ja, dann ist die Mersenne-Zahl nicht prim.

def testMersennePrime(p): 
# Test ob p eine Sophie-Germain-Prinzahl ist
if is_prime(2*p+1) and p % 4 == 3:
return False
m = 2p - 1
  s = 4
  for i in range(2, p):
  s = (s**2 - 2) % m
if s == 0:
return True
else:
return False

Miller-Rabin-Test

Der Miller-Rabin-Test ist ein probabilistischer Primzahltest. Er liefert entweder “Zahl ist zusammengesetzt” oder “Zahl ist wahrscheinlich prim” als Ergebnis zurück. Je nachdem wie viele Durchläufe gemacht werden erhöht sich die Wahrscheinlichkeit, das eine Zahl wirklich prim ist, wenn “wahrscheinlich prim” ausgegeben wird.

Für den Test wählt man zunächst eine Zahl \(a\in \{1,\dots , n-1\}\) und berechnet zwei Zahlen d und j, so dass

\[n-1 =d{2^j}\]

gilt. Wenn jetzt

\[a^d \equiv 1(mod{n})\]

oder

\[a^{d 2^r}\equiv -1(mod {n})\] für ein r mit \[0<= r<j\]

gilt, dann ist n prim. Für einige Paare n und a ist die Bedingung aber auch erfüllt, wenn n nicht prim ist. Deshalb führt man den Test möglichst oft durch.

In Python ist die Implementierung recht einfach. Die folgende Implementierung ist angelehnt an die Referenzimplementierung von rosettacode.org.

import random

def millerRabinTest(n, number):
""" Miller-Rabin-test
@param n: Number to test
@param number: Number of repeated tests
"""
assert(n >= 2)

# special case 2
if n == 2:
return True
# is n odd
if n % 2 == 0:
return False
s = 0
d = n-1
while True:
q, r = divmod(d, 2)
if r == 1:
break
s += 1
d = q
assert(2**s * d == n-1)

def try_composite(a):
# Test the first condition
if pow(a, d, n) == 1:
return False
# Test the second condition
for i in range(s):
if pow(a, 2**i * d, n) == n-1:
return False
return True

  # Repeat the test numbers-times
for i in range(numbers):
a = random.randrange(2, n)
if try_composite(a):
return False
  return True

Wie hat dir der Artikel gefallen? 1 Stern2 Sterne3 Sterne4 Sterne5 Sterne (Bisher keine Bewertungen)

Loading...

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Ich akzeptiere

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.