mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2014-08-21, 20:17   #1
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2×5×769 Posts
Default New Mersenne primality test

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

Anyone care to find a counter example?
Prime95 is online now   Reply With Quote
Old 2014-08-21, 20:44   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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

Last fiddled with by science_man_88 on 2014-08-21 at 21:01
science_man_88 is offline   Reply With Quote
Old 2014-08-21, 21:01   #3
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101011102 Posts
Default

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
Mini-Geek is offline   Reply With Quote
Old 2014-08-21, 21:38   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

53·7·11 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2014-08-21, 22:44   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

90910 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2014-08-21, 23:17   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by danaj View Post
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

Last fiddled with by science_man_88 on 2014-08-21 at 23:24
science_man_88 is offline   Reply With Quote
Old 2014-08-21, 23:58   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2·5·7·61 Posts
Default

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
Mini-Geek is offline   Reply With Quote
Old 2014-08-22, 00:09   #8
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

11×157 Posts
Default

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

"Look how good we are at trying the really big ones!"
TheMawn is offline   Reply With Quote
Old 2014-08-22, 01:22   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

53×7×11 Posts
Default

This journal is deservedly on the Beall's list.
Batalov is offline   Reply With Quote
Old 2014-08-22, 01:35   #10
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

6BF16 Posts
Default

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 is offline   Reply With Quote
Old 2014-08-22, 01:54   #11
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

11×157 Posts
Default

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.
TheMawn is offline   Reply With Quote
Reply

Thread Tools


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

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


Tue Dec 7 06:58:47 UTC 2021 up 137 days, 1:27, 0 users, load averages: 1.75, 1.46, 1.33

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.