Sehr wahrscheinlich prim

Neue Frage »

Malcang Auf diesen Beitrag antworten »
Sehr wahrscheinlich prim
Guten Morgen zusammen,

ich habe in "Samuel Wagstaff - The Joy of Factoring" folgende Definition gefunden:
[attach]54063[/attach]

Ich habe der Definition folgend diesen Algorithmus verfasst:
[attach]54064[/attach]

Das erscheint mir aber beim erneuten Lesen zu viel des Guten zu sein, da ja ohnehin nur eine von beiden Bedingungen erfüllt sein kann. Daher habe ich den Algorithmus abgewandelt und stelle mal hier meinen Pythoncode bereit. Die Variable bedingung1 ist nun weggefallen und die entsprechende Kongruenz wird direkt geprüft und ausgewertet.
Übersehe ich hier noch weiteres?

Vielen Dank an alle Leser und Helfer!

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
def strongprob(m, a):
    n = m - 1
    e = 0
    while n % 2 == 0:
        n = n // 2
        e = e + 1
    f = (m-1) // pow(2, e)
    if pow(a, f, m) == 1:  return True  
    bedingung2 = False
    c = 0
    while (bedingung2 == False and c < e):
        if pow(a, f*pow(2, c), m) == m-1:    bedingung2 = True
        c = c + 1
    return bedingung2
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »