PRP testing

[pepi37]

Lucas-Lehmer Test (1930): Let n be an odd prime. The Mersenne number M(n) = 2n-1 is prime if and only if S(n-2) = 0 (mod M(n)) where S(0) = 4 and S(k+1) = S(k)2-2.

(The proof of sufficiency is found on a separate page.) This test is exceptionally fast on a binary computer because it requires no division.

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 "exceptionally fast "?
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.

[axn]

Originally Posted by pepi37

Lucas-Lehmer Test (1930): Let n be an odd prime. The Mersenne number M(n) = 2n-1 is prime if and only if S(n-2) = 0 (mod M(n)) where S(0) = 4 and S(k+1) = S(k)2-2.

(The proof of sufficiency is found on a separate page.) This test is exceptionally fast on a binary computer because it requires no division.

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+1). Both Riesel Number & Proth Numbers are supported by LLR program (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]

[pepi37]

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

[axn]

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

[pepi37]

Thanks Axn

[henryzz]

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.

[pinhodecarlos]

Originally Posted by axn

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

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

Carlos