Cryptography Reference
In-Depth Information
3
(
(
)
)
exponentiation modulo
n
and so it has complexity
O
len
n
. The number of
(
)
tests to be performed is
O
n
and hence the complexity of the test would be
3
O
(
n
len
(
n
)
)
which is exponential in the length of
n
. Even if we perform only
O
(φ(
n
))
strong probable prime tests, taking into account that, by the PNT,
φ(
n
)
=
2
which is, again,
exponential and would require more than 10
300
exponentiations to test a 1024-bit
number.
O
(
n
/
len
(
n
))
, we would have a running time of
O
(
n
len
(
n
)
)
As we have just seen, submitting an integer to a number of strong probable prime
tests sufficient to produce a primality test according to Theorem 6.7 is not feasible
because finding a witness for a composite number may require a number of tests that
grows exponentially with the size of
n
. One possible way to overcome this difficulty
is to find a tighter bound on the number of strong liars for, if we show that this number
is polynomial in the size of
n
, then the method described in the preceding remarks
would give a polynomial-time primality test. Looking at the problem from the point
of view of witnesses, if we show that the
first witness
, i.e., the least base such that a
given odd composite
n
fails the strong probable prime test, grows polynomially as
a function of the size of
n
, we have a primality test just by submitting
n
to the first
bases in increasing order until reaching one greater than the first witness.
Exercise 6.11
Write a Maple procedure that computes the smallest odd composite
whose first witness is greater than a given integer and use it to compute the smallest
composite whose first witness is one of the following values: 3, 5, 7.
The preceding exercise shows that the smallest odd composite integer
n
whose
first witness is 3 is
n
2047 and, similarly, 1373653 and 25326001 are the smallest
composites whose first witnesses are 5 and 7, respectively. This small set of data
is greatly extended in [27, Table 3.2] where, for example, it is shown that the 56-
digit number 68528663395046912244223605902738356719751082784386681071
is a strong pseudoprime for all the bases
=
≤
100. We can easily confirm that the first
witness for this number is 101, as follows:
> FirstWitness := proc(n::odd)
local b;
b:=2;
if isprime(n) then
error "%1 is prime", n
else
while StrongProbablePrimeTest[b](n) do
b:=b+1
end do;
end if;
b
end proc:
> FirstWitness(68528663395046912244223605902738356719751082784386681071);
101
The values of the ratio between ln
n
and the first witness for
n
obtained from
Bleichenbacher's data suggest the possibility that the first witness is
O
but
this has not been proved. The strongest theoretical result we have in this regard is
(
len
(
n
))
