20140821, 20:17  #1 
P90 years forever!
Aug 2002
Yeehaw, FL
1ED1_{16} Posts 
New Mersenne primality test

20140821, 20:44  #2  
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
Quote:
edit: Theorem 2 should fail if the factoring is correct any time because then the factors turn into a number greater than (2np+1)^2 so M_p > (2np+1)^2 and you would get a positive fraction or real. edit2: if I coded in correct pick your choice of counterexample. Code:
(17:57) gp > K(p) = for(n=1,2^p1, if((((2^p1)(2*n*p+1)^2)/((6*p)*(2*n*p+1)))<0, print("Mersenne "p" is prime"); break() ) ) %3 = (p)>for(n=1,2^p1,if((((2^p1)(2*n*p+1)^2)/((6*p)*(2*n*p+1)))<0,print("Mersenne "p" is prime");break())) (17:58) gp > for(q=1,1000000000,K(q)) Mersenne 1 is prime Mersenne 2 is prime Mersenne 3 is prime Mersenne 4 is prime Mersenne 5 is prime Mersenne 6 is prime Mersenne 7 is prime Mersenne 8 is prime Mersenne 9 is prime Mersenne 10 is prime Mersenne 11 is prime Mersenne 12 is prime Mersenne 13 is prime Mersenne 14 is prime Mersenne 15 is prime Mersenne 16 is prime Mersenne 17 is prime Mersenne 18 is prime Mersenne 19 is prime Mersenne 20 is prime Mersenne 21 is prime Mersenne 22 is prime Mersenne 23 is prime Mersenne 24 is prime Mersenne 25 is prime Mersenne 26 is prime Mersenne 27 is prime Mersenne 28 is prime Mersenne 29 is prime Mersenne 30 is prime Mersenne 31 is prime Mersenne 32 is prime Mersenne 33 is prime Mersenne 34 is prime Mersenne 35 is prime Mersenne 36 is prime Mersenne 37 is prime Mersenne 38 is prime Mersenne 39 is prime Mersenne 40 is prime Mersenne 41 is prime Mersenne 42 is prime Mersenne 43 is prime Mersenne 44 is prime Mersenne 45 is prime Mersenne 46 is prime Mersenne 47 is prime Mersenne 48 is prime Mersenne 49 is prime Mersenne 50 is prime Mersenne 51 is prime Mersenne 52 is prime Mersenne 53 is prime Mersenne 54 is prime Mersenne 55 is prime Mersenne 56 is prime Mersenne 57 is prime Last fiddled with by science_man_88 on 20140821 at 21:01 

