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

Lucas-Lehmer Test With Polynomials

  1. Dec 3, 2006 #1
    Does anyone know why the lucas-lehmer test won't work with numbers represented by polynomials? The modulus polynomial does not divide the last term correctly for some reason.



    Example (the code boxes are polynomial long division):

    the numbers will be represented in base 4, so 4 = x

    p = x + 1 (or 5; the mersenne exponent)
    2^p-1 = x^2 + 3x + 3 (or 31; the mersenne number to be tested)

    p-2 iterations of the lucas sequence, mod 2^p-1:

    (x)^2 - 2 = x^2 - 2
    x^2 - 2 = -3x - 5 (mod x^2 + 3x + 3)
    Code (Text):

                   1
                 ---------------
    x^2 + 3x + 3 ) x^2 + 0x - 2
                  -x^2 - 3x - 3
                  --------------
                        -3x - 5
     
    (-3x - 5)^2 - 2 = 9x^2 + 30x + 23
    9x^2 + 30x + 23 = 3x - 4 (mod x^2 + 3x + 3)
    Code (Text):

                    9
                 ------------------
    x^2 + 3x + 3 ) 9x^2 + 30x + 23
                  -9x^2 - 27x - 27
                  ----------------
                           3x - 4
     
    (3x - 4)^2 - 2 = 9x^2 - 24x + 14
    9x^2 - 24x + 14 = -51x - 13 (mod x^2 + 3x + 3)
    Code (Text):

                   9
                 ------------------
    x^2 + 3x + 3 ) 9x^2 - 24x + 14
                  -9x^2 - 27x - 27
                  ----------------
                         -51x - 13
     
    x^2 + 3x + 3 should divide 9x^2 - 24x + 14 evenly, and the last result should be 0, not -51x - 13. And -51x - 13 is not congruent to zero in any field (I don't think).



    So what's wrong?
     
    Last edited: Dec 3, 2006
  2. jcsd
  3. Dec 22, 2006 #2
    Don't we should have all coefficients lower than x=4 ?
    As an example, 3x - 4 = 2x ?
    T.
     
  4. Dec 22, 2006 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That's not what Lucas-Lehmer says: it says that

    4² + 3*4 + 3

    should divide

    9*4² - 24*4 + 14

    evenly. (And it does)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?