Das Zahlkörpersieb: Wurzelziehen
Aus Wikibooks
[Bearbeiten] Das Problem mit dem Wurzelziehen in Zahlkörpern
Beim Zahlkörpersieb sucht man nach Quadratzahlen in den Ringen 
und ![\mathbb{Z}[\alpha]](http://upload.wikimedia.org/math/1/c/5/1c59ea033f12a3ebb99a715bbc8ebc01.png)
. Hat man diese gefunden, so besteht die nächste Aufgabe darin, aus diesen Zahlen die Quadratwurzel zu ziehen.
Im Falle von ist dies kein Problem, da die Quadratzahl als Produkt von Primzahlen gegeben ist. Im Falle des speziellen Zahlkörpersiebs ist das Wurzelziehen auch für den Ring kein Problem, da hier ebenfalls die Primfaktorzerlegung bekannt ist.
Ganz anders sieht dies im Falle des allgemeinen Zahlkörpersiebs aus. Hier ist die Information über die Primfaktorzerlegung in nicht vorhanden. Das einzige, was man gegeben hat, ist die Darstellung
,
mit Zahlen a + bα aus .
Um nun γ zu berechnen, kann man das Produkt auf der rechten Seite ausrechnen und dann das Polynom X2 - γ2 faktorisieren. Das Problem hierbei ist, dass die Zahl γ2 sehr groß ist.
Um diese großen Zahlen zu vermeiden, hat J.-M. Couveignes ([Cou91]) ein Verfahren entwickelt, welches für Zahlkörper mit ungeradem Grad ohne diese auskommt.
