0 Daumen
241 Aufrufe

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

Habe in Google folgenden Zusammenhang gefunden:

O(log4 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 ?

von

1 Antwort

0 Daumen
Dies scheint eine Anschlußfrage zu https://www.mathelounge.de/105110/wurzel-aus-modulo-wie-ziehe-ich-wurzel-aus-modulo?show=10511 zu sein. Die dort verlinkte Wikipedia-Seite ist ein ganzer Absatz zur Laufzeit. Die groß-O-Notation http://2.hidemyass.com/ip-1/encoded/Oi8vZGUud2lraXBlZGlhLm9yZy93aWtpL0xhbmRhdS1TeW1ib2xl 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.
von 1,1 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
+1 Punkt
2 Antworten
Gefragt 29 Apr 2013 von Gast
0 Daumen
1 Antwort
Gefragt 10 Apr 2013 von Gast
0 Daumen
0 Antworten

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...