Modifying the Lucas Lehmer Primality Test into a fast test of nothing

[science_man_88]

Originally Posted by gophne

The fact that the Lucas-Lehmer iteration works suggests to me that the distribution of mersenne prime numbers are "regular', dependant on the outcome of the LL iteration, but never-the-less "regular".

My question would be if anybody has ever looked or found any "marker/s" in the set of values generated by each mersenne prime iteration. Such things as say the term nearest to the "square root" position value of the set of iterations being of a certain relationship to the value of the successful value which would yield a return of "0", or any other relationship between the values comprising the set of iterations for a specific mersenne prime.

Any such marker could then either reduce the time needed to "prove" primality, or be an indicator whether it would be fruitful to continue with that iteration.

Iterations that hit -2,-1,0,1,2 mod the mersenne, prior to the final iteration are either bad, or not prime. We also know (uselessly) that the residue has the same parity as the floor of the full number divided by the mersenne. Another useless fact is that a candidate factor can be tested using a modified LL test mod the candidate ( given at least 1 LL test using the mersenne). About the only interesting fact I come up with on the fly, is that a candidate mersenne prime, has to have an even multiple of the product of all previous mersenne primes( except maybe pairs of twin prime exponents), congruent to -2 mod the candidate.

[JM Montolio A]

I never find any rule for primes.

I believe that is the only rule true here.

If you detect a rule, wrong way.

[gophne]

Originally Posted by science_man_88

Iterations that hit -2,-1,0,1,2 mod the mersenne, prior to the final iteration are either bad, or not prime. We also know (uselessly) that the residue has the same parity as the floor of the full number divided by the mersenne. Another useless fact is that a candidate factor can be tested using a modified LL test mod the candidate ( given at least 1 LL test using the mersenne). About the only interesting fact I come up with on the fly, is that a candidate mersenne prime, has to have an even multiple of the product of all previous mersenne primes( except maybe pairs of twin prime exponents), congruent to -2 mod the candidate.

Wow interesting. Does this last relationship hold for all the known mersenne primes?

[science_man_88]

Originally Posted by gophne

Wow interesting. Does this last relationship hold for all the known mersenne primes?

Has to for primes testable by LL. Once 0 mod a number is hit, -2 mod that number is hit, followed by repeating 2 forever. 2 mod coprimes, is 2 mod their product. Etc.