Cryptography Reference
In-Depth Information
Our algorithm uses as a black box an algorithm, denoted
SQRT
, that given a prime
P
and
a quadratic residue
s
mod
P
, returns a square root of
s
mod
P
. There is no guarantee
as to what the algorithm does in case the input is not of this form (and, in particular, in
case
P
is not a prime).
Algorithm.
On input a natural number
N
>
2, do the following:
1.
If
N
is either even or an integer-power, then
reject
.
2.
Uniformly select
r
r
2
∈{
1
,...,
N
−
1
}
and set
s
←
mod
N
.
3.
Let
r
←
s
). If
r
≡±
SQRT
(
N
,
r
(mod
N
), then
accept
, else
reject
.
Analysis.
By Fact 1, on input a prime number
N
, the algorithm always accepts (since in
this case
SQRT
(
N
). On the other hand,
suppose that
N
is an odd composite that is not an integer-power. Then, by Fact 2,
each quadratic residue
s
has at least four square roots, and each is equally likely
to be chosen at Step 2 (since
s
yields no information on the specific
r
). Thus, for
every such
s
, the probability that
±
SQRT
(
N
,
s
) is chosen in Step 2 is at most
,
r
2
mod
N
)
=±
r
for any
r
∈{
1
,...,
N
−
1
}
2
4
.It
follows that on input a composite number, the algorithm rejects with probability at
least
1
2
.
Comment.
The analysis presupposes that the algorithm
SQRT
is always correct when
fed with a pair (
P
,
s
), where
P
is prime and
s
is a quadratic residue mod
P
. Such
an algorithm was described for the special case where
P
≡
3 (mod 4). Thus, when-
ever the candidate number is congruent to 3 (mod 4), which typically is the case
in our applications, this description suffices. For the case
P
≡
1 (mod 4), we em-
ploy the randomized modular square-root-extraction algorithm mentioned earlier and
observe that in case
SQRT
has error probability
ε<
1
2
, our algorithm still distin-
guishes primes from composites (since on the former it accepts with probability at least
1
1
1
2
). The statistical
difference between the two cases can be amplified by invoking the algorithm several
times.
We mention that error-free probabilistic polynomial-time algorithms for testing pri-
mality do exist [121, 1], but currently are much slower. (These algorithms output either
the correct answer or a special
don't know
symbol, where the latter is output with
probability at most
−
ε>
2
, whereas on the latter it accepts with probability at most
1
2
.)
A.1.4. On Uniform Selection of Primes
A simple method for uniformly generating a prime number in some interval, say between
N
and 2
N
, consists of repeatedly selecting at random an integer in this interval and
testing it for primality. The question, of course, is,
How many times do we need to repeat
the procedure before a prime number is found?
This question is intimately related to
the
density of primes
, which has been extensively studied in number theory [7]. For
our purposes it suffices to assert that in case the sampling interval is sufficiently large
