Verallgemeinerung von Shanks-Tonelli

26/12/2008 - 01:25 von Tobi J | Report spam
Hallo Gruppe,

um Quadratwurzeln mod p (bzw. allgemein in endlichen zyklischen Gruppen)
zu berechnen eignet sich der Tonelli-Shanks Algorithmus. Ich referenziere
hier mal die englische Wikipedia:

http://en.wikipedia.org/wiki/Shanks..._algorithm

Die Wikipedia-Seite und zahlreiche google-results behaupten, dass der
Algorithmus auch auf k-te Wurzeln verallgemeinert werden kann. Ich
bekomme diese Verallgemeinerung jedoch nicht hin... Es scheitert unter
Anderen an folgendem Schritt (in der Notation aus dem Wikipedia-Artikel):

3. Let R = n^((Q+1)/2)

Hier teilt man ja im Falle für Quadratwurzeln durch 2. Wenn man aber k-te
Wurzeln ziehen will muss ja Q+1 nicht notwendig ein ganzzahliges
Vielfaches von k sein...

Kann mir jemand auf die Sprünge helfen (oder eine Referenz angeben, ich
finde über google etc. nix) wie der Algorithmus es für allgemeine k-te
Wurzeln aussieht?

Danke & LG

Tobi
 

Lesen sie die antworten

#1 Wolfgang Thumser
26/12/2008 - 13:45 | Warnen spam
Hallo Tobi,

Hier teilt man ja im Falle für Quadratwurzeln durch 2. Wenn man aber k-te
Wurzeln ziehen will muss ja Q+1 nicht notwendig ein ganzzahliges
Vielfaches von k sein...

Kann mir jemand auf die Sprünge helfen (oder eine Referenz angeben, ich
finde über google etc. nix) wie der Algorithmus es für allgemeine k-te
Wurzeln aussieht?



ich habe in einem Programmierpraktikum einmal diese Aufgabe gestellt, und
es existiert auch eine Implementierung in Python, die selbst mit hundert stelligen
Primzahlen noch problemlos umgehen kann. Allerdings befinden sich die Unterlagen im
Buero, und ich muss sie erst zusammen suchen.

In der Zwischenzeit kannst Du Dir zum Warmwerden einmal ueberlegen, wie man
in einer zyklischen Gruppe der Ordnung n die k-te Wurzel zieht, wenn
n und k teilerfremd sind (das ist naemlich der einfachere Fall, und dieser
ist anders zu behandeln als der Fall n = p-1 mit p prim und k = 2, da hier
k die Gruppenordnung n ja teilt).

Gruss Wolfgang

Ähnliche fragen