Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Another (candidate) test of primality of Mersenne number

  1. Apr 29, 2006 #1
    Hi,

    You probably already know the Lucas-Lehmer-Test (LLT) used for proving that a Mersenne number is prime or composite. (See: MathWorld and a proof).

    The LLT is based on the properties of the Tree built by [tex]x^2-2[/tex] modulo a Mersenne number.

    Now, here is a conjecture (checked up to M26 = [tex]M_{23209}[/tex]) based on the properties of the Cycles of length (q-1) built by [tex]x^2-2[/tex] modulo a Mersenne number.

    [tex]\large M_q=2^q-1 \text{ is prime } \Longleftrightarrow \ S_{q-1} \equiv S_0 \ \pmod{M_q} \text{ , where: } S_0=3^2+1/3^2 , \ S_{i+1}=S_i^2-2 \ .[/tex]

    How can it be proved ?

    Tony
    (far from Internet till 8th of May)
     
  2. jcsd
  3. May 8, 2006 #2
    No idea ?

    This conjecture is the first step of an attempt to find a primality proof for Mersenne numbers faster than the Lucas-Lehmer test (LLT).
    So a proof could help the GIMPS project.

    Tony
     
  4. May 8, 2006 #3
    I not sure how to do mod arithmetic in fractions.
    Let
    Say [tex]M_q = 7 = 63/9[/tex] and[tex]S_{0} = \frac{82}{9}[/tex]
    1) Is the following true?
    [tex]S_0 \equiv \frac{(82-63)}{9} = \frac{19}{9} \mod M_q[/tex]

    2)If S_0 is squared the denominator gets larger, but how does it then become equal to [tex]9[/tex] again?

    3)Can you illustrate this for M_2 or M_3?
     
    Last edited: May 8, 2006
  5. May 9, 2006 #4
    1/3^2 mod Mq can be easily computed, since Mq=1+2.3.q.k .
    1/3 mod Mq = (2.Mq+1)/3 .

    Examples with q=5, 7, 13 (using PARI/gp) :
    q=5
    (1/3)%31 --> 21
    (2*31+1)/31 --> 21
    (3^2+1/3^2)%31 --> 16

    q=7
    (1/3)%127 --> 85
    (2*127+1)/3 --> 85
    (3^2+1/3^2)%127 --> 122

    q=13
    (1/3)%8191 --> 5461
    (2*8191+1)/3 --> 5461
    (3^2+1/3^2)%8191 --> 7290

    Regards,

    Tony
     
  6. May 9, 2006 #5
    Iterations for q=5,7,11,13 and PARI/gp code

    Code (Text):
    q=5: S0=16 -> 6 -> 3 -> 7 -> 16

    q=7: S0=122 -> 23-> 19 -> 105 -> 101 -> 39 -> 122

    q=11: S0=464 -> 359 -> 1965 -> 581 -> 1851 -> 1568 -> 175 -> 1965 -> 581 -> 1851 -> 1568

    q=13: S0=7290 -> 890 -> 5762 -> 2519 -> 5525 -> 5957 -> 2435 -> 7130 -> 3552 -> 2562 -> 2851 -> 2727 -> 7290

    PARI/gp:

    LLGT(q)=
    {
    M=2^q-1; S0=(3^2+1/3^2)%M; print(S0); S=S0;
    for(i=1, q-1, S=(S^2-2)%M; print(S));
    if(S==S0, print("Prime !"), print("Composite"))
    }

     
     
  7. May 9, 2006 #6
    I forgot to say that the idea could only speed up proving a Mersenne number is composite.
    T.
     
  8. May 11, 2006 #7
    My excel program gives 1/3 mod 31 = .333 which seems correct to me.
    Why not (2*31+1)/31 = 3?
     
  9. May 11, 2006 #8
    Could you work these through to show how one would get a integer as the result using pencil and paper instead of a fraction when you compute [tex]S_{0} (or 9 + 1/9) mod 7[/tex]
     
  10. May 12, 2006 #9
    It is Arithmetic. Use an appropriate tool, like PARI/gp.
    Here y=1/x=x^(-1) mod z means y*x = 1 mod z , where x, y and z are integers ....
    T.
     
  11. May 12, 2006 #10
    Since 9 = 2 mod 7 and since 2*4=8=1 mod 7 , 9+1/9 = 2+1/2=2+4=6 mod 7.
    T.
     
  12. May 12, 2006 #11
    OK Now I understand how fractions can be converted to integers in mod calculations.
    [tex]1/9= 1/2 = 8/2 = 4 \mod 7[/tex]

    Thanks
     
  13. May 15, 2006 #12
    I thimk you and I have something

    I can't begin to proove it but you seem to have something here.
    P.S. How about my test?
    If [tex]M_{p}[/tex] is prime, then for the recursive series [tex]S_{1}=a, S_{2} = b,[/tex]
    [tex] S_{n} = 6*S_{(n-1)} - S_{(n-2)} \mod M_{p} \quad \mid 0 \leq a,b < M_{p}[/tex]
    Then [tex]S_{2^{(p-1)}} = a[/tex]

    For [tex]m_{p}[/tex] = composite the test is not conclusive for a single a and b but it is easy to find a false set.
     
    Last edited: May 15, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Another (candidate) test of primality of Mersenne number
Loading...