20170120, 08:51  #1 
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^p1,a=Mod(4,n),b=a+1);for(k=2,p,a=2*a*b;b=a+1);print(p" "a==4) 
20170120, 12:41  #2  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:
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. 

20170120, 23:25  #3 
"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? 
20170121, 00:28  #4 
Sep 2002
Database er0rr
3·11·107 Posts 

20170121, 00:48  #5 
"Rashid Naimi"
Oct 2015
Remote to Here/There
3675_{8} 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 20170121 at 00:48 
20170121, 01:27  #6 
Sep 2002
Database er0rr
DCB_{16} Posts 

20170121, 01:38  #7 
"Rashid Naimi"
Oct 2015
Remote to Here/There
7BD_{16} 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. 
20170121, 05:31  #8  
Aug 2006
3×1,987 Posts 
Quote:
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; } 

20170121, 11:53  #9 
Sep 2002
Database er0rr
3·11·107 Posts 

20170121, 12:00  #10 
Jun 2003
1001011101010_{2} 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) 
20170122, 09:38  #11 
"Rashid Naimi"
Oct 2015
Remote to Here/There
7×283 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Regex can test for prime numbers  retina  Programming  8  20160526 01:37 
Conjectured Primality Test for Specific Class of Mersenne Numbers  primus  Miscellaneous Math  1  20141012 09:25 
6 digit numbers and the mersenne numbers  henryzz  Math  2  20080429 02:05 
LLT numbers, linkd with Mersenne and Fermat numbers  T.Rex  Math  4  20050507 08:25 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 