Lucas-Lehmer Test With Polynomials

  • Thread starter Milkman
  • Start date
  • #1
5
0

Main Question or Discussion Point

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:
               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:
                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:
               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:

Answers and Replies

  • #2
62
0
Don't we should have all coefficients lower than x=4 ?
As an example, 3x - 4 = 2x ?
T.
 
  • #3
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
x^2 + 3x + 3 should divide 9x^2 - 24x + 14 evenly
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)
 

Related Threads on Lucas-Lehmer Test With Polynomials

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
4
Views
5K
  • Last Post
Replies
8
Views
6K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
9
Views
3K
Replies
5
Views
2K
Replies
7
Views
14K
Top