Cryptography Reference
In-Depth Information
xy
p
=
x
p
y
p
·
This fact directly results from Euler's criterion:
xy
p
(
xy
)
p
−
1
≡
(mod
p
)
2
x
p
−
2
y
p
−
1
≡
(mod
p
)
2
x
p
−
1
(mod
p
)
y
p
−
2
(mod
p
)
≡
2
x
p
y
p
=
·
For example,
6
7
=
2
7
3
7
=1
·
·
(
−
1) =
−
1
.
In fact, 6 is a quadratic nonresidue (i.e., 6
∈
QNR
7
). Furthermore, for any
∈
Z
p
, it holds that
x
p
=1.
There is an efficient randomized algorithm that on input prime
p
and
x
x
∈
Z
p
tests whether
x
is a quadratic residue and, if so, returns the two square roots of
x
.
Things are getting even simpler if one assumes
p
≡
3(mod4). In this case,
it is particularly simple to compute the square root from
x
∈
QR
p
:
y
=
x
p
+1
(mod
p
)
(3.6)
4
p
+1
4
The expression makes sense, because
p
≡
3(mod4)and hence
is an
integer. Also, it can be verified that
y
2
≡
x
(mod
p
):
(
x
p
+
4
)
2
(mod
p
)
y
2
≡
x
p
+1
≡
(mod
p
)
2
x
p
−
1
x
2
(mod
p
)
≡
·
2
