Cryptography Reference
In-Depth Information
PROOF
Let
p
be a prime factor of
n
and let
e
be the highest power of
dividing
r
.Let
b ≡ a
(
n−
1)
/
e
(mod
p
). Then
b
e
≡
1(mod
p
)and
b
e−
1
≡ a
(
n−
1)
/
≡ a
n−
1
≡
1(mod
p
)
,
since gcd
a
(
n−
1)
/
1
,n
= 1. It follows that the order of
b
(mod
p
)is
e
.
−
Therefore,
e
1. Since this is true for every prime power factor
e
of
r
,we
|
p
−
have
r
|
p
−
1. In particular,
≥
√
n.
If
n
is composite, it must have a prime factor at most
√
n
.Wehaveshown
this is not the case, so
n
is prime.
p>r
REMARK 7.2
A converse of Proposition 7.1 is true. See Exercise 7.3.
Example 7.2
Let
n
= 153533. Then
n −
1=4
·
131
·
293. Let
r
=4
·
131. The primes
dividing
r
are
=2and
= 131. We have
≡
1(mod
n
)and gcd
2
(
n−
1)
/
2
−
1
,n
=1
,
2
n−
1
so we can take
a
2
=2. Also,
≡
1(mod
n
)and gcd
2
(
n−
1)
/
131
−
1
,n
=1
,
2
n−
1
so we can take
a
131
= 2, also. The hypotheses of Proposition 7.1 are satisfied,
so we have proved that 153533 is prime. The fact that
a
2
=
a
131
can be
regarded as coincidence. In fact, we could take
a
2
=
a
131
=
a
293
=2,which
shows that 2 is a primitive root mod 153533 (see Appendix A). So, in a sense,
the calculations for the Pocklington-Lehmer test can be regarded as progress
towards showing that there is a primitive root mod
n
(see Exercise 7.3).
Of course, to make the proof complete, we should prove that 2 and 131 are
primes. We leave the case of 2 as an exercise and look at 131. We'll use the
Pocklington-Lehmer test again. Write 130 = 2
·
5
·
13. Let
r
= 13, so we have
only one prime
,namely
= 13. We have
(mod 131) and gcd
2
10
1
,
131
=1
.
2
130
≡
1
−
Therefore, we can take
a
13
= 2. The Pocklington-Lehmer test implies that
131 is prime. Of course, we need the fact that 13 is prime, but 13 is small
enough to check by trying possible factors.
We can compactly record the proof that an integer
n
is prime by stating
the values of the prime factors
of
r
and the corresponding integers
a
.We
Search WWH ::
Custom Search