mersenneforum.org Another way to PRP test Mersenne numbers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2017-01-20, 08:51 #1 paulunderwood     Sep 2002 Database er0rr 3×11×107 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
Dumbassville

203008 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 7·283 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

3·11·107 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 36758 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

DCB16 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 7BD16 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

3×1,987 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

3·11·107 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 10010111010102 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

7×283 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?

 Thread Tools

 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 13:08.

Tue Jan 19 13:08:40 UTC 2021 up 47 days, 9:19, 0 users, load averages: 1.73, 1.45, 1.44

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.