20140821, 21:01  #3 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
7·13·47 Posts 
Theorem 2 is a (correct?) way to say the wellknown fact that 2np+1 (usually called 2kp+1) can be a factor of 2^p1. I suspect that the only interesting choices for "n" are those for which 2kp+1 are factors, making this, at best, a silly way to TF.
When Kn is negative, that means that (2kp+1)^2 is larger than Mp, i.e. you've TFed past the square root of the number. Something missing from their claim of O(n) runtime is the number of candidates for "n" before Kn is negative, which is roughly 2^p / k. In short: this is O(scary), but for small enough values of p, it is faster than LL. Last fiddled with by MiniGeek on 20140821 at 21:02 
20140821, 21:38  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×29×113 Posts 
Kris Caldwell [Ref.6 and 8] will be now as famous as Kris Kringle!
P.S. Loved the Table 2. "Modular arithmetic? Never heard of it." Last fiddled with by Batalov on 20140821 at 21:39 
20140821, 22:44  #5 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}×101 Posts 
science_man_88, that code isnt' correct. Calculate the numerator and denominator separately. If the numerator is negative, then the claim is it is prime. If numerator mod demoninator is 0, then the claim is it is composite. Stop looping through n when one of the results is found.
I didn't found counterexamples to M_p (p prime, p < 10000, n < 100k) for primality, but there are plenty where an answer isn't found in a reasonable time (I limited n to 100k). E.g. M_61, M_67, M_89, M_101, etc. all take a very long time (no surprise these correspond to numbers that are either prime or have large smallest factors). This makes it not very useful. For primes, we need to test n's all the way until (2*p*n+1)^2 > 2^p1. For p=61 this comes at 12446724. For p=89 it's much larger. The second page makes much more sense to me when I replace every occurrence of the word "theorem" with the word "conjecture". There is no proof or even handwaving explanation of why the conjectures should hold, other than some results on tiny numbers. O(n) can't possibly be right. Calculating K_n is clearly not constant time with respect to the size of p. We may need to calculate K_n a stupendously large number of times. I think this is just a roundabout way of saying what MiniGeek said earlier. 
20140821, 23:17  #6  
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
Quote:
Code:
%16 = (p)>for(n=1,2^p1,if((((2^p1)(2*n*p+1)^2)/((6*p)*(2*n*p+1)))<0,print("Mersenne "p" is prime,"n);break(),if((((2^p1)(2*n*p+1)^2)/((6*p)*(2*n*p+1)))>0&&(((2^p1)(2*n*p+1)^2)/((6*p)*(2*n*p+1 ))%1==0,print("Mersenne "p" is composite,"n);break()))) (20:16) gp > forprime(q=5,100,K(q)) Mersenne 5 is prime,1 Mersenne 7 is prime,1 Mersenne 11 is composite,1 Mersenne 13 is composite,1 Mersenne 17 is composite,1 Mersenne 19 is composite,1 Mersenne 23 is composite,1 Mersenne 29 is composite,1 Mersenne 31 is composite,1 Mersenne 37 is composite,1 Mersenne 41 is composite,1 Mersenne 43 is composite,1 Mersenne 47 is composite,1 Mersenne 53 is composite,1 Mersenne 59 is composite,1 Mersenne 61 is composite,1 Mersenne 67 is composite,1 Mersenne 71 is composite,1 Mersenne 73 is composite,1 Mersenne 79 is composite,1 Mersenne 83 is composite,1 Mersenne 89 is composite,1 Mersenne 97 is composite,1 Last fiddled with by science_man_88 on 20140821 at 23:24 

20140821, 23:58  #7 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
7·13·47 Posts 
This paper is so interesting. Not its content, which is poppycock at best, of course.
But it's interesting that they seem to manage to be both aware of (e.g. LL test run time complexity, largest known Mersenne) and ignorant of (e.g. Sn can be taken mod Mp, 2kp+1 are the only factors) existing knowledge at the same time, while coming up with a complicated but maybecorrect way to prove Mersenne primes (by brute force factorization). It's a bit like someone handed them a copy of the Wikipedia page on Mersenne numbers, but with every other paragraph removed (and no access to other research materials, of course), then gave them a computer and told them to get cracking. They also (intentionally? accidentally? Hanlon's razor would suggest the latter) have graphs that suggest their method is better than the LL, which while accurate in what they portray, lead you to draw entirely incorrect conclusions (either by graphing too little, or by graphing the wrong thing). And if you graphed Fig 2 a little farther (maybe 17 or 19, definitely at 31), it would make their approach's main problem become crystal clear. Last fiddled with by MiniGeek on 20140822 at 00:02 
20140822, 00:09  #8 
May 2013
East. Always East.
11×157 Posts 
I'm not too inclined for this kind of thing though I'll take a couple more reads through anyway.
My point though is that even I picked up on the fact that they still need to find the correct n to make this work. I'd be interested in seeing them try some bigger numbers. I laughed when I saw M_{11} = 2047 as their first example. "Look how good we are at trying the really big ones!" 
20140822, 01:22  #9 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·29·113 Posts 
This journal is deservedly on the Beall's list.

20140822, 01:35  #10 
May 2013
East. Always East.
6BF_{16} Posts 
Are the more mathematically inclined here able to immediately see that theorem 1 is true? Or is that some "it can be shown that..." bullshit that's fairly complicated?
Theorem 2 is trivial to prove (though not completely stupid) after the definition of Kn. 
20140822, 01:54  #11 
May 2013
East. Always East.
11·157 Posts 
I was going to suggest we could eliminate all n's less than the k's which have already been attempted for trial factoring but if this method were good trial factoring would be eliminated altogether.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fastest software for Mersenne primality test?  JonathanM  Information & Answers  25  20200616 02:47 
Conjectured Primality Test for Specific Class of Mersenne Numbers  primus  Miscellaneous Math  1  20141012 09:25 
A (new) old, (faster) slower mersenne(primality) PRP test  boldi  Miscellaneous Math  74  20140417 07:16 
LLT Cycles for Mersenne primality test: a draft  T.Rex  Math  1  20100103 11:34 
Mersenne Primality Test in Hardware  Unregistered  Information & Answers  4  20070709 00:32 