1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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?