Cryptography Reference
In-Depth Information
p
e
with
e
=
=
≥
Finally, if
j
1 then
n
is a prime power,
n
2. By Proposition 2.4,
Z
p
e
whose order divides
p
e
−
J
consists of the elements of
1. By Corollary 2.1, the
|Z
p
e
p
e
p
e
−
1
orders of these elements also divide
|=
φ(
)
=
(
p
−
1
)
. Hence
J
consists
Z
p
e
whose order divides gcd
p
e
−
1
p
e
of the elements of
(
−
1
,
(
p
−
1
))
=
p
−
1.
Z
p
e
, which exists by Theorem 2.19. Then, using Proposition
Let
g
be a generator of
g
p
e
−
1
(
Z
p
e
2.5 we see that
J
=
and hence
|
J
|=
p
−
1. Therefore,
:
J
)
=
|Z
p
e
|
/
|
p
e
−
1
p
e
−
1
4 except when
p
e
J
|=
(
(
p
−
1
))/(
p
−
1
)
=
≥
=
9. Since we
are assuming that
n
>
9, the proof is complete.
Z
n
. (Hint: Use Maple
to show that 65 is the smallest odd composite
n
such that there are elements
b
1
,
Exercise 6.10
Show that
S
(
n
)
is not necessarily a subgroup of
b
2
∈
(
)
∈
(
)
S
n
with
b
1
b
2
mod
n
S
n
).
Remarks 6.1
1. Note that, for any odd composite integer
n
, the number of strong liars is always
≤
(
n
−
1
)/
4. Indeed, by Theorem 6.7 we know that this number is actually
≤
φ(
n
)/
4if
n
>
9. The only case not covered by the theorem is when
n
=
9, for
which
φ(
9
)
=
6 and
|
S
(
9
)
|=
2 because:
> StrongLiars(9);
[1, 8]
In this case the assertion of the theorem does not hold—this is the reason why the
hypothesis
n
>
|
(
)
|≤
(
−
)/
4 is verified, so
that this weaker form of the theorem indeed holds for all odd composite integers.
2. The bound
9 was required—but we see that
S
n
n
1
φ(
n
)/
4 on the size of
S
(
n
)
is attained for
n
=
15 and for
n
=
91. In
the first case,
φ(
15
)/
4
=
2 and there are always at least two strong liars (1 and
−
1), so that we have that
S
(
15
)
={
1
,
14
}
. In the second case, we have seen that
|
4. But, as we shall indicate below, this bound is not tight
and is very far from giving a good estimate of the value of
S
S
(
91
)
|=
18
=
φ(
91
)/
(
n
)
when
n
grows
large.
3. Theorem 6.7 (and also Theorem 6.6) shows that a primality test may be obtained
from the strong probable prime test. Indeed, given an odd integer
n
we select
n
−
1
. In fact, a smaller number suffices
because we are not including the trivial bases 1 and
n
different bases in the interval
[
2
,
n
−
2
]
4
−
1 and, moreover,
n
might
be replaced by
except that, of course, if we are testing
n
for primality, we
do not know the exact value of
φ(
n
)
(although we might know an approximation
sufficient for our purposes). We then submit
n
to the strong probable prime test
for each of these bases. Then:
φ(
n
)
a. If
n
fails any of these tests, we stop and declare
n
composite (because of
Theorem 6.6).
b. If
n
passes all these tests, then
n
is declared prime (because of Theorem 6.7).
This will always produce the correct result but has an important drawback: the
test is highly inefficient. The running time of this test may be analyzed as follows.
In the worst case, performing the strong probable prime test amounts to a binary
