PRP testing
 

[INDENT][B]Lucas-Lehmer Test[/B] (1930): Let [I]n[/I] be an odd prime. The Mersenne number M([I]n[/I]) = 2[I]n[/I]-1 is prime if and only if S([I]n[/I]-2) = 0 (mod M([I]n[/I])) where S(0) = 4 and S([I]k[/I]+1) = S([I]k[/I])2-2. [/INDENT](The proof of sufficiency is found on a [URL="http://primes.utm.edu/notes/proofs/LucasLehmer.html"]separate page[/URL].) [B]This test is exceptionally fast on a binary computer because it requires no division. [/B]

As I ( and if I ) understand correctly in process of prime search there is sieving , PRP and proof of prime with some software (LLR, PFGW)
All prime searchers do a deep sieve then immediately start llr testing.
Why is PRP step skipped if it is as quoted "[B]exceptionally fast [/B]"?
In any case it is sure faster then LLR ( or it is not)
I read that PFGW can do PRP test, but never sow that test was faster then LLR of same number.
Thanks for explanation.

[QUOTE=pepi37;336501][INDENT][B]Lucas-Lehmer Test[/B] (1930): Let [I]n[/I] be an odd prime. The Mersenne number M([I]n[/I]) = 2[I]n[/I]-1 is prime if and only if S([I]n[/I]-2) = 0 (mod M([I]n[/I])) where S(0) = 4 and S([I]k[/I]+1) = S([I]k[/I])2-2. [/INDENT](The proof of sufficiency is found on a [URL="http://primes.utm.edu/notes/proofs/LucasLehmer.html"]separate page[/URL].) [B]This test is exceptionally fast on a binary computer because it requires no division. [/B][/QUOTE]

This is not a PRP test. This is a primality proving test (like LLR test). This test is for mersenne numbers (2^p-1), while LLR is for Riesel numbers (k*2^n-1). There is another primality proving test called proth test for Proth numbers (k*2^n[COLOR="Red"]+[/COLOR]1). Both Riesel Number & Proth Numbers are supported by LLR [B]program[/B] (written by Jean Penne). And for their respective numbers, these tests are as fast or faster than a generic PRP test.

For numbers that are not of these forms, we'll do a PRP test followed by a more time consuming primality proving test. PFGW can do both of these.

[I am glossing over the addition of more supported forms in LLR program, and specialized PRP testers/provers for some other projects]

So in present time PRP test for Proth or Riesel numbers are slower then testing those numbers with LLR?

Correct (although not by much). Directly proving primality is the way to go for them.

Thanks Axn :smile:

The amount of multiplications for each test is roughly the same although doing those multiplications(ffts) is less efficient for non-mersenne numbers as more generic methods must be used.

[QUOTE=axn;336518]There is another primality proving test called proth test for Proth numbers (k*2^n[COLOR=Red]+[/COLOR]1). Both Riesel Number & Proth Numbers are supported by LLR [B]program[/B] (written by Jean Penne). And for their respective numbers, these tests are as fast or faster than a generic PRP test.
[/QUOTE]

Can a positive from a primality proving test be called a unique prime number?

Carlos