- #1

Milkman

- 5

- 0

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)

(-3x - 5)^2 - 2 = 9x^2 + 30x + 23

9x^2 + 30x + 23 = 3x - 4 (mod x^2 + 3x + 3)

(3x - 4)^2 - 2 = 9x^2 - 24x + 14

9x^2 - 24x + 14 = -51x - 13 (mod x^2 + 3x + 3)

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?

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: