Cryptography Reference
In-Depth Information
> StrongLiars := proc(n::odd)
local i, w;
if isprime(n) then
error "n is prime"
end if;
w:=[];
i:=1;
for i to n-1 do
if StrongProbablePrimeTest[i](n) then
w := [op(w), i]
end if
end do;
w
end proc:
Let us compute the strong liars for
n
=
91
=
7
·
13:
> StrongLiars(91);
[1, 9, 10, 12, 16, 17, 22, 29, 38, 53, 62, 69, 74, 75, 79, 81, 82, 90]
There are 18 strong liars for this number. Let us now consider a bigger number:
> StrongLiars(1208183);
[1, 1208182]
We see that for
n
=
1208183
=
599
·
2017, the only strong liars are 1 and
n
−
1. These are always strong liars so that, for this number, any base
b
such that
1
1 will be a witness that proves that
n
is composite. Thus, for a number
like this the strong probable prime test has an ideal behavior in the sense that a single
application of the test for any nontrivial base suffices to prove that the number is
composite. In contrast, if we submit 91 to the test with only one randomly chosen
base
b
,1
<
b
<
n
−
<
b
<
90, we have a probability equal to 18
/
88
>
1
/
5 that the number
passes the test and is declared to be a probable prime.
Exercise 6.9
Write a Maple procedure that computes the ratio between the number
of strong liars and the number of bases
b
,1
1 for a given odd composite
number. Apply this function to a sample of composite numbers in order to get an
intuitive idea of how this ratio varies.
<
b
<
n
−
In order to show that there is no analogue of the concept of Carmichael number
for the strong probable prime test, we only have to prove that, for a given
n
, not all
b
∈ Z
n
are strong liars. But we will show that a much stronger condition holds, as
follows from the following theorem, due to Monier and Rabin: the number of strong
liars cannot be more than one-fourth the number of possible bases.
Theorem 6.7
(Monier-Rabin)
If n
>
9
is an odd composite integer, then the number
of strong liars for n is at most
φ(
n
)/
4
.
=
i
=
1
p
e
i
2
s
t
, with
t
odd and let
n
Proof
Let
n
−
1
=
be the prime factorization
i
∈ Z
n
with
a
2
i
=
{
∈ N|
≡−
(
)
}
of
n
.Let
k
max
i
there exists
a
1
mod
n
(
k
is well
2
0
2
k
t
. Since
a
2
k
defined because
(
−
1
)
≡−
1
(
mod
n
)
) and set
m
=
≡−
1
(
mod
n
)
,
we also have
a
2
k
≡−
1
(
mod
p
i
)
for each
i
=
1
...
j
and, by Proposition 2.6,
Z
p
i
is precisely 2
k
+
1
. Thus 2
k
+
1
the order of
a
mod
p
i
in
|
p
i
−
1 by Corollary
