mersenneforum.org Another way to PRP test Mersenne numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2017-01-20, 08:51 #1 paulunderwood     Sep 2002 Database er0rr 118F16 Posts Another way to PRP test Mersenne numbers Not as efficient as LL: Code: yaMersennePRP(p)=local(n=2^p-1,a=Mod(4,n),b=a+1);for(k=2,p,a=2*a*b;b=a+1);print(p" "a==4)
2017-01-20, 12:41   #2
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 Originally Posted by paulunderwood Not as efficient as LL: Code: yaMersennePRP(p)=local(n=2^p-1,a=Mod(4,n),b=a+1);for(k=2,p,a=2*a*b;b=a+1);print(p" "a==4)
modification thoughts:
1) getting rid of b is easy as at every step using it you are calculating 2*a^2+2*a

I had a few more at first but I tested them and they didn't work to replicate, they went down the wrong division of everything by 2 path I think.

 2017-01-20, 23:25 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 44458 Posts Isn't LL a primality test rather than a PRP test? Is this algo also a deterministic primality test?
2017-01-21, 00:28   #4
paulunderwood

Sep 2002
Database er0rr

118F16 Posts

Quote:
 Originally Posted by a1call Isn't LL a primality test rather than a PRP test? Is this algo also a deterministic primality test?
Yes, LL is a primailty test. And, no, this is just a PRP test. It might be just another 3-PRP test in disguise -- I am not sure about it.

 2017-01-21, 00:48 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 92516 Posts So I assume you know of values for p which return true but are in fact yield composite Mersennes. Correct? Last fiddled with by a1call on 2017-01-21 at 00:48
2017-01-21, 01:27   #6
paulunderwood

Sep 2002
Database er0rr

5×29×31 Posts

Quote:
 Originally Posted by a1call So I assume you know of values for p which return true but are in fact yield composite Mersennes. Correct?
No. I do not know of any counterexamples -- maybe there are infinitely many or none.

 2017-01-21, 01:38 #7 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2,341 Posts Well, that makes it more interesting than just another PRP test. Are there any values that you know of, that yield false but are in fact prime? That shouldn't be too difficult to check given the limited number of known MPs.
2017-01-21, 05:31   #8
CRGreathouse

Aug 2006

10111011000112 Posts

Quote:
 Originally Posted by a1call Are there any values that you know of, that yield false but are in fact prime? That shouldn't be too difficult to check given the limited number of known MPs.
The Mersenne exponents through 44497 check out. There are no false positives through 23209. I'm using this PARI code which should be somewhat more efficient than the GP above.
Code:
#include <pari/pari.h>
/* For use in gp:
GP;install("testMersenne","lU","testMersenne","./filename.gp.so");
*/

long
testMersenne(ulong p)
{
if (p < 4) return p > 1;
pari_sp av = avma;
GEN n = subiu(int2u(p), 1);
pari_sp btop = avma;
GEN a = utoipos(4);
ulong k;
long ret;
for (k = 2; k <= p; ++k) {
a = remii(shifti(addii(sqri(a), a), 1), n);
if (gc_needed(btop, 1))
a = gerepileuptoint(btop, a);
}
ret = absequaliu(a, 4);
avma = av;
return ret;
}

2017-01-21, 11:53   #9
paulunderwood

Sep 2002
Database er0rr

5·29·31 Posts

Quote:
 Originally Posted by paulunderwood It might be just another 3-PRP test in disguise
The test tst(n)=Mod(Mod(1,n)*(2+I*x),x^2+1)^(n+1)==5+4*I*x is just a 3-PRP test. It follows from studying the left-right exponentiation. Sorry about the SNR. Note "I" is sqrt(-1).

 2017-01-21, 12:00 #10 axn     Jun 2003 2·2,719 Posts This test will work with other seeds of the form 2*a*(a+1) like 4,12,24,40, etc.. Interestingly some of them fail for p=11, declaring it to be prime (for eg:- 60, 760)
2017-01-22, 09:38   #11
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2,341 Posts

Quote:
 Originally Posted by axn This test will work with other seeds of the form 2*a*(a+1) like 4,12,24,40, etc.. Interestingly some of them fail for p=11, declaring it to be prime (for eg:- 60, 760)
I wonder how well it would work for factorials and primorials as seeds?

 Similar Threads Thread Thread Starter Forum Replies Last Post retina Programming 8 2016-05-26 01:37 primus Miscellaneous Math 1 2014-10-12 09:25 henryzz Math 2 2008-04-29 02:05 T.Rex Math 4 2005-05-07 08:25 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 08:52.

Sun Feb 5 08:52:20 UTC 2023 up 171 days, 6:20, 1 user, load averages: 0.34, 0.71, 0.78