2013/04/08 by Thomas Morrell, Morrell, Thomas
Mathematics · #11A51 #E.3 #F.2.1 #FOS: Mathematics #I.1.2 #Number Theory (math.NT) #acm:11A51 #math.NT #msc:11A51
paper · pdf · doi:10.48550/arxiv.1304.2314
Withdrawn due to error
arxiv created 2013/04/15 · arxiv updated 2013/04/17
The Lucas-Lehmer (LL) primality test for Mersenne numbers is the fastest known primality test. In 1969, Hans Riesel published a modification of LL to test numbers of the form N = h ⋅ 2n - 1, where h < 2n is an odd integer and n ≥ 2 \citeRiesel. This test is now known as the Lucas-Lehmer-Riesel (LLR) primality test. In Algorithm \refPrimalityAlgorithm, we present a modification of LLR which works for any odd integer N. A probabilistic version of our algorithm runs in expected time O(log3 N), and a deterministic version in expected O(log4 N). We conclude with a conjecture which, if true, would imply that there exists a polynomial time algorithm for factoring integers.