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

Re: Shortcutting the Lucas-Lehmer Test

Expand Messages
  • 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 1 of 3 , Aug 21, 2004
      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.