Cryptography Reference
In-Depth Information
We set
a
(
q
+1)
/
2
mod
p,
y
0
≡ n
q
mod
p,
z
0
x
0
≡
(10.13)
a
q
mod
p,
r
0
:=
k.
≡
Since by Fermat's little theorem we have
a
(
p
−
1)
/
2
x
2(
p
−
1)
/
2
x
p
−
1
≡
1mod
p
for
a
and for a solution
x
of (10.11), and since additionally, for quadratic
nonresidues
n
we have
n
(
p
−
1)
/
2
≡
≡
≡−
1mod
p
(cf. (vi), page 221), we have
az
0
≡ x
0
mod
p,
y
2
r
0
−
1
≡−
1mod
p,
(10.14)
0
z
2
r
0
−
1
≡
1mod
p.
0
1mod
p
,then
x
0
is already a solution of the congruence (10.11).
Otherwise, we recursively define numbers
x
i
,y
i
,z
i
,r
i
such that
If
z
0
≡
x
i
mod
p,
az
i
≡
y
2
r
i
−
1
≡−
1mod
p,
(10.15)
i
z
2
r
i
−
1
≡
1mod
p,
i
and
r
i
>r
i
−
1
. After at most
k
steps we must have
z
i
1mod
p
and that
x
i
is
a solution to (10.11). To this end we choose
m
0
as the smallest natural number
such that
z
2
m
0
≡
≡
1mod
p
,whereby
m
0
≤ r
0
−
1
. We set
0
x
i
y
2
r
i
−
m
i
−
1
x
i
+1
i
mod
p,
y
i
+1
≡ y
2
r
i
−
m
i
mod
p,
z
i
+1
≡ z
i
y
2
r
i
−
m
i
≡
(10.16)
mod
p,
i
with
r
i
+1
:=
m
i
:= min
m ≥
1
| z
2
m
≡
1mod
p
. Then
i
x
i
+1
≡ x
i
y
2
r
i
−
m
i
≡ az
i
y
2
r
i
−
m
i
≡ az
i
+1
mod
p,
i
i
y
2
r
i
−
m
i
2
m
i
−
1
y
2
r
i
+1
−
1
y
2
m
i
−
1
y
2
r
i
−
1
≡
≡
≡
≡−
1mod
p,
(10.17)
i
+1
i
+1
i
i
z
i
y
2
r
i
−
m
i
2
m
i
−
1
z
2
r
i
+1
−
1
≡ z
2
m
i
−
1
≡−z
2
m
i
−
1
≡
≡
1mod
p,
i
+1
i
+1
i
i
since
z
2
m
i
−
1
2
z
2
m
i
≡
≡
1mod
p
, and therefore by the minimality of
m
i
only
i
i
z
2
m
i
−
1
≡−
1mod
p
is possible.
We have thus proved a solution procedure for quadratic congruence, on
which the following algorithm of D. Shanks is based (presented here as in [Cohe],
Algorithm 1.5.1).
i
