Python berechnet Modulo nicht richtig?

[schoel27]

Hallo,

Ich bin absoluter Beginner in Python. Will den Miller-Rabin-Test schreiben, aber irgendwie klappt es mit dem Modulo rechnen nicht. Für kleine Zahlen klappt es, bei großen jedoch nicht. Kurz was eigentlich passieren sollte. Man gibt ein zufälliges a ein und für p eine Primzahl. Ich lass mir ein Array ausgeben, welches als letzen Wert auf jeden Fall 1 haben sollte. Bei kleinen Zahlen klappt dies auch, jedoch bei größeren nicht. Deswegen meine Vermutung, dass Python nicht mit so großen Zahlen zurecht kommt, was mich eigentlich verwundern würde. Auch mit einem debugger komme ich nicht weiter. Wenn ich die Werte nicht per Python direkt (ohne langen Algorithmus), passt es wieder. Die spannende Zeile um die es geht ist 9:

Code: Alles auswählen

def MillerRabin(p,a):
        reste=[]
        k=0
        x=p-1
        while x % 2 == 0:
            x=x/2
            k=k+1
        while k>-1:
            rest=(a**x)%p
            if rest == p-1:
                rest=-1
            reste.append(rest)
            x=2*x
            k=k-1
        return reste

print(MillerRabin(13,6))

Bei 13 = p und 6 = a funktioniert alles: [8.0, -1, 1.0]
Jedoch bei 89=9 und 5=a klappt es nicht, hier stimmen nur die ersten beide Werte: [55.0, -1, 66.0, 39.0]

Ich hoffe, mein Problem ist klar geworden, und jemand kann mir weiterhelfen

Lg schoel27

[__deets__]

Aus dem Bauch raus wuerde ich sagen: deine Typen stimmen nicht. Du musst integer verwenden, arbeitest aber mit floats. Die koennen auch nicht beliebig gross werden. Statt / musst du dann // fuer die ganzzahlige Division benutzen.

[schoel27]

Vielen Dank. Das löst tatsächlich das Problem. Irgendwiesowas hab ich mir fast gedacht, da ich mich aber nicht auskannt, wusste ich nicht an welcher Stelle Python einen anderen Typ wollte.

Vielen Dank

[__blackjack__]

@schoel27: Anmerkungen zum Quelltext: Namen werden in Python klein_mit_unterstrichen geschrieben. Ausnahmen sind Konstanten (KOMPLETT_GROSS) und Klassen (PascalCase).

Leerzeichen um das Gleichheitszeichen bei Zuweisungen (ausserhalb von Argumentlisten) und binären Operatoren, und nach Kommas, erhöhen die Lesbarbeit.

Siehe auch den Style Guide for Python Code.

Die zweite ``while``-Schleife ist eingentlich eine ``for``-Schleife, denn deren Aufgabe ist ja nur das k+1-malige ausführen des Schleifenkörpers.

Überarbeitet (und ungetestet):

Code: Alles auswählen

def miller_rabin(p, a):
    k = 1
    x = p - 1
    while x % 2 == 0:
        x //= 2
        k += 1

    reste = []
    for _ in range(k):
        rest = (a ** x) % p
        reste.append(-1 if rest == p - 1 else rest)
        x *= 2
    return reste

[Sirius3]

Es ist umständlich, erst `x` vielfach durch 2 zu teilen, nur um diese Operation danach wieder rückgängig zu machen. Die Operation (a ** x) % p führt zu sehr großen Zahlen, die dann wieder per Modulo zu einer kleinen Zahl gemacht wird, für diesen Fall gibt es `pow`.

Code: Alles auswählen

def miller_rabin(p, a):
    reste = []
    x = p - 1
    while True:
        rest = pow(a, x, p)
        reste.append(-1 if rest == p - 1 else rest)
        if x % 2 != 0:
            break
        x //= 2
    return reste[::-1]

Hier noch eine andere Variante, die zuerst effektiv die 0-Bits berechnet:

Code: Alles auswählen

def miller_rabin(p, a):
    b = p - 1
    k = (b ^ (b - 1)).bit_length()
    reste = (pow(a, b >> c, p) for c in reversed(range(k)))
    return [-1 if r == p - 1 else r for r in reste]