Cryptography Reference
In-Depth Information
Furthermore, squaring modulo
P
is a 2-to-1 mapping of the group to the sub-
group. In case
P
3 (mod 4), each image of this mapping has one pre-image in the
subgroup (i.e., a quadratic residue) and one pre-image that is not in the subgroup (i.e.,
a non-quadratic residue).
2
≡
A.1.2. Extracting Square Roots Modulo a Prime
In general, extracting square roots module a prime can be done by using Berlekamp's
algorithm [28]. The latter is a randomized algorithm for factoring polynomials modulo
a prime. (Note that extracting a square root of
s
modulo a prime
P
amounts to solving
the equation
x
2
≡
s
(mod
P
), which can be cast as the problem of factoring the
polynomial
x
2
s
modulo
P
.)
A more direct approach is possible in the special case in which the prime is congruent
to 3 (mod 4), which is the case in most cryptographic applications. In this case we
observe that for a quadratic residue
s
≡
x
2
−
(mod
P
), we have
s
(
P
+
1)
/
4
≡
x
(
P
+
1)
/
2
(mod
P
)
≡
x
(
P
−
1)
/
2
·
x
(mod
P
)
≡±
x
(mod
P
)
where in the last equality we use Fermat's little theorem, by which
x
(
P
−
1)
/
2
≡±
1
(mod
P
) for every integer
x
and prime
P
. Thus, in this special case, we obtain a square
root of
s
modulo
P
by raising
s
to the power
P
+
1
modulo
P
. (Note that this square root
4
is a quadratic residue modulo
P
.)
A.1.3. Primality Testers
The common approach to testing whether or not an integer is a prime is to utilize
Rabin's randomized primality tester [185], which is related to a deterministic algo-
rithm due to Miller [166].
3
The alternative of using a somewhat different randomized
algorithm, discovered independently by Solovay and Strassen [202], seems less popular.
Here we present a third alternative, which seems less well known (and was discovered
independently by several researchers, one of them being Manuel Blum). The only
number-theoretic facts that we use are as follows:
1.
For every
prime P
2, each quadratic residue mod
P
has exactly two square roots
mod
P
(and they sum up to
P
).
2.
For every odd and non-integer-power
composite
number
N
, each quadratic residue
mod
N
has at least four square roots mod
N
.
>
2
This follows from the fact that
−
1 is a non-quadratic residue modulo such primes. In contrast, in case
P
≡
1
(mod 4), it holds that
−
1 is a quadratic residue modulo
P
. Thus, in case
P
≡
1 (mod 4), for each quadratic
residue the two square roots either are both quadratic residues or are both non-quadratic residues.
3
Miller's algorithm relies on the Extended Riemann Hypothesis (ERH).
