Rabin-Miller Strong Pseudoprime Test-Implementierung nicht funktionieren

Versucht, das umzusetzen, Rabin-Miller Strong Pseudoprime Test heute.

Verwendet haben Wolfram Mathworld als Referenz, Zeilen 3-5 fasst mein code ziemlich viel.

Jedoch wenn ich das Programm starte, sagt es (manchmal), dass Primzahlen (auch niedrig wie 5, 7, 11) sind keine Primzahlen. Habe ich mich über den code für eine sehr lange Zeit und kann nicht herausfinden, was falsch ist.

Für die Hilfe ich habe mir auf dieser Website aswell als viele andere Seiten, aber die meisten verwenden eine andere definition (wahrscheinlich das gleiche, aber da bin ich neu in dieser Art von Mathematik, die ich nicht sehen kann die gleiche offensichtliche Verbindung).

Mein Code:

import random

def RabinMiller(n, k):

    # obviously not prime
    if n < 2 or n % 2 == 0:
        return False

    # special case        
    if n == 2:
        return True

    s = 0
    r = n - 1

    # factor n - 1 as 2^(r)*s
    while r % 2 == 0:
        s = s + 1
        r = r // 2  # floor

    # k = accuracy
    for i in range(k):
        a = random.randrange(1, n)

        # a^(s) mod n = 1?
        if pow(a, s, n) == 1:
            return True

        # a^(2^(j) * s) mod n = -1 mod n?
        for j in range(r):
            if pow(a, 2**j*s, n) == -1 % n:
                return True

    return False

print(RabinMiller(7, 5))

Wie unterscheidet sich dies von der gegebenen definition bei Mathworld?

Warum muss das in Java als ein tag? Sieht aus wie Python zu mir...
Wenn Sie mit Java, vielleicht könnte Sie uns zeigen Sie Ihre java-code zu vergleichen, um den Algorithmus.
Sorry, es ursprünglich geschrieben in Java und dann umgeschrieben in Python machen es leichter zu Lesen. Dann, wenn ich gebucht, ich war nicht erlaubt, neues zu schaffen-tags (nicht zu sagen, Python ist ein neuer tag) und nahm einfach Java, da bin ich alles in es. Wieder einmal, sorry für dieses.
Sie sollten if n == 2 vor dem check für gerade zahlen, da du sonst zurück False bevor Sie selbst prüfen, ob die Zahl 2.
FWIW, eine Menge von der Logik ist umgedreht hier. Die Idee hinter Rabin-Miller-ist, dass Sie testen ein paar Dinge, und wenn die Zahl eine Primzahl ist, dass Sie passieren, also, wenn Sie nicht pass, dann sind es die composite. Jetzt bist du True zurück, sobald eine Prüfung geschieht zu übergeben. Stattdessen, Sie wirklich wollen, testen Sie diese Bedingungen, und wenn Sie Versagen, dann sollten Sie False zurück, und am Ende return True (bedeutet das womöglich, prime).
Danke für den Tipp - das ist natürlich wahr. Ich habe die Plätze getauscht auf Sie jetzt. Aber das Allgemeine problem, für n ungleich 2 (wie 7 im code) das problem bleibt immer noch.
pow(a, 2**j*s, n) == -1 % n - Ich denke, die % n am Ende ist überflüssig.
vergleicht man das Ergebnis der pow mit positiven Argumenten zu -1 (ohne Modul) ist keine gute Idee.
war nicht sicher, thx

InformationsquelleAutor Maxwell | 2013-01-30

6

1. Kommentare in Ihrem code

Einer Anzahl der Punkte, die ich machen werde weiter unten festgestellt wurden, die in anderen Antworten, aber es scheint nützlich, um Sie alle zusammen.
1. Im Abschnitt
```
s = 0
r = n - 1

# factor n - 1 as 2^(r)*s
while r % 2 == 0:
    s = s + 1
    r = r // 2  # floor
```
  du hast die Rollen von r und s vertauscht: Sie haben tatsächlich einkalkuliert n − 1 2^sr. Wenn Sie möchten, zu bleiben, um die MathWorld-notation, dann müssen Sie swap - r und s in diesem Abschnitt des Codes:
