Tonelli-Shanks-Algorithmus Laufzeit (Anzahl der Iterationen) Berechnen von Quadratwurzeln mod p

Question

Wie verhält sich die Laufzeit (Anzahl Iterationen) des Tonelli-Shanks-Algorithmus zu n bzw. p?

Habe in Google folgenden Zusammenhang gefunden:

O(log⁴ p).

Bin mir bei dieser Schreibweise nicht sicher, wie zu berechnen.

Wie viele Iterationen ergäben sich z.B. real bei 100 Dezimalstellen grossen n bzw. p ?

Answer 1

Dies scheint eine Anschlußfrage zu https://www.mathelounge.de/105110/wurzel-aus-modulo-wie-ziehe-ich-wu… zu sein. Die dort verlinkte Wikipedia-Seite ist ein ganzer Absatz zur Laufzeit. Die groß-O-Notation http://2.hidemyass.com/ip-1/encoded/Oi8vZGUud2lraXBlZGlhLm9yZy93aWtp… gibt nur die Größenordnung der Laufzeit wieder, nicht die exakte Anzahl der Iterationen. Und irgendwie hab ich das Gefühl, dass die eigentliche Frage was ganz anderes ist.