Talk:Lucas primality test

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
  • Something is very wrong here. The article seems to use the hidden (and wrong) assumption that a number n is prime if a primitive root mod n can be located. AxelBoldt 15:05, 18 Jun 2004 (UTC)
Ooops, sorry. Please ignore the above and excuse my stupidity. AxelBoldt 15:27, 18 Jun 2004 (UTC)
  • Question: what is its complexity ?
  • I do not understand why you name this test as Lucas-Lehmer Test (LLT) ! The LLT was designed by Lucas for proving the primality of Mersenne and Fermat numbers, and it made use of "Lucas" Sequences at first, and then a complete proof was given by Lehmer and he provided one test instead of the two of Lucas (depending on q of 2^q-1). The LLT uses the famous S(i+1)=S(i)^2-2 suite. The test you are talking about is called "Lucas' test as strengthened by Kraitchik and Lehmer" by Chris. Caldwell (see: Caldwell Prime Site), and it is a VERY different test since it is based on Fermat's little theorem and not on "Lucas" sequences nor on the S(i+1)=S(i)^2-2 suite. So, maybe it would be better to name it: Lucas' test. Also, the description of the test is not perfectly correct, compared to Caldwell's version. I've fixed it. (2007/05/20)
  • Definititely, this test is not "Lucas-Lehmer test" ! The Pomerance/Crandall book, 2nd Edition, "Prime Numbers, A computational perspective", clearly names it: "Lucas theorem", page 173. Lehmer never did anything about this theorem. So this must be renamed !!!! (but I don't know how to fix the page... —Preceding unsigned comment added by (talk) 20:58, 13 January 2009 (UTC)
  • {{support}} this is wrongly titled. This is known only as "Lucas test". Reference: «17 Lectures on Fermat numbers: From number Theory to Geometry", by Krizek, Luca & Sommer. Canadian Mathematical Society/Springer, 2001. ISBN 0387953329. -- m:drini 17:51, 2 June 2009 (UTC)

Similarity to the Pratt's ceritificate[edit]

Am I the only man to notice that this test is VERY similar to the Pratt's certificate?! (talk) 21:04, 16 March 2008 (UTC)


This test is described as the Lehmer-Pocklington Theorem by Riesel. He does not use this exact name, but refers to Lehmer's Analogue for Lucas sequences, which is the case where the factorisation of N+1 is known. Richard Pinch (talk) 16:12, 20 September 2008 (UTC)

Could this be any denser?[edit]

This page isn't too friendly for those who want to understand but can't due to the density of the text and $5 words. Perhaps a Simple English translation? (talk) 16:08, 6 October 2008 (UTC)