```
# factor n - 1 as 2^(r)*s, where s is odd.
r, s = 0, n - 1
while s % 2 == 0:
    r += 1
    s //= 2
```
2. In der Zeile
```
for i in range(k):
```
  die variable i ungenutzt ist: es ist üblich, Namen wie Variablen _.
3. Wählen Sie eine zufällige Basis zwischen 1 und n − 1 inklusive:
```
a = random.randrange(1, n)
```
  Dies ist, was es sagt, in dem MathWorld-Artikel, aber das Artikel ist geschrieben aus der Mathematiker-Sicht. In der Tat ist es nutzlos, um die Basis 1, da die 1^s = 1 (mod n) und Sie werden Abfall-ein Versuch. Ebenso ist es nutzlos, um die Basis n − 1, da s ist ungerade und damit (n − 1)^s = -1 (mod n). Mathematiker haben keine sorgen zu machen über vergebliche versuche, aber die Programmierer tun, so schreiben Sie stattdessen:
```
a = random.randrange(2, n - 1)
```
  (n muss mindestens 4 für diese Optimierung zu arbeiten, aber wir können leicht arrangieren, dass durch die Rückkehr True an den Anfang der Funktion, wenn n = 3, genau wie für n = 2.)
4. Wie bereits in anderen Antworten, hast du falsch verstanden, die MathWorld-Artikel. Wenn er sagt, dass "n geht der test" heißt es, dass "n besteht die Prüfung für den Basis - eine". Die Unterscheidung Tatsache über Primzahlen ist, dass Sie den test bestehen, für alle Basen. Also, wenn Sie feststellen, dass eine^s = 1 (mod n), was Sie tun sollten, ist zu gehen um die Schleife und wählen Sie den nächsten base zu testen, gegen.
```
# a^(s) = 1 (mod n)?
x = pow(a, s, n)
if x == 1:
    continue
```
5. Gibt es eine Möglichkeit für Optimierung hier. Der Wert x, dass haben wir gerade berechnet wird eine²⁰ s (mod n). So konnten wir es gleich testen und sparen uns eine loop iteration:
```
# a^(s) = ±1 (mod n)?
x = pow(a, s, n)
if x == 1 or x == n - 1:
    continue
```
6. In die Rubrik, wo du berechnen eine²^j s (mod n) jede dieser zahlen ist das Quadrat der vorhergehenden Zahl (modulo n). Es ist verschwenderisch zu berechnen, die jeweils von Grund auf neu, wenn Sie nur könnten Platz der Vorherige Wert. Also, schreiben Sie diese Schleife als:
```
# a^(2^(j) * s) = -1 (mod n)?
for _ in range(r - 1):
    x = pow(x, 2, n)
    if x == n - 1:
        break
else:
    return False
```
7. Ist es eine gute Idee, um zu testen, für die Teilbarkeit durch kleine Primzahlen, bevor Sie versuchen, Miller–Rabin. Zum Beispiel, in Rabin ist 1977 Papier er sagt:
  
  In der Implementierung des Algorithmus wir fassen einige arbeitssparende Schritte. Zuerst testen wir die Teilbarkeit von jedem prime p < N, wo, sagen N = 1000.
2. Überarbeitete Kodex

Putting all dies zusammen:
```
from random import randrange

small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31] # etc.

def probably_prime(n, k):
    """Return True if n passes k rounds of the Miller-Rabin primality
    test (and is probably prime). Return False if n is proved to be
    composite.

    """
    if n < 2: return False
    for p in small_primes:
        if n < p * p: return True
        if n % p == 0: return False
    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True
```
InformationsquelleAutor Gareth Rees
4

