Information Technology Reference
In-Depth Information
not grow exponentially. Evidence of the primality of the divisors can be given in the same way,
that is, by exhibiting an integer
r
j
for each prime as well as the prime divisors of
q
j
−
1for
each prime
q
j
. We must then show that all of this evidence can be given succinctly and verified
deterministically in time polynomial in the length
n
of
p
.
THEOREM
8.6.4
PRIMALITY
is in
NP
∩
coNP
.
Proof
We give an inductive proof that
PRIMALITY
is in
NP
. For a prime
p
we give its
evidence
E
(
p
)
as
(
p
;
r
,
E
(
q
1
)
,
...
,
E
(
q
k
))
,where
E
(
q
j
)
is evidence for the prime
q
j
.We
let the evidence for the base case
p
=
2be
E
(
2
)=(
2
)
.Then,
E
(
3
)=(
3
;
2,
(
2
))
because
r
=
2 works for this case and 2 is the only prime divisor of 3
−
1, and
(
2
)
is the evidence for
it. Also,
E
(
5
)=(
5
;
3,
(
2
))
.The
length
of the evidence
E
(
p
)
on
p
is the number
of parentheses, commas and bits in integers forming part of the evidence.
We show by induction that
|
E
(
p
)
|
is at most 4
log
2
p
. The base case satisfies the hy-
|
E
(
p
)
|
|
E
(
2
)
|
pothesis because
=
4.
Because the prime divisors
{
q
1
,
...
,
q
k
}
satisfy
q
i
≥
2and
q
1
q
2
···
q
k
≤
p
−
1, it follows
that
k
≤
log
2
p
≤
n
.Also,since
p
is prime, it is odd and
p
−
1 is divisible by 2. Thus,
the first prime divisor of
p
−
1is2.
Let
E
(
p
)=(
p
;
r
,
E
(
2
)
,
E
(
q
2
)
,
...
,
E
(
q
k
))
. Let the inductive hypothesis be that
4
log
2
p
.Let
n
j
=log
2
q
j
. From the definition of
E
(
p
)
we have that
|
|
satisfies the following inequality because at most
n
bits are needed for
p
and
r
,thereare
k
E
(
p
)
|≤
|
E
(
p
)
−
≤
n
−
|
E
(
2
)
|
=
4.
1
1 commas and three other punctuation marks, and
3
n
+
6
+
4
2
n
j
|
E
(
p
)
|≤
≤
j
≤
k
Since the
q
j
are the prime divisors of
p
−
1 and some primes may be repeated in
p
−
1,
1. It follows that
2
≤j≤k
n
j
≤
their product (which includes
q
1
=
2) is at most
p
−
log
2
Π
2
≤j≤k
q
j
≤
1
)
/
2
)
.Sincethesumofthesquaresof
n
j
is less than or equal
to the square of the sum of
n
j
, it follows that the sum in the above expression is at most
(log
2
p
log((
p
−
1
)
2
1
)
2
.But3
n
+
6
+
4
(
n
1
)
2
=
4
n
2
4
n
2
when
n
2.
Thus, the description of a certificate for the primality of
p
is polynomial in the length
n
of
p
.
We now show by induction that a prime
p
can be verified in
O
(
n
4
)
steps on a RAM.
Assume that the divisors
q
1
,
...
,
q
k
for
p
−
≤
(
n
−
−
−
5
n
+
10
≤
≥
1 have been verified. To verify
p
,wecompute
r
p−
1
mod
p
from
r
and
p
as well as
r
(
p−
1
)
/q
mod
p
for each of the prime divisors
q
of
p
−
1
)
/q
can be computed through
subtraction of
n
-bit numbers in
O
(
n
2
)
steps on a RAM. To raise
r
to an exponent
e
,rep-
resent
e
as a binary number. For example, if
e
=
7, write it as
p
=
2
2
+
2
1
+
2
0
.If
t
is the largest such power of 2,
t
−
1 and compare the results with 1. The integers
(
p
−
n
.Compute
r
2
j
mod
p
by squaring
rj
times, each time reducing it by
p
through division. Since each squaring/reduction step
takes
O
(
n
2
)
RAM steps, at most
O
(
jn
2
)
RAM steps are required to compute
r
2
j
.Since
this may be done for 2
≤
log
2
(
p
−
1
)
≤
t
and
2
≤j≤t
j
=
O
(
t
2
)
,atmost
O
(
n
3
)
RAM steps suffice
to compute one of
r
p−
1
mod
p
or
r
(
p−
1
)
/q
mod
p
for a prime divisor
q
.Sincethereareat
most
n
of these quantities to compute,
O
(
n
4
)
RAM steps suffice to compute them.
To complete the verification of the prime
p
,wealsoneedtoverifythedivisors
q
1
,
...
,
q
k
≤
j
≤
of
p
1. We take as our inductive hypothesis that an arbitrary prime
q
of
n
bits can be veri-
fied in
O
(
n
5
)
steps. Since the sum of the number of bits in
q
2
,
...
,
q
k
is
(log
2
(
p
−
1
)
and the sum of the
k
th powers is no more than the
k
th power of the sum, it follows that
−
1
)
/
2
−
Search WWH ::
Custom Search