Loading ...
Sorry, an error occurred while loading the content.
 

FW: [PrimeNumbers] Lucas-Lehmer proofs?

Expand Messages
  • Torbjorn Alm
    The best description is in Riesel 94, p 124-129, where both the simple case mod(k,3) 0 and the more complex case where mod(k,3)=0 are desribed. Torbjorn Alm
    Message 1 of 1 , Dec 30, 2002
      The best description is in Riesel 94, p 124-129, where both the simple case
      mod(k,3)<> 0 and the more complex case where mod(k,3)=0 are desribed.

      Torbjorn Alm
      Tranholmsvagen 3
      SE-178 32 Ekero, Sweden
      +46 8 560 307 51
      torbjorn.alm@... <mailto:torbjorn.alm@...>


      There are 10 types of people in this world, those who can read binary and
      those who can't.






      -----Original Message-----
      From: Phil Carmody [mailto:thefatphil@...]
      Sent: den 30 december 2002 14:54
      To: primenumbers
      Subject: Re: [PrimeNumbers] Lucas-Lehmer proofs?


      --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...>
      wrote:
      > I seem to have a hole in my math.

      This should be a FAQ. It gets guys on sci.crypt all the time.

      > Where is the reference that a Lucas-Lehmer test
      > can prove primality of k*2^n-1,
      > as opposed to being merely a Lucas PrP test
      > in Q(sqrt(3)) ?

      <<<
      It is also easy to give a test paralleling Pocklington's theorem using Lucas
      sequences. This was first done by D. H. Lehmer in 1930 (in the same article
      he introduced the Lucas-Lehmer test: [Lehmer30]). See [BLSTW88] or [BLS75]
      or ... for more information on these tests.
      >>>

      The Lehmer-Pocklington (a la Riesel) tests are frequently refered to as
      Lucas-Lehmer tests by peole who don't care for minutiae.

      > Help, please!

      There's always the source, I guess. Is there anything which looks like a
      Pocklington step?

      However, I reckon that as finding an element with maximal order is
      non-deterministic, it ought to be able to provoke a Pocklington test into
      having different running times for different numbers. And given that only
      one prime factor, 2, is being considered, the running times should be
      integer
      multiples of a LPRP test time.

      Does that make sense?

      If so, every number runs in the same time, I'd _guess_ that this is a SLPRP
      test, and David's diagnosis is realised.

      Phil


      =====
      The answer to life's mystery is simple and direct:
      Sex and death. -- Ian 'Lemmy' Kilminster

      __________________________________________________
      Do you Yahoo!?
      Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
      http://mailplus.yahoo.com

      Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      The Prime Pages : http://www.primepages.org/



      Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
    Your message has been successfully submitted and would be delivered to recipients shortly.