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

Re: [PrimeNumbers] Shortcutting the Lucas-Lehmer Test

Expand Messages
  • James Wanless
    ... Speaking of speeding up LL - I noticed some slightly odd behaviour a while ago in the course of writing some (very) simple little java programs for finding
    Message 1 of 3 , Aug 18, 2004
    • 0 Attachment
      jfollas wrote:

      >I've been researching a concept involving shortcutting the Lucas-
      >Lehmer primality test for Mersenne numbers over the past several
      >months. Today, prompted by someone posting on mersenneforums the
      >same critical discovery that I made, I have released a summarization
      >of my off-and-on research effort. I welcome the members of this
      >group to review my findings.
      >
      >My post:
      >
      >http://www.mersenneforum.org/showpost.php?p=38252&postcount=8
      >
      >or the entire thread:
      >
      >http://www.mersenneforum.org/showthread.php?t=2783
      >
      >-Jason
      >
      >
      >(Please be kind! I'm not really a mathematician! ;-)
      >
      >
      >
      >
      >
      >Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      >The Prime Pages : http://www.primepages.org/
      >
      >
      >Yahoo! Groups Links
      >
      >
      >
      >
      >
      >
      >
      >
      Speaking of speeding up LL - I noticed some slightly odd behaviour a
      while ago in the course of writing some (very) simple little java
      programs for finding Mp's - I'd be interested if anyone investigated
      further/ even confirmed my findings...?
      What I found (apparently) was that [and I only tested relatively small
      indices of Mn's - up to a couple of thousand or so] a 3-PRP test (or
      maybe even a 3-Wanless test, with the extra level of exponentiation for
      even greater accuracy - see my earlier post for details of "wanless
      test") was actually somewhat quicker than a LL test.
      This surprised me somewhat (I have to say), but at the time I put it
      down (presumably) to java's efficient implementation of the "Russian
      Peasant" method of modular exponentiation.
      J
    • Shane
      If we look at the known test: A Mersenne number M(p) is prime if M(p) divides S(p-2) where S(0)=4 and, S(p)=S(p-1)^2 -2(mod 2^p -1) My double case
      Message 2 of 3 , Aug 21, 2004
      • 0 Attachment
        If we look at the known test:

        A Mersenne number M(p) is prime if M(p) divides S(p-2) where S(0)=4
        and,

        S(p)=S(p-1)^2 -2(mod 2^p -1)



        My double case test/probable test: (where L(n) are Lucas numbers, via
        the golden proportion)(10/19/01) The golden ratio could speed up the
        squarings involved. Since there are various algorithmic ways to
        generate Lucas numbers, by adding fractals etc. The mod here, would
        be subracted at each add, rather than divided out.

        L(2^(p-1))mod 2^p -1 = 0 [CASE1]
        L(2^(p-1) -1) mod 2^p -1 = 0 [CASE2]
        Or L(2^(p-1) -1)mod 2^p +1 /3 = 0[CASE2]

        2^2-1=3 divides L(2)=3 [C1]
        2^3-1=7 divides, L(4)=7 [C1]
        2^5-1=31 divides, L(15)=1364 [C2]
        2^7-1=127 divides, L(64)=23725150497407 [C1]
        2^13-1=8191 divides, L(4095) [C2]
        2^17-1=131071 divides, L(65535) [C2]
        2^19-1=524287 divides, L(262144) [C1]

        So, also with F(n): (Fibonacci numbers)
        F(2^p) mod 2^p -1 = 0[Case 1]
        F(2^p -2) mod 2^p -1 = 0[Case 2]
        F(2^p -2) mod 2^p +1 /3 = 0[Case 2]


        2^2-1=3 divides F(4)=3 [C1]
        2^3-1= 7 divides F(8)=21 [C1]
        2^5-1=31 divides F(30)=832040, [C2]
        2^7-1=127 divides F(128)=251728825683549488150424261 [C1]
        2^13-1=8191 divides F(8190) [C2]
        2^17-1=131071 divides F(131070) [C2]
        2^19-1=524287 divides F(524288) [C1]


        David Broadhurst wrote me:
        The classic Lucas-Lehmer test for Mersennes
        uses the Lucas sequence with
        p=2, q=-2, d=p^2-4*q=12 (Ribenboim p.92).
        You can "probably" use the same batch of theorems
        from Ribenboim to prove the necessity and sufficiency
        of your more complicated two-case test with
        p=1, q=-1, d=p^2-q=5 (i.e. the rabbit case).

        This is proven completey true up to Lucas# = L(2^4499)
        Though, the residue of the Mersenne exponent mod 4, decides whether
        or not the test is deterministic.
      Your message has been successfully submitted and would be delivered to recipients shortly.