Cryptography Reference
In-Depth Information
∈
Z
p
where
p
≥
Input
: a quadratic residue
a
3 is prime
Output
:
b
such that
b
2
≡
a
(mod
p
)
1:
repeat
2:
Z
p
at random
3:
until
g
is not a quadratic residue
4:
let
p
choose
g
∈
2
s
t
with
t
odd
−
1
=
5:
e
←
0
=
6:
for
i
2to
s
do
p
−
1
if
(
ag
−
e
)
=
mod
p
1
then
7:
2
i
e
←
2
i
−
1
+
e
8:
9:
end if
10:
end for
11:
b
g
−
t
2
a
t
+
1
←
mod
p
2
Figure 6.7.
The Tonelli algorithm for square roots in
Z
p
.
Let us first state the following theorem.
Theorem 6.6.
Let p be an odd prime number. We have
Z
p
is a quadratic residue if and only if x
p
−
1
1. x
∈
mod
p
=
1
2
p
−
1
2
quadratic residues in
Z
p
3. that if p
2.
Z
p
, the two square roots
≡
3 (mod 4)
, for any quadratic residue x
∈
of x modulo p are x
p
+
1
x
p
+
1
−
mod
p and
mod
p
4
4
The last property holds only for
p
1 is a multiple of 4. For
other primes
p
, we generalize this formula by using the Tonelli algorithm in Fig. 6.7.
≡
3 (mod 4), i.e. when
p
+
Proof.
We first notice that since
Z
p
is a field, the number of possible solutions to the
polynomial equation
y
2
−
x
=
0in
y
is limited to two. For
x
=
0, we can even notice
that if
y
is a root, then
−
y
is another different root. Thus the number of solutions for
x
0 is zero or two. Due to the pigeonhole principle, we infer that all elements of
Z
p
will be mapped onto the set of all quadratic residues by the square operation as
a two-to-one mapping. This proves the second property, namely we have exactly
p
−
1
2
quadratic residues in
Z
p
. To prove the first property, we notice that if
x
is a quadratic
residue, we can write
x
=
y
2
=
mod
p
. Then we have
x
p
−
1
y
p
−
1
≡
≡
1
(mod
p
)
.
2
Thus all quadratic residues are roots of the equation
x
p
−
1
p
−
1
2
≡
1. Since we have exactly
2
p
−
1
2
quadratic residues and at most
roots, this shows that all roots are quadratic residues.
x
p
+
1
The third property is straightforward: if
x
is a quadratic residue, let
y
=±
mod
4
p
.Wehave
x
p
+
1
x
p
−
2
x
y
2
≡
≡
(mod
p
)
.
2
Search WWH ::
Custom Search