Cryptography Reference
In-Depth Information
Quadratwurzeln in der Rechnung modulo p
Für das Beispiel der Rechnung modulo 7 mit GF(7) können wir die Wurzeln der Elemente a
aus Tab. 4-2 entnehmen. Für die Elemente in der Zeile a
2
stehen die Wurzeln darüber in der
Zeile a
1
. In der Zeile a
2
finden wir außer der 0 nur die Elemente 1, 2 und 4, und diese je zwei-
mal. Das bedeutet, es gibt Elemente, die keine Wurzel besitzen, und andere Elemente, die je
zwei Wurzeln besitzen. Die Elemente 1, 2, und 4 werden in der Arithmetik modulo 7 als
Quadratische Reste
oder als
Quadratzahlen
bezeichnet. Die Elemente 3, 5 und 6 sind in modu-
lo 7
Quadratische Nichtreste
.
In Tab. 4-6 findet sich für die Arithmetik modulo 7 eine Aufstellung der Quadratzahlen und
ihrer Wurzeln.
Tab. 4-6: Wurzeln in der Arithmetik modulo 7
a
Wurzel a
1
1, 6
6=7-1
2
3, 4
4=7-3
4
2, 5
5=7-2
Für n=p=7 ist die Berechnung der Wurzeln sehr einfach. Wir sehen in Tab. 4-2, dass die Zeilen
für a
2
und a
8
gleich sind. Die Zeile a
8
ist allgemein die Zeile a
p+1
.
kann die Wurzel a aus a
2
berechnet werden.
2 p 1
aa( d )
Aus der Kongruenz
(p 1)/ 2
2
(p 1)/ 4
a
(
a
) mod p
(
(a )
) mod p
für
(p) mod 4
3
(4.1-19)
Durch die Wurzeloperation kommt das „±“ in den Ausdruck. Ein negativer Wert „-x“ bedeutet
in mod p den additiv inversen Wert n-x. Die Formel (4.1-19) ist nur anwendbar, wenn der
Modul p durch 4 dividiert den Rest 3 ergibt. (Das gilt für die Hälfte aller ungeraden Zahlen,
denn der Rest kann nur 3 oder 1 sein.)
Das Wurzelelement a erhalten wir damit aus a
2
, indem wir a
2
mit (p+1)/4 potenzieren! In unse-
rem Beispiel ist (p+1)/4=(7+1)/4=2, d.h. „Wurzel ziehen mittels Quadrieren“. Als Beispiel
erhalten wir zu a
2
=4 das Wurzelelement a ±4
2
±2 2 bzw. 5 (mod 7).
Prüfung auf quadratischen Rest
Einem Element b sieht man nicht an, ob es ein quadratischer Rest b=a
2
ist (eine Quadratzahl)
oder ein quadratischer Nichtrest. Man könnte auf b einen Wurzel-Algorithmus anwenden und
durch Quadrieren prüfen, ob das Ergebnis eine Wurzel war.
In dem Beispiel von Tab. 4-2 fällt auf, dass die Zeile für a
3
genau an den Positionen eine 1
enthält, für die das Element a (in der Zeile a
1
) ein quadratischer Rest ist. Und dass die Zeile für
a
3
genau an den Positionen eine 6 enthält (das ist in mod7 eine 1), für die das Element a ein
quadratischer Nichtrest ist. Dieses Merkmal für quadratische Reste wird durch die Jacobi-
Funktion beschrieben.
1
falls x ein quadratischer Re st in GF(p)
.
(p 1)/ 2
J(x, p)
(x
) mod p
/
(4.1-20)
1
falls x ein quadratischer Nicht r e st in GF(p)
0
