[python] Jacobisymbol und Primzahltest effizient implementieren

17.02.2023, 16:44

Malcang

[python] Jacobisymbol und Primzahltest effizient implementieren

Und wieder ich Big Laugh

Wie ihr wisst, setze ich mich aktuell mit einem Primzahltest auseinander. Dieser funktioniert folgendermaßen:
[attach]56821[/attach]
Dabei ist $\begin{eqnarray*} \left( \frac{D}{n}\right) \end{eqnarray*}$ das Jacobisymbol. Dieses habe ich implementiert mein Code sieht so aus:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

def jacobisymbol(a, n):
    if n == 1 or n % 2 == 0:
        return
    if a == 2:
        if n % 8 == 1 or n % 8 == 7:
            return 1
        else:
            return -1
    if a == -1:
        return pow(-1, (n-1)//2)
    if a == 1:
        return 1
    if a >= n:
        return jacobisymbol(a % n, n)
    if a == 0:
        return 0
    if a % 2 == 0:
        k = 0
        while (a % 2 == 0):
            k += 1
            a = a // 2
        return jacobisymbol(2, n) ** k * jacobisymbol(a, n)
    faktor = pow(-1, ((n-1) // 2) * (a-1) // 2)
    return faktor * jacobisymbol(n, a)

Im Grunde habe ich nur die Spezialfälle abgefangen, den "Zähler" reduziert modulo "Nenner" und ansonsten das Quadratische Reziprozitätsgesetz angewendet.

Meine eigentliche Frage betrifft allerdings zwei Versionen des Tests. Dazu ist zu sagen, dass ja ein Element $\begin{eqnarray*} D \end{eqnarray*}$ gesucht ist, sodass $\begin{eqnarray*} \left( \frac{D}{n}\right) = -1 \end{eqnarray*}$ ergibt. Ich konnte bereits zeigen, dass es eine Primzahl sein muss, welche kleinergleich $\begin{eqnarray*} \frac{n-1}{2} \end{eqnarray*}$ ist. Bisher habe ich diese "Grenze" nicht implementiert, da die infragekommenden $\begin{eqnarray*} D \end{eqnarray*}$ ohnehin sehr klein sind. Ich habe daher einfach eine Liste der Primzahlen bis $\begin{eqnarray*} 10^9 \end{eqnarray*}$ eingelesen. Es gibt natürlich noch ein paar Fälle die ich einzeln abgrasen werde, meine Frage betrifft aber vor allem, warum die zweite Version des Tests langsamer ist als die nun folgende:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

def bosma(h, k, primes):
    for D in primes:
        jacobi = jacobisymbol( (h % D)*2**(k % (D-1)) + 1, D)
        if jacobi == 0:
            return [False, D]
        if jacobi == -1:
            exp = h*2**(k-1)
            n = 2*exp+1
            if pow(int(D), exp, n) == n-1:
                return [True, D]
            return [False, D]
    return False

Das funktioniert auch.
Nun habe ich mal für $\begin{eqnarray*} h=3 \end{eqnarray*}$ alle $\begin{eqnarray*} 2\leq k\leq 6000 \end{eqnarray*}$ berechnen lassen. Die Primzahlliste wurde natürlich einmal vorab eingelesen, nicht jedesmal. Das hat 511 Sekunden gedauert.

Und dann dachte ich mir aber folgendes:
Wenn bei gegebenem $\begin{eqnarray*} h \end{eqnarray*}$ für ein $\begin{eqnarray*} k \end{eqnarray*}$ die Primzahl $\begin{eqnarray*} D_k \end{eqnarray*}$ "funktioniert", dann klappt das für alle $\begin{eqnarray*} k\pmod{ord_{D_k}(2)} \end{eqnarray*}$ . Also habe ich nicht einfach blind die Primzahlen testen lassen, sondern die Restklassen mit der dort funktionierenden Primzahl abelegt.
Beispiel:
Mit dem Test wurde für $\begin{eqnarray*} h=3 \end{eqnarray*}$ der Exponent $\begin{eqnarray*} 2 \end{eqnarray*}$ untersucht. Dabei kam heraus:
Für $\begin{eqnarray*} k = 2 \end{eqnarray*}$ geht $\begin{eqnarray*} D = 7 \end{eqnarray*}$ und $\begin{eqnarray*} ord_7(2) = 3 \end{eqnarray*}$ . Also lege ich [2, 3, 7] in der Liste Dord ab.
Für einen Exponenten wird nun zuerst abgefragt, ob eine entsprechende Restklasse bereits geprüft wurde. Wenn ja, nehme die dazugehörige Primzahl, wenn nein, führe Test durch und lege das Ergebnis ebenfalls ab.
DAs sieht dann so aus:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

for k in range(2, 6001):
    for el in Dord:
        rest, modul, usedB = el[0], el[1], el[2] 
        if (k % modul == rest):
            B = bosma(h,k,[usedB])
            break
    else:
        B = bosma(h, k, primes)
        o = ord(2, B[1])
        Dord.append([(k % o), o, B[1]])

Und das funktioniert auch. Seltsamerweise ist das aber entschieden langsamer, nämlich 580 Sekunden verwirrt

Intuitiv hätte ich ja jetzt gesagt, es sollte schneller sein, dass viele "Blinde Versuche" entfallen.
Andererseits sind die zu nutzenden Primzahlen ja auch sehr klein, also weit vorne in der Liste.
Trotzdem hätte ich mir gewünscht, dass ich diese Erkenntnis sinnig umsetzen kann.

Was ratet ihr mir?
Danke für's Lesen smile

17.02.2023, 20:44

IfindU

Auf diesen Beitrag antworten »

RE: [python] Jacobisymbol und Primzahltest effizient implementieren
10% zu Verargumentieren wird schwierig. Ich schlage vor, du misst wo dein Code wie viel Zeit braucht: Towards DataScience.

Dann kannst du gucken, wo der neue Code so viel Zeit braucht.

17.02.2023, 20:52

HAL 9000

Auf diesen Beitrag antworten »

Mal eine bescheidene Frage: Wie schlägt sich denn sympy.ntheory.jacobi_symbol im Performance-Vergleich?

18.02.2023, 00:03

Malcang

Auf diesen Beitrag antworten »

Hallo ihr zwei, danke für eure Antworten!

@IfindU: Werde mir den Link morgen in Ruhe durchlesen. Danke dafür smile

@HAL 9000: Ich habe nun beides mal mit diesem Skript laufen lassen:

code:
1: 2: 3: 4: 5: 6:	lim = 510*3 start = time.time() for m in range(1, lim+1, 2): for n in range(1, lim + 1, 2): jacobisymbol(m,n) print(time.time() - start)

sympy.ntheory.jacobi_symbol brauchte dafür 42.3 Sekunden, meine Version brauchte 51.8

18.02.2023, 09:22

HAL 9000

Auf diesen Beitrag antworten »

Das ist in der Tat ein kaum nennenswerter Unterschied.

18.02.2023, 12:18

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Das ist in der Tat ein kaum nennenswerter Unterschied.

Die Frage die sich mir noch stellt ist, ob ich nicht die am häufigsten auftretenden Fälle an den Anfang der Funktion packe. Solange das mit dem Rest des Ablaufs verträglich ist, natürlich.
Das führt mich zu Frage, die ich mir oft stelle: Sagen wir, ich laufe eine Schleife $\begin{eqnarray*} 10^6 \end{eqnarray*}$ mal durch und jedesmal gibt es (möglicherweise viele) if-Abfragen, die negativ ausfallen.
Macht sich das zeitlich überhaupt bemerkbar?

Neue Frage »

Antworten »

[python] Jacobisymbol und Primzahltest effizient implementieren

Verwandte Themen