Cryptography Reference
In-Depth Information
cpy_l (tmp_l, a_l);
mod_l (b_l, tmp_l, a_l);
cpy_l (b_l, tmp_l);
}
if (GT_L (b_l, one_l))
{
k=0;
}
return (int) k;
}
10.4.2 Square Roots Modulo
p
k
We now have an idea of the property possessed by an integer of being or not being
a quadratic residue modulo another integer, and we also have at our disposal an
efficient program to determine which case holds. But even if we know whether an
integer
a
is a quadratic residue modulo an integer
n
, we still cannot compute the
square root of
a
, especially not in the case where
n
is large. Since we are modest,
we will first attempt this feat for those
n
that are prime. Our task, then, is to solve
the quadratic congruence
x
2
≡ a
mod
p,
(10.11)
where we assume that
p
is an odd prime and
a
is a quadratic residue modulo
p
, which guarantees that the congruence has a solution. We shall distinguish
the two cases
p ≡
3mod4
and
p ≡
1mod4
. In the former, simpler, case,
x
:=
a
(
p
+1)
/
4
mod
p
solves the congruence, since
x
2
≡ a
(
p
+1)
/
2
≡ a · a
(
p
−
1)
/
2
≡ a
mod
p,
(10.12)
p
where for
a
(
p
−
1)
/
2
≡
1mod
p
we have used property (vi) of the Legendre
symbol, the Euler criterion, cited above.
The following considerations, taken from [Heid], lead to a general procedure
for solving quadratic congruences, and in particular for solving congruences of
the second case,
p ≡
1mod4
:Wewrite
p −
1=2
k
q
, with
k ≥
1
and
q
odd, and
we look for an arbitrary quadratic nonresidue
n
mod
p
by choosing a random
≡
number
n
with
1
≤ n<p
and calculating the Legendre symbol
p
. This has
value
1
with probability
2
, so that we should find such an
n
relatively quickly.
−
