Cryptography Reference
In-Depth Information
listing of the function and noting that it calls the built-in command
gmp_isprime
.
This is a function from the
GNU Multiple-Precision Bignum Library (GMP)
and, as
can be seen in the documentation of this library or by inspecting the code (available
at
http://gmplib.org/
)
, it is just an implementation of the Miller-Rabin test. But wait,
we have used
isprime
to provide us with the numbers required by the experiments
with Miller-Rabin, so it seems that we are trapped in a kind of vicious circle here
... However, this does not invalidate these experiments because it is known that
for the rather small numbers that we used in them,
isprime
always provides the
correct answer. Moreover, even if
isprime
gave some erroneous results, the rough
comparisons we made for different number of bases and for numbers of different
size would still be meaningful.
The Lucas probable prime tests and their generalizations (not to be confused with
the Lucas-Lehmer test which is deterministic and very inefficient except in particular
cases) are described in [60] and [194] and they are often used in conjunction with
Miller-Rabin because it is believed that these tests are in some sense independent
and hence the probability that a composite number passes both tests should be very
small. In fact, Pomerance, Selfridge and Wagstaff made in [159] the conjecture that
no odd composite positive integer is both a strong pseudoprime to the base 2 and a
Lucas pseudoprime for a certain choice of parameters (see, e.g., [194, p. 165]). In
1980, Pomerance, Selfridge and Wagstaff offered $30 for a proof or disproof of this
conjecture. They later raised the prize to $620 so that this question became known
as the “$620
problem
”.
More recently, the challenge has been simplified and it consists in finding a num-
ber
n
≡±
(
)
that is simultaneously a base-2 (Fermat) pseudoprime and a
Fibonacci pseudoprime (a special kind of Lucas pseudoprime; see below for the def-
inition). A peculiar thing is that the prize money came from the three authors, but not
equally: Selfridge offered $500, Wagstaff offered $100 and Pomerance offered $20
for finding such an
n
and they also agreed to pay $620, with Pomerance and Selfridge
reversing their roles, for a proof that no such
n
exists (see [60, Research Problem3.41,
p. 168]). It is clear that this uneven distribution of the reward money to be paid was a
reflection of the authors' feelings about the most likely outcome. In fact, Pomerance
has an (unpublished) heuristic argument written in 1984 that suggests that, even for
the stronger version of the problem, there is an infinite number of counterexamples
n
that pass these tests without being prime. This argument is available from the web
page of Grantham [95], where there is also a list of primes compiled by Alford and
Grantham that may be helpful in solving the problem. Grantham strongly believes
that some sub-product of these primes is a Carmichael number and a Fibonacci
pseudoprime that is also
2
mod 5
.
Let us sketch a naive attack on the $620 problem using the Alford-Grantham list
of primes. First we define a Fibonacci pseudoprime. Let
F
0
=
≡
2or
≡
3
(
mod 5
)
0
,
F
1
=
1
,...
F
i
=
F
i
−
1
+
F
i
−
2
be the sequence of Fibonacci numbers. An integer
n
such that
n
≡
±
is called a
Fibonacci pseudoprime
when it is composite and divides
F
n
+
1
. Thus we are looking for a composite number
n
that is simultaneously a 2-
pseudoprime and a Fibonacci pseudoprime
2
(
mod 5
)
≡±
2
(
mod 5
)
. Such a number should
pass a test composed of the following ingredients:
