Lucas-Lehmer Test With Polynomials

In summary, the Lucas-Lehmer test may not work with numbers represented by polynomials because the modulus polynomial may not divide the last term correctly. This can result in coefficients that are not lower than the base, which goes against the principles of the test.
  • #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)
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:
Physics news on Phys.org
  • #2
Don't we should have all coefficients lower than x=4 ?
As an example, 3x - 4 = 2x ?
T.
 
  • #3
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 to Lucas-Lehmer Test With Polynomials

What is the Lucas-Lehmer test with polynomials?

The Lucas-Lehmer test with polynomials is a method for determining whether a given number is a Mersenne prime, which is a prime number of the form 2^n - 1. It is based on the Lucas-Lehmer algorithm, which was developed by mathematicians Édouard Lucas and Derrick Henry Lehmer.

How does the Lucas-Lehmer test with polynomials work?

The test works by using a specific type of polynomial called a Lucas-Lehmer polynomial, which is generated using the given number being tested. The polynomial is then evaluated at a specific value, and if the result is equal to 0, the number is a Mersenne prime. If the result is not equal to 0, the number is not a Mersenne prime.

What is the significance of the Lucas-Lehmer test with polynomials?

The Lucas-Lehmer test with polynomials is significant because it provides a fast and efficient way to determine whether a given number is a Mersenne prime. This is important in the field of number theory and for finding large prime numbers, which are used in cryptography and other mathematical applications.

What are the limitations of the Lucas-Lehmer test with polynomials?

While the Lucas-Lehmer test with polynomials is a useful tool for determining Mersenne primes, it is not foolproof. There are rare cases where the test may produce a false positive, meaning a number is mistakenly identified as a Mersenne prime when it is not. Additionally, the test only works for numbers that are one less than a power of 2.

How is the Lucas-Lehmer test with polynomials different from the traditional Lucas-Lehmer test?

The traditional Lucas-Lehmer test is based on the same algorithm, but it uses a different type of polynomial called a Lucas-Lehmer sequence. This sequence is generated in a different way and does not rely on the given number being tested. The traditional test is generally slower and less efficient than the polynomial test, but it is more reliable in terms of producing accurate results.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
2
Views
618
  • Precalculus Mathematics Homework Help
Replies
4
Views
801
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
946
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
3K
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
2K
Replies
13
Views
3K
Back
Top