mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-01-20, 08:51   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1111011000102 Posts
Default 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)
paulunderwood is online now   Reply With Quote
Old 2017-01-20, 12:41   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-01-20, 23:25   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

87E16 Posts
Default

Isn't LL a primality test rather than a PRP test?
Is this algo also a deterministic primality test?
a1call is offline   Reply With Quote
Old 2017-01-21, 00:28   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·11·179 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
paulunderwood is online now   Reply With Quote
Old 2017-01-21, 00:48   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,087 Posts
Default

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
a1call is offline   Reply With Quote
Old 2017-01-21, 01:27   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·11·179 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
paulunderwood is online now   Reply With Quote
Old 2017-01-21, 01:38   #7
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

41768 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2017-01-21, 05:31   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135338 Posts
Default

Quote:
Originally Posted by a1call View Post
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;
}
CRGreathouse is offline   Reply With Quote
Old 2017-01-21, 11:53   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·11·179 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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).
paulunderwood is online now   Reply With Quote
Old 2017-01-21, 12:00   #10
axn
 
axn's Avatar
 
Jun 2003

5,197 Posts
Default

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)
axn is offline   Reply With Quote
Old 2017-01-22, 09:38   #11
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,087 Posts
Default

Quote:
Originally Posted by axn View Post
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?
a1call is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Regex can test for prime numbers retina Programming 8 2016-05-26 01:37
Conjectured Primality Test for Specific Class of Mersenne Numbers primus Miscellaneous Math 1 2014-10-12 09:25
6 digit numbers and the mersenne numbers henryzz Math 2 2008-04-29 02:05
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25
A primality test for Fermat numbers faster than P├ępin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 23:58.


Sun Dec 5 23:58:10 UTC 2021 up 135 days, 18:27, 0 users, load averages: 1.11, 1.17, 1.26

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.