mersenneforum.org New Mersenne primality test
 Register FAQ Search Today's Posts Mark Forums Read

 2014-08-22, 04:38 #12 axn     Jun 2003 535910 Posts This is a really slow way of TF-ing the Mp. The algorithm starts with n=1, and proceeds incrementally, until a factor is found or Mp-(2pn+1)^2 becomes negative (which is a fancy way of saying all numbers less than square root of Mp has been checked). All that is left to prove the theorem is to show that if (2pn+1) | Mp then (6p(2pn+1)) | (Mp-(2pn+1)^2) which is equivalent of saying 6p | Mp/(2pn+1) - (2pn+1). [I guess the theorem would still be true if the 6p term was not there] Since Mp/(2pn+1) is of the form 2pk+1, Mp/(2pn+1) - (2pn+1) = 2p(k-n), so we get the factor of 2p. Therefore we need to show that 3 | (k-n). ... And here I am out of ideas, so I stop.
2014-08-22, 05:22   #13
axn

Jun 2003

23×233 Posts

Quote:
 Originally Posted by axn ... And here I am out of ideas, so I stop.
We have (2pn+1)(2pk+1)=2^p-1 = 1 (mod 3)

The only solution are (2pn+1)=(2pk+1) = 1 (mod 3) or (2pn+1)=(2pk+1) = -1 (mod 3). Either way, we have n=k (mod 3), thus completing the proof.

 2014-08-22, 05:56 #14 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 11·19·47 Posts As we all know, as slow as it is, this algorithm is also at least twice slower than it could have been because only half of the "n" values are eligible to produce a factor.
2014-08-22, 11:53   #15
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by axn 6p | Mp/(2pn+1) - (2pn+1).
if you multiply everything by 2np+1 you get 6p|(2np+1)*Mp-(2np+1)^3 and this can be reduced to 6p | (2np+1*1)-(8*p^3*n^3 + 1) then I tried reducing it using n mod 3 or something but it's that that I think I messed up. edit: this assumes kn to show it's composite.

Last fiddled with by science_man_88 on 2014-08-22 at 12:20

2014-08-22, 17:18   #16
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by Prime95 http://www.ijcaonline.org/archives/v...er3/17505-8053 Anyone care to find a counter example?
This piece of trash was actually published?????

It is clear just by reading the abstract/intro that it is a crank effort.

Who are these nut jobs? Is Essaadi U. a real University? Are
these nut jobs really on the faculty? What kind of fool referee
and editor could let this nonsense get published?

Or is this a 'pay to publish journal' that accepts anything?

 2014-08-22, 17:22 #17 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 11×19×47 Posts On Beall's list. Here are the criteria.
2014-08-22, 18:28   #18
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Batalov On Beall's list. Here are the criteria.
The Journal's Web page claims that it is peer reviewed.

What self-respecting reviewer would ever serve this trash journal?
What self-respecting reviewer would ever accept this trash article?
What kind of editor would actually ask someone to act as
referee? As editor, I would just bounce the article and not even ask
that someone waster their time with it. Just reading the abstract and
intro shows that the paper is crap.

2014-08-22, 19:52   #19
TheMawn

May 2013
East. Always East.

11·157 Posts

It makes me laugh that they never take Sn mod MP.

Quote:
 The Lucas-Lehmer algorithm is very greedy in terms of computer memory since it involves very much large integer numbers for Sn parameter as shown in Table 2 and in Figure 3, even for relatively very small Mersenne prime numbers (e.g. for p = 13 there are 292 digits involved!)
A 292 digit residue for M13. They effing quoted the largest Mersenne Prime, yet not one of them tried to extrapolate the size of Sn for such a test and come to the realization that they've missed a crucial detail because a LL test of 261-1 would require a few thousand Terabyte drives to store S59?

The fact that the modular arithmetic can be used in the algorithm was one of the first things about the process I ever learned. A link to the Lucas-Lehmer Primality Test is pretty easy to find on the Mersenne Prime Wikipedia page. They never referenced the algorithm itself but they referenced mersenne.org when they claimed that the LLT is a good tool, so presumably they would have actually checked out our own page where it is well explained that the residue is taken mod Mp at every iteration...

Maybe they all have tenure.

Last fiddled with by TheMawn on 2014-08-22 at 20:03

 2014-08-23, 04:18 #20 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 90910 Posts Not sure whether I should even feed this thread any more... Looks like this is the last author's bio. I would guess two master's students and the last author as the professor, but it lists them as faculty. I would think with the name attached there would be more concern about the paper (I know my advisor would have been merciless with the red pen even without his name involved). An anecdote that seems apropos: I was attending a master's thesis defense at my school because the subject was interesting. It was about cryptography of some sort, perhaps RSA. I was confused when the performance charts were shown at the end because the key lengths went from 20 to 64. After the faculty questions I asked what units they were -- obviously they couldn't be bits, as that would be absurdly small. To the mortification of the advising professor, indeed that was the bit size, because all the work was in Java and Java bigints didn't support needed features, so they just stopped at a key length of 64 bits. Making all the performance comparisons, which was the culmination of their work, more-or-less meaningless.

 Similar Threads Thread Thread Starter Forum Replies Last Post JonathanM Information & Answers 25 2020-06-16 02:47 primus Miscellaneous Math 1 2014-10-12 09:25 boldi Miscellaneous Math 74 2014-04-17 07:16 T.Rex Math 1 2010-01-03 11:34 Unregistered Information & Answers 4 2007-07-09 00:32

All times are UTC. The time now is 21:55.

Sat May 21 21:55:30 UTC 2022 up 37 days, 19:56, 0 users, load averages: 0.96, 1.18, 1.34