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.(adsbygoogle = window.adsbygoogle || []).push({});

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 + 23Code (Text):

1

---------------

x^2 + 3x + 3 ) x^2 + 0x - 2

-x^2 - 3x - 3

--------------

-3x - 5

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

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

9

------------------

x^2 + 3x + 3 ) 9x^2 + 30x + 23

-9x^2 - 27x - 27

----------------

3x - 4

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).Code (Text):

9

------------------

x^2 + 3x + 3 ) 9x^2 - 24x + 14

-9x^2 - 27x - 27

----------------

-51x - 13

So what's wrong?

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Lucas-Lehmer Test With Polynomials

Loading...

Similar Threads - Lucas Lehmer Test | Date |
---|---|

Fourier transformation and test function -- Question in the derivation | Dec 31, 2015 |

Lemma Lucas theorem | Oct 19, 2013 |

K*Lucas_n + 1 is a prime of Lucas Number Index (a Lattice/Partition # Relationship?) | May 10, 2011 |

Fibonacci and lucas series. | Feb 28, 2011 |

Edouard Lucas. Théorie des Nombres. Help with his unpublished Second Volume | Dec 3, 2008 |

**Physics Forums - The Fusion of Science and Community**