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)[/CODE] :geek: 
[QUOTE=paulunderwood;451252]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)[/CODE] :geek:[/QUOTE] 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. 
Isn't LL a primality test rather than a PRP test?
Is this algo also a deterministic primality test? 
[QUOTE=a1call;451298]Isn't LL a primality test rather than a PRP test?
Is this algo also a deterministic primality test?[/QUOTE] Yes, LL is a primailty test. And, no, this is just a PRP test. It might be just another 3PRP test in disguise  I am not sure about it. :smile: 
So I assume you know of values for p which return true but are in fact yield composite Mersennes. Correct?

[QUOTE=a1call;451301]So I assume you know of values for p which return true but are in fact yield composite Mersennes. Correct?[/QUOTE]
No. I do not know of any counterexamples  maybe there are infinitely many or none. 
Well, that makes it more interesting than just another PRP test.:smile:
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. 
[QUOTE=a1call;451303]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.[/QUOTE] 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; }[/code] 
[QUOTE=paulunderwood;451300]It might be just another 3PRP test in disguise[/QUOTE]
The test [c]tst(n)=Mod(Mod(1,n)*(2+I*x),x^2+1)^(n+1)==5+4*I*x[/c] is just a 3PRP test. It follows from studying the leftright exponentiation. Sorry about the SNR. Note "I" is sqrt(1). :smile: 
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) 
[QUOTE=axn;451321]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)[/QUOTE] I wonder how well it would work for factorials and primorials as seeds? 
All times are UTC. The time now is 19:04. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.