Zusätzlich zu dem, was Omri Barel gesagt hat, gibt es auch ein problem mit der for-Schleife. Sie werden zurück true wenn Sie einen finden a dass der test bestanden. Jedoch, alle a haben, um den test zu bestehen, für n werden, die eine mögliche Primzahl ist.
- Laut Mathworld ... oder a^(2^(j)*s) = -1 {mod n) für 0 <= j <= r - 1 ... interpretiere ich dies als es ist lediglich notwendig, eine Entsprechung für n um den test zu bestehen.
- Sie sind offenbar verlesen Mathworld die Beschreibung von test. Für einen single gegeben ein, die Ihren Kandidaten geht test. Nun Lesen Sie weiter. Es heißt: "ein prime den test bestanden für alle möglichen Entscheidungen ein". Anschließend wird beschrieben, warum, wenn Ihr Kandidat übergibt k Z-tests Sie können die (1/4)**k gebunden. Es ist vorbei, alle k tests. Alle von Ihnen, nicht nur eine.
InformationsquelleAutor Henry
2

Ich wundere mich über dieses Stück code:
```
# factor n - 1 as 2^(r)*s
while r % 2 == 0:
    s = s + 1
    r = r // 2  # floor
```
Nehmen wir n = 7. So n - 1 = 6. Wir können express n - 1 als 2^1 * 3. In diesem Fall r = 1 und s = 3.

Aber der code oben findet etwas anderes. Es beginnt mit r = 6, so r % 2 == 0. Zunächst s = 0 so nach einer iteration wir haben s = 1 und r = 3. Aber jetzt r % 2 != 0 und die Schleife beendet.

Wir am Ende mit s = 1 und r = 3 was eindeutig falsch: 2^r * s = 8.

Sollten Sie nicht aktualisieren Sie s in der Schleife. Stattdessen sollten Sie zählen, wie viele Male Sie können durch 2 dividieren (dies wird r) und das Ergebnis nach Divisionen s. In dem Beispiel von n = 7, n - 1 = 6, können wir teilen es mal (so r = 1) und nach der Teilung, die wir am Ende mit 3 (also s = 3).
- Danke - das ist die Lösung zu meinem problem!
- Es gibt noch ein problem mit dem code, obwohl (es sei denn, ich bin völlig stumpf - durchaus möglich, es ist spät). s=3, r=1, a=4, j=0 then pow(a,2**j*s,n) = 1 und (-1 % n) = 6, also n=7 keine Primzahl???
- Ja, aber die Bedingung nur oben sagt, wenn pow(a, s, n) == 1. Dies gibt uns 4^3 = 64 = 1 mod 7. Die gleich 1 ist.
- bekam Sie, 'oder' nicht 'und'... ich wurde stumpf 🙁
InformationsquelleAutor Omri Barel

Hier ist meine version:

# miller-rabin pseudoprimality checker

from random import randrange

def isStrongPseudoprime(n, a):
    d, s = n-1, 0
    while d % 2 == 0:
        d, s = d/2, s+1
    t = pow(a, d, n)
    if t == 1:
        return True
    while s > 0:
        if t == n - 1:
            return True
        t, s = pow(t, 2, n), s - 1
    return False

def isPrime(n, k):
    if n % 2 == 0:
        return n == 2
    for i in range(1, k):
        a = randrange(2, n)
        if not isStrongPseudoprime(n, a):
            return False
    return True

Wenn Sie wissen möchten, mehr über die Programmierung mit Primzahlen, die ich bescheiden empfehlen dieser essay auf meinem blog.

InformationsquelleAutor user448810

1

Sollten Sie auch einen Blick auf Wikipedia, wo die bekannten "random" - Sequenzen gibt garantiert Antworten bis zu einer bestimmten prime.
- wenn n < 1,373,653, es ist genug, um den test für a = 2 und 3;
- wenn n < 9,080,191, es ist genug, um zu testen a = 31 und 73;
- wenn n < 4,759,123,141, es ist genug, um zu testen, a = 2, 7, 61;
- wenn n < 2,152,302,898,747, es ist genug, um zu testen, a = 2, 3, 5, 7 und 11;
- wenn n < 3,474,749,660,383, es ist genug zum testen = 2, 3, 5, 7, 11, und 13;
- wenn n < 341,550,071,728,321, es ist genug zum testen = 2, 3, 5, 7, 11, 13, und 17;
- Finden Sie noch bessere Grundlagen von zahlen bis 2^64 auf miller-rabin.appspot.com
InformationsquelleAutor Albin Sunnanbo

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.

1. Kommentare in Ihrem code

2. Überarbeitete Kodex