mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Another way to PRP test Mersenne numbers (https://www.mersenneforum.org/showthread.php?t=21950)

paulunderwood 2017-01-20 08:51

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)[/CODE]

:geek:

science_man_88 2017-01-20 12:41

[QUOTE=paulunderwood;451252]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)[/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.

a1call 2017-01-20 23:25

Isn't LL a primality test rather than a PRP test?
Is this algo also a deterministic primality test?

paulunderwood 2017-01-21 00:28

[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 3-PRP test in disguise -- I am not sure about it. :smile:

a1call 2017-01-21 00:48

So I assume you know of values for p which return true but are in fact yield composite Mersennes. Correct?

paulunderwood 2017-01-21 01:27

[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.

a1call 2017-01-21 01:38

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.

CRGreathouse 2017-01-21 05:31

[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]

paulunderwood 2017-01-21 11:53

[QUOTE=paulunderwood;451300]It might be just another 3-PRP 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 3-PRP test. It follows from studying the left-right exponentiation. Sorry about the SNR. Note "I" is sqrt(-1). :smile:

axn 2017-01-21 12:00

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)

a1call 2017-01-22 09:38

[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.