unterschiedliche Rechenzeiten: Distributivgesetz gilt nicht für pow und %

[hubertgrassmann]

Beim Fermatschen Primzahltest berechnet man a**(p-1)%p. Ich gehe davon aus, dass python (zumindest für ganze Zahlen) einen schnellen Potenzierungsalgorithmus besitzt. Wenn man aber diesen Algorithmus selbst implementiert und nach jeder Multpilikation modulo p reduziert, ergeben sich erstaunlich unterschiedliche Rechenzeiten:
Dauer powmod(2,p-1,p): 0:00:00
Dauer pow(2,p-1)%p: 0:00:00.28
Hier war p = 20996011, 2**p-1 war vor einigen Jahren die größte bekannte Primzahl.

[darktrym]

Ich sehe da ein Bruchteil einer Sekunde, kann man da irgendwelche Erkenntnisse daraus ziehen?

[hubertgrassmann]

Ergänzung:
Dauer powmod(2,p-1,p): 0:00:00
Dauer pow(2,p-1)%p: 0:00:00.30
Dauer 2**(p-1)%p: 0:00:00.13

Es gibt verschiedene Zeitkomplexitäten; es ist ein Unterschied, ob ein Verfahren exponentielle, polynomiale oder logarithmische Zeit braucht (nicht im täglichen Leben, aber bei großen Problemen kann das schon kritisch sein).
Man kann es ja mal für größere Werte von p versuchen.

[nezzcarth]

Man kann es ja mal für größere Werte von p versuchen.

Auf einem normalen Rechner mit einem normalen Betriebssystem passiert so viel im Hintergrund/parallel, dass es m.M.n. bei so niedrigen Zeitskalen bei einer einmaligen Messung schwierig wird, eindeutig zu sagen, wie stark der gemessene Wert mit der Berechnung zusammenhängt. Vielleicht sollte man es daher eher mit Mittelwert+Streumaß von sehr vielen Durchläufen derselben Berechnung versuchen?

[__blackjack__]

Mindestens mal sollte man das `timeit`-Modul verwenden. Und dann vielleicht auch noch mal die `pow()`-Funktion von Python benutzen. Also für alles. Die hat ein optionales drittes Argument.