mersenneforum.org PRP testing
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2013-04-08, 23:46 #1 pepi37     Dec 2011 After milion nines:) 24·89 Posts PRP testing 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. Last fiddled with by pepi37 on 2013-04-08 at 23:49
2013-04-09, 03:38   #2
axn

Jun 2003

2·5·7·71 Posts

Quote:
 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]

 2013-04-09, 07:24 #3 pepi37     Dec 2011 After milion nines:) 24×89 Posts So in present time PRP test for Proth or Riesel numbers are slower then testing those numbers with LLR?
 2013-04-09, 07:33 #4 axn     Jun 2003 2·5·7·71 Posts Correct (although not by much). Directly proving primality is the way to go for them.
 2013-04-09, 07:41 #5 pepi37     Dec 2011 After milion nines:) 24×89 Posts Thanks Axn
 2013-04-09, 16:21 #6 henryzz 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 non-mersenne numbers as more generic methods must be used.
2013-04-12, 09:42   #7
pinhodecarlos

"Carlos Pinho"
Oct 2011
Milton Keynes, UK

22·5·13·19 Posts

Quote:
 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

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post kladner Soap Box 3 2016-10-14 18:43 GARYP166 Information & Answers 9 2009-02-18 22:41 gd_barnes Riesel Prime Search 20 2007-11-08 21:13 grobie Marin's Mersenne-aries 1 2006-05-15 12:26 eepiccolo Math 6 2006-03-28 20:53

All times are UTC. The time now is 00:31.

Wed May 19 00:31:51 UTC 2021 up 40 days, 19:12, 0 users, load averages: 2.19, 2.16, 2.02

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.