Lucas Lehmer Complexity Problem
Lucas Lehmer Complexity Problem
GIMPS recently discovered a prime number containing more than 10 million digits with a prize of $100,000. See:
The number found was 243,112,609-1. How many decimal digits is that? Solve 10d = 243,112,609. Take logs to the base 10 to get d = 43112609 log102 = 12978188, almost 13 million digits. Numbers of the special form 2n – 1 are easier to test for primeness than for general numbers, by using the Lucas Lehmer algorithm.
LucasLehmer(n):
s 4
for i 0,…,n-2 do
s ( s2 -2 ) mod 2n – 1
if s = 0
output prime
else
output not prime
Example: for n = 7 the values of s are 4, 14, 67, 42, 111, 0, so 27-1 = 127 is prime.
What is the time complexity of this algorithm, as a function of n? The loop is run n-1 times, which we’ll approximate by n. How long do the math operations take? There is one multiplication, a subtraction of 2, and a modulo 2n – 1. Subtraction of 2 will be almost constant – most of the time you only need to consider a few bits at the end. The modulo can be done by shifting and adding instead of division. (Consider the analogous: 38724198 mod 9999 = 3872+4198 = 8070.) The complexity of adding is linear, so the majority of time is done on multiplication. How fast can multiplication be done? The standard method is O(n2) and the faster recursive Karatsuba method is about O(n1.6). What is the fastest practical algorithm? Research shows that it is the Schonage-Strassen method with complexity O(n log n log log n), which means O( n log(n) log(log(n)) ). Therefore the complexity of the Lucas Lehmer algorithm is O(n2 log n log log n). (Wikipedia’s Primality Test indicates that algorithms for general numbers of n bits have a much greater complexity of O(n6).) Let’s use that information to solve the following problem.
If it takes 12 days for a powerful desktop computer to perform a Lucas Lehmer test on a 10 million digit number, how long will it take for 100 million digits, and for 1 billion digits?
Do we need to use the number of decimal digits, or the number of binary digits – bits? If you review the calculation of decimal digits you see that it is about 3.32 times the number of bits – a constant factor. Also, does it matter if we use logs to base 2, or to base 10? Well, log10x = log2x / log210 so the logs are related by multiplying by a constant factor. The O(.) notation ignores constant multiples, so we can simplify our calculations by using decimal digits and logs to the base 10.
From the algorithm complexity we know that
T(n) = c n2 log n log log n
where c is some constant. So we have three equations:
T(107) = c (107)2 log (107) log log (107) = 12 days
T(108) = c (108)2 log (108) log log (108) = x days
T(109) = c (109)2 log (109) log log (109) = y days
The constant c can be eliminated by division to get
x = 12 [ (108)2 log (108) log log (108) ] / [ (107)2 log (107) log log (107) ]
= 12 [ 1016 8 0.903 ] / [ 1014 7 0.845 ] = 1465 days = about 4 years
Similarly, y = 500 years. So, it takes about 4 years to test a 100 million digit number and about 500 years to test a 1 billion digit number. The corresponding prizes are $150,000 and $250,000.