Quadratwurzeln in Fp

4.4 Quadratwurzeln in $Fp$

4.4.1 Vorbetrachtungen

Das Bestimmen der Quadratwurzel kann man im Körper $F p$ recht effizient mit dem TONELLI-SHANKS Algorithmus erledigen. Bevor man aber dazu übergehen kann den Algorithmus zu erläutern, muß man sich unbedingt über einige Fakten in Bezug auf das Quadrieren von Körperelementen klar werden. Ohne wesentlich an Allgemeinheit zu verlieren, betrachten wird dazu die multiplikative Gruppe $ℤ∗p = (ℤp∖ {0})$ und formulieren zuerst die folgenden Grundaussagen in Bezug auf:⁶⁰

2 y= x (mod p )

Aus der Beziehung $2 y= x (mod p )$ ersieht man sofort, daß immer zwei Elemente $′ x,x$ genau zum selben $y$ führen – ein „Positives“ und ein „Negatives“: $x′ ≡ − x (mod p )$ .
Da $ℤ∗ p$ genau $p − 1$ Elemente enthält (besitzt die Ordnung $|ℤ ∗|= |ℤ |− 1= p − 1 p p$ ), können $(p − 1)∕2$ Elemente $∗ y ∈ ℤp$ keine Quadratwurzel besitzen. Denn umgekehrt betrachtet sind ja die verfügbaren $p − 1$ Elemente $x$ wegen der Paarbildung beim Quadrieren (welche zu $(p− 1)∕2$ Elementen $y$ führt) schon „aufgebraucht“.
Für die $(p − 1)∕2$ Elemente $y$ , welche der Beziehung $2 y= x (mod p)$ genügen, gilt wegen des kleinen Satzes von FERMAT (vgl. Abschnitt 3.3.2):
$p−12- 2 p−21- p− 1 y = (x ) = x ≡ 1 (mod p).$ (4.19)
Für die restlichen Elemente , welche keine zugeordnete Quadratwurzel besitzen, gilt hingegen:⁶¹
$y p−21-≡ − 1 (mod p).$ (4.20)

Für einen kurzen Beweis nehmen wir uns ein bestimmtes (konstantes) Element $y$ heraus und betrachten die Zerlegung $y= ax (mod p)$ , welche es in $∗ ℤp$ immer geben muß: $a = x−1y (mod p)$ . Wenn man nun für $x$ alle möglichen Werte $1...p− 1$ setzt, dann muß auch $a$ entsprechend variieren. Wegen:
- der Abgeschlossenheit der Multiplikation;
- der Eindeutigkeit des Inversen;
- und der Kommutativität von Elementen
in $ℤ∗p$ wird $a$ einerseits alle möglichen Werte $1...p− 1$ annehmen und andererseits wird jedes Produkt $ax$ insofern doppelt vorkommen, daß $a$ und $x$ nur die Rolle getauscht haben. In Abbildung 4.1 sind mögliche Produkte für $y= 8$ (hat keine Wurzel) und $y = 9$ (Wurzeln sind $± 3$ ) beispielhaft in $ℤ ∗ 11$ dargestellt (wobei gestrichelte Linien Produkte kennzeichnen, bei denen $a$ und $x$ nur die Rolle getauscht haben).
(a) $y= 8$ (b) $y= (±3 )2= 9$

Abbildung 4.1: Beispiele für Produkte in $ℤ∗11$

Multiplizieren wir alle Produkte $ax$ miteinander und schließen dabei die Doppelungen aus (d. h. berücksichtigen nur die Produkte in Abbildung 4.1a, welche mit durchgezogenen Linien dargestellt sind), dann hat man alle Elemente $x∈ ℤ∗p$ miteinander multipliziert.
$p−1 p−1 p−1 -2- -2- 2-- p−1 ∏ aixi = ∏ ai⋅∏ xi = ∏ xi = (p − 1)! i=1 i=1 i=1 i=1$

Bei den $(p − 1)∕2$ Produkten $a x i i$ handelt es sich aber genau um die Potenz
$p−1 p−12- p−21- y 2--= ∏ yi = ∏ aixi i=1 i=1$

und so kann man mit dem Satz von WILSON (siehe Formel 3.7) den Beweis abschließen:
$p−21- y = (p − 1)!≡ − 1.$

Noch bevor man also versucht die Quadratwurzel $√ - x= y$ zu berechnen, kann man mit Hilfe des gerade eingeführten (EULER-) Kriteriums prüfen, ob diese überhaupt existiert. Die Nomenklatur für das EULER-Kriterium stammt allerdings von A.-M. LEGENDRE und wird als LEGENDRE-Symbol bezeichnet:

