New Mersenne primality test - Page 2

axn · 2014-08-22, 04:38

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 · 2014-08-22, 05:22

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.

Batalov · 2014-08-22, 05:56

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.

science_man_88 · 2014-08-22, 11:53

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.

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

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?

Batalov · 2014-08-22, 17:22

On Beall's list.

Here are the criteria.

R.D. Silverman · 2014-08-22, 18:28

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.

TheMawn · 2014-08-22, 19:52

It makes me laugh that they never take S_n mod M_P.

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 M₁₃. They effing quoted the largest Mersenne Prime, yet not one of them tried to extrapolate the size of S_n for such a test and come to the realization that they've missed a crucial detail because a LL test of 2⁶¹-1 would require a few thousand Terabyte drives to store S₅₉?

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.

danaj · 2014-08-23, 04:18

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
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

2014-08-22, 04:38	#12
axn Jun 2003 5359₁₀ 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: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, 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-23, 04:18	#20
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 909₁₀ 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.