mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2013-04-08, 23:46   #1
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

24·89 Posts
Default 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
pepi37 is online now   Reply With Quote
Old 2013-04-09, 03:38   #2
axn
 
axn's Avatar
 
Jun 2003

2·5·7·71 Posts
Default

Quote:
Originally Posted by pepi37 View Post
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]
axn is offline   Reply With Quote
Old 2013-04-09, 07:24   #3
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

24×89 Posts
Default

So in present time PRP test for Proth or Riesel numbers are slower then testing those numbers with LLR?
pepi37 is online now   Reply With Quote
Old 2013-04-09, 07:33   #4
axn
 
axn's Avatar
 
Jun 2003

2·5·7·71 Posts
Default

Correct (although not by much). Directly proving primality is the way to go for them.
axn is offline   Reply With Quote
Old 2013-04-09, 07:41   #5
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

24×89 Posts
Default

Thanks Axn
pepi37 is online now   Reply With Quote
Old 2013-04-09, 16:21   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×5×587 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2013-04-12, 09:42   #7
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

22·5·13·19 Posts
Default

Quote:
Originally Posted by axn View Post
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
pinhodecarlos is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Anti-poverty drug testing vs "high" tax deduction testing kladner Soap Box 3 2016-10-14 18:43
What am I testing? GARYP166 Information & Answers 9 2009-02-18 22:41
k=243 testing ?? gd_barnes Riesel Prime Search 20 2007-11-08 21:13
Testing grobie Marin's Mersenne-aries 1 2006-05-15 12:26
Speed of P-1 testing vs. Trial Factoring testing 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.