On January 19, 2016, Dr. Curtis Cooper published about his recent discovery of a
ID: 1716561 • Letter: O
Question
On January 19, 2016, Dr. Curtis Cooper published about his recent discovery of a 49^th Mersenne prime, 2^74207281 - 1 (a number with 22,338,618 digits), as a result of a search executed by a GIMPS server network. The best method presently known for testing the primality of Mersenne numbers is the Lucas-Lehmer test. Specifically, it can be shown that for prime p > 2, M_P = 2^p - 1 is prime if and only if (S_P - 2) % M_P = 0, where S_0 = 4 and, for k > 0, S_k = ((S_k-1)^2 - 2) % M_p. I give you two options: you may use either the grade school algorithm for multiplication or the Karatsuba algorithm. I arbitrarily chose the following two constants: time to add two numbers of 64 bits each: 0.5nano-sec time to multiply two numbers of 64 bits each: 1.5nano-sec. How much time would be required (on a single machine) to prove the primality of the 49th Mersenne prime? (Proceed by making some reasonable assumptions about the recurrence expressing the running-time of both multiplication methods and solving them.) Count time for subtraction to be the same as addition and the time for modulo (%) to be the same as multiplication.Explanation / Answer
sorry this was meant to be a programming question