0 Daumen
220 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 ?

Gefragt 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.
Beantwortet 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
...