mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2014-08-22, 04:38   #12
axn
 
axn's Avatar
 
Jun 2003

7·683 Posts
Default

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.
axn is offline   Reply With Quote
Old 2014-08-22, 05:22   #13
axn
 
axn's Avatar
 
Jun 2003

7·683 Posts
Default

Quote:
Originally Posted by axn View Post
... 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.
axn is offline   Reply With Quote
Old 2014-08-22, 05:56   #14
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100011110010102 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2014-08-22, 11:53   #15
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by axn View Post

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
science_man_88 is offline   Reply With Quote
Old 2014-08-22, 17:18   #16
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 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?
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?
R.D. Silverman is offline   Reply With Quote
Old 2014-08-22, 17:22   #17
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23CA16 Posts
Default

On Beall's list.

Here are the criteria.
Batalov is offline   Reply With Quote
Old 2014-08-22, 18:28   #18
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2014-08-22, 19:52   #19
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

11·157 Posts
Default

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
TheMawn is offline   Reply With Quote
Old 2014-08-23, 04:18   #20
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

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.
danaj 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 12:01.

Tue Dec 1 12:01:59 UTC 2020 up 82 days, 9:12, 1 user, load averages: 1.79, 2.18, 2.12

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.