20130408, 23:46  #1 
Dec 2011
After milion nines:)
2^{4}·89 Posts 
PRP testing
LucasLehmer Test (1930): Let n be an odd prime. The Mersenne number M(n) = 2n1 is prime if and only if S(n2) = 0 (mod M(n)) where S(0) = 4 and S(k+1) = S(k)22.(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. Last fiddled with by pepi37 on 20130408 at 23:49 
20130409, 03:38  #2  
Jun 2003
2·5·7·71 Posts 
Quote:
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] 

20130409, 07:24  #3 
Dec 2011
After milion nines:)
2^{4}×89 Posts 
So in present time PRP test for Proth or Riesel numbers are slower then testing those numbers with LLR?

20130409, 07:33  #4 
Jun 2003
2·5·7·71 Posts 
Correct (although not by much). Directly proving primality is the way to go for them.

20130409, 07:41  #5 
Dec 2011
After milion nines:)
2^{4}×89 Posts 
Thanks Axn

20130409, 16:21  #6 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×5×587 Posts 
The amount of multiplications for each test is roughly the same although doing those multiplications(ffts) is less efficient for nonmersenne numbers as more generic methods must be used.

20130412, 09:42  #7  
"Carlos Pinho"
Oct 2011
Milton Keynes, UK
2^{2}·5·13·19 Posts 
Quote:
Carlos 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Antipoverty drug testing vs "high" tax deduction testing  kladner  Soap Box  3  20161014 18:43 
What am I testing?  GARYP166  Information & Answers  9  20090218 22:41 
k=243 testing ??  gd_barnes  Riesel Prime Search  20  20071108 21:13 
Testing  grobie  Marin's Mersennearies  1  20060515 12:26 
Speed of P1 testing vs. Trial Factoring testing  eepiccolo  Math  6  20060328 20:53 