Cryptography Reference
In-Depth Information
Algorithm for calculating square roots of an integer
a
modulo an odd prime
p
1=2
k
q
,
q
odd. Choose random numbers
n
until
p
=
1.
Write
p
−
−
1
.
a
(
q
−
1)
/
2
mod
p
,
y
n
q
mod
p
,
z
x
2
mod
p
,
x
2.
Set
x
←
←
←
a
·
←
a · x
mod
p
,and
r ← k
.
3.
If
z ≡
1mod
p
, output
x
and terminate the algorithm. Otherwise, find
the smallest
m
for which
z
2
m
≡
1mod
p
.If
m
=
r
, then output the
information that
a
is not a quadratic residue
p
and terminate the algorithm.
4.
Set
t ← y
2
r
−
m
−
1
mod
p
,
y ← t
2
mod
p
,
r ← m
mod
p
,
x ← x · t
mod
p
,
z ← z · y
mod
p
, and go to step 3.
It is clear that if
x
is a solution of the quadratic congruence, then so is
x
2
mod
p
.
Out of practical considerations in the following implementation of the search
for a quadratic nonresidue modulo
p
we shall begin with 2 and run through all the
natural numbers testing the Legendre symbol in the hope of finding a nonresidue
in polynomial time. In fact, this hope would be a certainty if we knew that the
still unproved extended Riemann hypothesis were true (see, for example, [Bund],
Section 7.3, Theorem 12, or [Kobl], Section 5.1, or [Kran], Section 2.10). To the
extent that we doubt the truth of the extended Riemann hypothesis the algorithm
of Shanks is probabilistic.
For the practical application in constructing the following function
proot_l()
we ignore these considerations and simply expect that the calculational time is
polynomial. For further details see [Cohe], pages 33 f.
x
)
2
−
x
mod
p
, since
(
−
≡
compute the square root of
a
modulo
p
Function:
int proot_l (CLINT a_l, CLINT p_l, CLINT x_l);
Syntax:
a_l, p_l
(operands,
p_l
>
2
aprime)
Input:
x_l
(square root of
a_l
modulo
p_l
)
Output:
0if
a_l
is a quadratic residue modulo
p_l
−
1
otherwise
Return:
