[python] Modulares Rechnen mit großen Zahlen

Neue Frage »

Malcang Auf diesen Beitrag antworten »
[python] Modulares Rechnen mit großen Zahlen
Hallo zusammen,

wie manche ja mitbekommen haben, schaue ich mir derzeit diesen Primzahltest an:
[attach]56784[/attach]

In python habe ich diesen folgendermaßen umgesetzt:

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:
25:
def bosma(h, k, step = 2):
    if (k % 2 == 0):
        if (h % 3 == -1):
            return False
    else:
        if (h % 3 == 1):
            return False 
    exp = h * pow(2, k-1)
    n = 2*exp + 1
    for D in range(3, lim, step):
        if jacobisymbol(D, n) == 0:
            # ggT(D, n)> 1
            return False
        
        if jacobisymbol(D, n) == -1:
            # Es wurde ein passendes D gefunden.
            # Damit ist die Äquivalenz anwendbar.
            # In dieser Verzweigung wird also auf jeden Fall korrekt entschieden, ob prim oder nicht.
            if pow(D, exp, n) == n-1:
                return True
            else:
                return False
    # Sollte (D, n) niemals -1 ergeben, so liegt eine Quadratzahl vor.
    # Daher wird auch dann False zurückgegeben
    return False


Es funktioniert auch.
Mir ist aber aufgefallen,dass die Berechnung in Zeile 19 ein Flaschenhals ist.
Mit Exponenten in der Größenordnung dauert diese Berechnung eine Sekunde, mit bereits 8 Sekunden.

Da ich im Programmieren wirklich nicht fit bin denke ich mal, dass mein Code sicherlich nicht optimal ist.
Gibt es insbesondere für diese Berechnung Möglichkeiten, die ich nicht sehe?

Vielen Dank und schönes Restsonntag smile
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Malcang
Mit Exponenten in der Größenordnung dauert diese Berechnung eine Sekunde, mit bereits 8 Sekunden.

Von welchem und (noch wichtiger) welchem Modul redest du hier?

Vielleicht solltest du es statt mit pow(D, exp, n) auch einfach mal mit gmpy2.powmod(D, exp, n) probieren, diese Bibliothek hatte sich ja auch schon anderweitig als performanter erwiesen. verwirrt
Malcang Auf diesen Beitrag antworten »

Hallo HAL, danke für deine Zeit!

Zitat:
Original von HAL 9000
Zitat:
Original von Malcang
Mit Exponenten in der Größenordnung dauert diese Berechnung eine Sekunde, mit bereits 8 Sekunden.

Von welchem und (noch wichtiger) welchem Modul redest du hier?

Es sind und . Dabei werden die Werte von sukzessive abgegrast, bis erfüllt ist.

Zitat:
Original von HAL 9000
Vielleicht solltest du es statt mit pow(D, exp, n) auch einfach mal mit gmpy2.powmod(D, exp, n) probieren, diese Bibliothek hatte sich ja auch schon anderweitig als performanter erwiesen. verwirrt


Das probiere ich sofort aus smile

Edit: Donnerwetter, das ist schon deutlich besser. bosma(5001, 15000) dauert jetzt nur noch 0.73 statt 8.5 Sekunden!

Vielen Dank!! smile
Neue Frage »
Antworten »



Verwandte Themen

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