20150305, 17:30  #1 
Jul 2014
3·149 Posts 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"
Hi,
I'm not sure whether this has been discussed. I searched for it here on the forums but didn't find anything. I'm expecting that it's naïve to think it's not known about here especially since there was a post about this on the mailing list about a year ago. The post was about a new way of testing whether or not Mersenne numbers are prime or not. The post included a link to this article : http://ijcaonline.org/archives/volum...er3/175058053 I was half expecting a new program to be in use by now by the GIMPS and I don't believe one is so I'm starting to wonder why (since the document clearly outlines the details and is mathematically sound). So can someone update me on the effect this news had on the mersenne.org community  i.e what the response was, and if there are any plans to use this algorithm. 
20150305, 18:04  #2 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×2,399 Posts 
http://www.mersenneforum.org/showthread.php?p=381194
That article, the test, isn't worth the figurative paper it's printed on. 
20150305, 19:10  #3 
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
1175_{16} Posts 
Yes MP13 does only take 4 iterations ...
... to determine it is prime vs 11 iterations for Prime95... WOW?!?!?!?
However, it took 1,525 iterations for MP59 to find the first factor 748 iterations to determine MP31 is prime and it quickly gets much worse. 
20150305, 20:13  #4 
Jul 2014
3·149 Posts 
Thanks Guys.
So is it just the claim that it's more efficient CPU time  wise that's wrong ? Does the algorithm actually work? There was no proof on the paper so I'm unable to even attempt to work the answer out for myself. 
20150305, 20:33  #5 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
16035_{8} Posts 
Read the other thread I linked. The algorithm is basically trial factoring, like mfakt*, except done really really really really poorly.

20150305, 20:34  #6 
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
41×109 Posts 
Using Excel I was able to verify that it works at least up to MP61.....a LONG LONG way from where Prime95 is currently

20150305, 20:41  #7 
Jul 2014
110111111_{2} Posts 
Without proof it really is useless except to them if they've got one, but why would they keep the proof secret?

20150305, 22:17  #8 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,161 Posts 
The proof is obvious, however the test is impractical. (I am trying to use only nice words.)
It is important to know that "ijcaonline" is a predatory "journal" that publishes anything as long as the submitters pay the required fee. As such, it should be avoided for reading (and as for writing/publishing  only if one likes to publish on the walls of public restrooms; it's the same sort of thing). 
20150305, 22:47  #9  
∂^{2}ω=0
Sep 2002
República de California
3^{2}·1,093 Posts 
Quote:
In theory I can do a rigorous '1iteration' test of any M(p) by simply feeding it to e.g. the Pari 'factor' command. In practice, once p gets larger than a few hundred bits, the needed runtime becomes impractically large. 

20150306, 00:30  #10  
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
8890_{10} Posts 
Quote:
Quote:


20150306, 02:11  #11 
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
did I do the math correct ?
I know I shouldn't play with this, However I manipulated the equation in Theorem 1 to:
where k is such that 2*k*p+1 is Mp I was thinking of manipulating it more, but if I've messed up already it's pointless to try to extrapolate further. EDIT: I think I messed up the +3/2 part I think it should be 3/2 now that I looked over my manipulation on paper. EDIT2: I found a fatal error I failed to correct further up if only I hadn't gone through 27 steps. Last fiddled with by science_man_88 on 20150306 at 02:53 Reason: had to edit what I said needed editing. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GQQ: a "deterministic" "primality" test in O(ln n)^2  Chair Zhuang  Miscellaneous Math  21  20180326 22:33 
Speeding up double checking when first test returns "prime"  Unregistered  PrimeNet  16  20060228 02:00 
P1 B1/B2 selection with "Test=" vs "Pfactor="  James Heinrich  Software  2  20050319 21:58 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 