New Mersenne primality test

Prime95 · 2014-08-21, 20:17

http://www.ijcaonline.org/archives/v...er3/17505-8053

Anyone care to find a counter example?

science_man_88 · 2014-08-21, 20:44

Quote:

Originally Posted by Prime95

http://www.ijcaonline.org/archives/v...er3/17505-8053

Anyone care to find a counter example?

one thing I like if this test is true that not even all integer n need to be tested as n needs certain properties for 2np+1 to be a factor. I'll see if I can make this test in pari and test it.

edit: Theorem 2 should fail if the factoring is correct any time $k_n\gt -6p$ 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^p-1,
if((((2^p-1)-(2*n*p+1)^2)/((6*p)*(2*n*p+1)))<0,
print("Mersenne "p" is prime");
break()
  )
)
%3 = (p)->for(n=1,2^p-1,if((((2^p-1)-(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

Mini-Geek · 2014-08-21, 21:01

Theorem 2 is a (correct?) way to say the well-known fact that 2np+1 (usually called 2kp+1) can be a factor of 2^p-1. 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.

Batalov · 2014-08-21, 21:38

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

danaj · 2014-08-21, 22:44

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^p-1. 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 Mini-Geek said earlier.

science_man_88 · 2014-08-21, 23:17

Quote:

Originally Posted by danaj

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

Code:

%16 = (p)->for(n=1,2^p-1,if((((2^p-1)-(2*n*p+1)^2)/((6*p)*(2*n*p+1)))<0,print("Mersenne "p" is prime,"n);break(),if((((2^p-1)-(2*n*p+1)^2)/((6*p)*(2*n*p+1)))>0&&(((2^p-1)-(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

edit:apparently I had to mod by 1. for it to work nevermind

Mini-Geek · 2014-08-21, 23:58

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 maybe-correct 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.

TheMawn · 2014-08-22, 00:09

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₁₁ = 2047 as their first example.

"Look how good we are at trying the really big ones!"

Batalov · 2014-08-22, 01:22

This journal is deservedly on the Beall's list.

TheMawn · 2014-08-22, 01:35

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.

TheMawn · 2014-08-22, 01:54

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.

2014-08-21, 20:17	#1
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 2²×3×659 Posts	New Mersenne primality test http://www.ijcaonline.org/archives/v...er3/17505-8053 Anyone care to find a counter example?

2014-08-21, 21:01	#3
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 4278₁₀ Posts	Theorem 2 is a (correct?) way to say the well-known fact that 2np+1 (usually called 2kp+1) can be a factor of 2^p-1. 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 Mini-Geek on 2014-08-21 at 21:02

2014-08-21, 21:38	#4
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2⁷·7·11 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 2014-08-21 at 21:39

2014-08-21, 23:58	#7
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 10266₈ 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 maybe-correct 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 Mini-Geek on 2014-08-22 at 00:02

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Fastest software for Mersenne primality test?	JonathanM	Information & Answers	25	2020-06-16 02:47
Conjectured Primality Test for Specific Class of Mersenne Numbers	primus	Miscellaneous Math	1	2014-10-12 09:25
A (new) old, (faster) slower mersenne-(primality) PRP test	boldi	Miscellaneous Math	74	2014-04-17 07:16
LLT Cycles for Mersenne primality test: a draft	T.Rex	Math	1	2010-01-03 11:34
Mersenne Primality Test in Hardware	Unregistered	Information & Answers	4	2007-07-09 00:32

2014-08-21, 22:44	#5
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 3²·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 (2pn+1)^2 > 2^p-1. 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 Mini-Geek said earlier.

2014-08-22, 00:09	#8
TheMawn 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₁₁ = 2047 as their first example. "Look how good we are at trying the really big ones!"

2014-08-22, 01:22	#9
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23200₈ Posts	This journal is deservedly on the Beall's list.

2014-08-22, 01:35	#10
TheMawn May 2013 East. Always East. 1727₁₀ 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.

2014-08-22, 01:54	#11
TheMawn 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.