( ) { y p−1 1 wenn y eine Quadratwurzel in ℤp besitzt; p- = y 2 = − 1 wenn y keine Quadratwurzel in ℤ besitzt. p

(4.21)

4.4.2 Der Spezialfall $p mod 4 = 3$

Im speziellen Fall $p≡ 3 (mod 4)$ kann man eine sehr einfache Lösung für die Quadratwurzel $√- x = y$ erhalten, sofern sie denn existiert [Ros99, Theorem 9.3], [ANS05, D.1.4]:

s+1 x= y (mod p ),

(4.22)

mit $s= (p− 3)∕4$ .

Ausgangspunkt für einen kurzen Beweis könnte die folgende Darstellung für das Modul $p$ sein:⁶²

Wird sie im Zusammenhang mit dem EULER-Kriterium von Gleichung 4.19 angewendet, dann bestätigt sich Formel 4.22 wiefolgt:

p−1- x2 = y2(s+1) = y ⋅y2s+1 = y ⋅y 2 ≡ y (mod p).

4.4.3 Der TONELLI-SHANKS Algorithmus

Idee Der TONELLI-SHANKS Algorithmus nach [Ton91, Sha73] reduziert, ausgehend von einem Anfangswert $x0 ∈ ℤp>2$ , den Exponenten $2ti$ im Ausdruck

t (x2i)2 i -y ≡ 1 (mod p)

(4.23)

immer weiter, bis schließlich $tn = 0$ wird und deshalb $2 xn ≡ y (mod p)$ die gesuchte Lösung darstellt (siehe z. B. auch [NZM91, 2.9], [CP05, 2.3.2]). Mit $2ti$ soll es sich aber nicht um irgendeine Zweierpotenz handeln, sondern um die Ordnung des Elements $zi ≡ x2iy− 1 (mod p)$ .

Es gilt also einen Algorithmus zu beschreiben, bei dem sowohl für den Startwert $z0$ als auch für alle Werte $zi$ in

z2ti≡ 1 (mod p) i

(4.24)

die Ordnung $ti |zi|= 2$ einerseits (und überhaupt) eine Zweierpotenz ist und andererseits (auch noch) abnimmt.⁶³

Startwerte Als Anfangswerte setzt man:

Dabei entspricht der Wert $′ 2t0$ nicht zwingendermaßen der Ordnung $|z0|= 2t0$ , er befriedigt aber Kongruenz 4.24 grundsätzlich:

Da es sich bei $p$ um eine Primzahl mit $p> 2$ handeln soll ( $p$ ist zwingendermaßen ungerade), kann man
$p − 1 = 2rs$ (4.25)

setzen (mit $r ≥ 1$ , maximal) und erhält so:
$p−-1-= 2r−1s. 2$
Soll die Quadratwurzel $√ - x = y$ wirklich existieren (wovon wir ausgehen) dann gilt mit dem EULER-Kriterium 4.21: $( ) y- = yp−21-≡ 1 (mod p). p$
Faßt man beide Punkte zusammen, dann bestätigt sich:
$′ ( 2)2r−1 ( s+1)2r−1 z2t0 = x0 = y--- ≡ y2r−1s ≡ yp−21≡ 1 (mod p). 0 y y$ (4.26)

Interpretieren wir Kongruenz 4.26 jetzt mit dem Wissen aus Abschnitt 2.1.2, dann muß es sich bei $2t′0$ entweder um die Ordnung $|z0|$ selbst oder aber um ein Vielfaches davon handeln: $2t′0 = K |z0|$ . Deshalb können $K$ und $|z0|$ nur Zweierpotenzen sein (was $K = 1$ nicht ausschließt), d. h. für die Ordnung kann man ohne weitere Bedenken $|z |= 2t0 0$ ansetzen (mit $t ≤ t′ 0 0$ ). Um nun aus $t′ 0$ den exakten Exponenten $t0$ bzw. die Ordnung $|z0|$ zu ermitteln, kann man $z0$ einfach so oft quadrieren bis (nach FERMAT’s kleinem Satz) die Bedingung $|z| z00 ≡ 1 (mod p)$ erfüllt ist.

Iteration Bevor wir zum iterativen Teil des Algorithmus übergehen können, benötigen wir noch die Mithilfe irgendeines (zufällig gewählten) Elements $α ∈ ℤp$ , welches keine Wurzel in $∗ ℤ p$ haben darf. Für $α$ muß das EULER-Kriterium 4.21 dann den Wert

( ) α- ≡ − 1 (mod p) p

annehmen. Aus diesem Element $α$ erzeugen wir ein neues Element $β = αs (mod p)$ mit den Eigenschaften:

potenziert zu $2r$ ergibt sich mit FERMAT’s kleinem Satz: $r r β2 = α2 s = αp −1 ≡ 1 (mod p );$
aus dem EULER-Kriterium für $α$ läßt sich schlußfolgern:
$2r−1 2r−1s p−21 β = α = α ≡ − 1 (mod p).$ (4.27)

Nun wird die Näherung schrittweise nach folgender Vorschrift verbessert:⁶⁴

2r−ti−1 xi+1 = xiβ (mod p ),

(4.28)

wobei sich der Exponent $ti$ jeweils um $1$ verringert ( $t′i+1 = ti− 1$ , mit $2t′i+1$ einem mglw. Vielfachen der Ordnung $|zi+1|$ ).

Um die Verringerung des Exponenten nachzuweisen bilden wir einfach $t−1 z2ii+1$ mit Hilfe von Iterationsformel 4.28:

′ t′ ( )2ti−1 t−1( )2ti−1 z2ti+i+11= (x2i+1y− 1)2 i+1 = x2iβ 2⋅2r−ti−1y−1 = (x2iy−1)2i β 2r−ti = z2iti−1β 2r−1 (mod p).

Beide Faktoren auf der rechten Seite sind aber vom Wert $− 1 (mod p )$ , was letztlich

t′ z2i+i+11≡ 1 (mod p )

bedeutet. Zur Begründung folgende Argumentation:

$2r−1 β ≡ − 1 (mod p)$ gilt wegen des EULER-Kriteriums für $α$ (siehe Kongruenz 4.27).
Der Beweis für $z2ti−1≡ − 1 (mod p) i$ stützt sich auf die Darstellung: $( ) z2ti= z2ti−1 2, i i$

welche ja bei jeder Iteration als $+ 1 (mod p)$ vorausgesetzt wird. Aus diesem Grund kann der Wert innerhalb des Klammerausdrucks nur $+ 1$ oder $− 1$ sein [NZM91, Hilfssatz 2.10]. Wenn $t 2i$ aber die Ordnung von $zi$ derstellt, dann muß $ti$ der kleinste Wert sein, welcher zu $t z2ii≡ +1 (mod p)$ führt. Deshalb kann $2ti−1$ nicht (ebenfalls) die Ordnung von $zi$ sein und es bleibt nur die Schlußfolgerung: $z2iti−1≡ − 1 (mod p)$ .

Aus dem letzten Punkt ergibt sich die Notwendigkeit, daß man am Anfang des Iterationszyklus jedesmal die exakte Ordnung $|zi|$ bzw. den zugehörigen Exponenten $ti ≤ ti′$ bestimmt (vgl. auch die Erläuterungen zu den Startwerten).

Algorithmus Bevor wir in Algorithmus 7 alle Erkenntnisse zusammenfassen, noch zwei Hinweise zur Umsetzung:

Die Berechnung des inversen Elements $y− 1$ kann man einmalig zu Beginn des Algorithmus durchführen.
Setzt man für die Reduktion der Ordnung in jedem Schritt $Δi = ti− 1− ti$ und führt in Formel 4.28 die Abkürzungen

ein, dann kann man auch $γi$ rekursiv berechnen:
$( )2Δi γi = β2r−ti−1−1+Δi = β2r−ti−1−1 = γ2Δi. i−1$

Um den korrekten Startwert $r−t−1 γ0 = β2 0$ zu erzielen, vergleichen wir jetzt noch die Werte für $i = 0$ :
$β2r−1−t0 = γ2−Δ10= γ2−t−11−t0$

und erhalten:

Algorithmus 7: Quadratwurzel eines Elements $y∈ ℤp$

Require: $p > 2$ Ensure: $√ - x = y$ $r,s⇐$ aus $r p− 1 = 2 s$ , mit $r$ maximal
repeat
$α ⇐$ zufälliges Element aus $ℤp$
until $α(p−1)∕2 mod p= p − 1$ {EULER-Kriterium: $α (p−1)∕2 ≡ − 1 (mod p)$ }
$γ ⇐ αs mod p$ { $γ−1 = β$ }
$(s+1)∕2 x ⇐ y mod p$ { $x0$ }
$yinv = y− 1 mod p$
$t′ ⇐ r− 1$
$t ⇐$ aus $t 2 2 = ord(x yinv mod p )$ {Ordnung von $z0$ }
while $t > 0$ do
$Δ ⇐ t′− t$
$2Δ γ ⇐ γ mod p$ { $2r−ti−1 γi = β$ }
$x ⇐ xγ mod p$
$′ t ⇐ t$
$t$ aus $2t = ord(x2yinv mod p)$ {Ordnung von $zi ≡ x2iy−1 (mod p)$ }
end while {Probe (siehe auch [DM11, Appendix C]),
anstatt zu Beginn das EULER-Kriterium $(y|p)= 1$ zu verifizieren}
$′ 2 y ⇐ x mod p$
if $y′ = y$ then
return $y$
else
return keine Lösung
end if