mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2015-03-05, 17:30   #1
wildrabbitt
 
Jul 2014

19·23 Posts
Default Aouessare-El Haddouchi-Essaaidi "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/17505-8053

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.
wildrabbitt is offline   Reply With Quote
Old 2015-03-05, 18:04   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100001101012 Posts
Default

http://www.mersenneforum.org/showthread.php?p=381194

That article, the test, isn't worth the figurative paper it's printed on.
Dubslow is offline   Reply With Quote
Old 2015-03-05, 19:10   #3
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

102568 Posts
Default 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.
petrw1 is offline   Reply With Quote
Old 2015-03-05, 20:13   #4
wildrabbitt
 
Jul 2014

6658 Posts
Default

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.
wildrabbitt is offline   Reply With Quote
Old 2015-03-05, 20:33   #5
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

722110 Posts
Default

Quote:
Originally Posted by wildrabbitt View Post
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.
Read the other thread I linked. The algorithm is basically trial factoring, like mfakt*, except done really really really really poorly.
Dubslow is offline   Reply With Quote
Old 2015-03-05, 20:34   #6
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

2·5·7·61 Posts
Default

Quote:
Originally Posted by wildrabbitt View Post
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.
Using Excel I was able to verify that it works at least up to MP61.....a LONG LONG way from where Prime95 is currently
petrw1 is offline   Reply With Quote
Old 2015-03-05, 20:41   #7
wildrabbitt
 
Jul 2014

19×23 Posts
Default

Without proof it really is useless except to them if they've got one, but why would they keep the proof secret?
wildrabbitt is offline   Reply With Quote
Old 2015-03-05, 22:17   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

11×19×43 Posts
Default

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).
Batalov is offline   Reply With Quote
Old 2015-03-05, 22:47   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

17×643 Posts
Default

Quote:
Originally Posted by wildrabbitt View Post
Without proof it really is useless except to them if they've got one, but why would they keep the proof secret?
The point is, even with proof of correctness the test is useless in practice.

In theory I can do a rigorous '1-iteration' 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.
ewmayer is offline   Reply With Quote
Old 2015-03-06, 00:30   #10
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

1E7116 Posts
Default

Quote:
Originally Posted by Batalov View Post
It is important to know that "ijcaonline" is a predatory "journal" that publishes anything as long as the submitters pay the required fee.
Same idea
Uncwilly is offline   Reply With Quote
Old 2015-03-06, 02:11   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default did I do the math correct ?

I know I shouldn't play with this, However I manipulated the equation in Theorem 1 to:

k>(2np^2-2np+\frac{3}{2}p) 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 2015-03-06 at 02:53 Reason: had to edit what I said needed editing.
science_man_88 is offline   Reply With Quote
Reply

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 2018-03-26 22:33
Speeding up double checking when first test returns "prime" Unregistered PrimeNet 16 2006-02-28 02:00
P-1 B1/B2 selection with "Test=" vs "Pfactor=" James Heinrich Software 2 2005-03-19 21:58
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 16:18.

Wed Apr 8 16:18:26 UTC 2020 up 14 days, 13:51, 3 users, load averages: 1.56, 1.73, 1.91

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.