Another way to PRP test Mersenne numbers

[paulunderwood]

Not as efficient as LL:

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)

[science_man_88]

Originally Posted by paulunderwood

Not as efficient as LL:

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.

[a1call]

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

[paulunderwood]

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.

[a1call]

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

[paulunderwood]

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.

[a1call]

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.

[CRGreathouse]

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.

#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;
}

[paulunderwood]

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

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

[a1call]

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?