New Mersenne primality test
 

[url]http://www.ijcaonline.org/archives/volume100/number3/17505-8053[/url]

Anyone care to find a counter example?

[QUOTE=Prime95;381082][url]http://www.ijcaonline.org/archives/volume100/number3/17505-8053[/url]

Anyone care to find a counter example?[/QUOTE]

one thing I like if this test is true that not even all integer n need to be tested as n needs certain properties for 2np+1 to be a factor. I'll see if I can make this test in pari and test it.

edit: Theorem 2 should fail if the factoring is correct any time [TEX]k_n\gt -6p[/TEX] because then the factors turn into a number greater than (2np+1)^2 so M_p > (2np+1)^2 and you would get a positive fraction or real.

edit2: if I coded in correct pick your choice of counterexample.[CODE](17:57) gp > K(p) =
for(n=1,2^p-1,
if((((2^p-1)-(2*n*p+1)^2)/((6*p)*(2*n*p+1)))<0,
print("Mersenne "p" is prime");
break()
)
)
%3 = (p)->for(n=1,2^p-1,if((((2^p-1)-(2*n*p+1)^2)/((6*p)*(2*n*p+1)))<0,print("Mersenne "p" is prime");break()))
(17:58) gp > for(q=1,1000000000,K(q))
Mersenne 1 is prime
Mersenne 2 is prime
Mersenne 3 is prime
Mersenne 4 is prime
Mersenne 5 is prime
Mersenne 6 is prime
Mersenne 7 is prime
Mersenne 8 is prime
Mersenne 9 is prime
Mersenne 10 is prime
Mersenne 11 is prime
Mersenne 12 is prime
Mersenne 13 is prime
Mersenne 14 is prime
Mersenne 15 is prime
Mersenne 16 is prime
Mersenne 17 is prime
Mersenne 18 is prime
Mersenne 19 is prime
Mersenne 20 is prime
Mersenne 21 is prime
Mersenne 22 is prime
Mersenne 23 is prime
Mersenne 24 is prime
Mersenne 25 is prime
Mersenne 26 is prime
Mersenne 27 is prime
Mersenne 28 is prime
Mersenne 29 is prime
Mersenne 30 is prime
Mersenne 31 is prime
Mersenne 32 is prime
Mersenne 33 is prime
Mersenne 34 is prime
Mersenne 35 is prime
Mersenne 36 is prime
Mersenne 37 is prime
Mersenne 38 is prime
Mersenne 39 is prime
Mersenne 40 is prime
Mersenne 41 is prime
Mersenne 42 is prime
Mersenne 43 is prime
Mersenne 44 is prime
Mersenne 45 is prime
Mersenne 46 is prime
Mersenne 47 is prime
Mersenne 48 is prime
Mersenne 49 is prime
Mersenne 50 is prime
Mersenne 51 is prime
Mersenne 52 is prime
Mersenne 53 is prime
Mersenne 54 is prime
Mersenne 55 is prime
Mersenne 56 is prime
Mersenne 57 is prime[/CODE]

Theorem 2 is a (correct?) way to say the well-known fact that 2np+1 (usually called 2kp+1) can be a factor of 2^p-1. I suspect that the only interesting choices for "n" are those for which 2kp+1 are factors, making this, at best, a silly way to TF.
When Kn is negative, that means that (2kp+1)^2 is larger than Mp, i.e. you've TFed past the square root of the number.

Something missing from their claim of O(n) runtime is the number of candidates for "n" before Kn is negative, which is roughly 2^p / k.

In short: this is [URL="http://stackoverflow.com/a/185576/781792"]O(scary)[/URL], but for small enough values of p, it is faster than LL.

Kris Caldwell [Ref.6 and 8] will be now as famous as Kris Kringle!

P.S. Loved the Table 2. "[I]Modular arithmetic? Never heard of it.[/I]"

science_man_88, that code isnt' correct. Calculate the numerator and denominator separately. If the numerator is negative, then the claim is it is prime. If numerator mod demoninator is 0, then the claim is it is composite. Stop looping through n when one of the results is found.

I didn't found counterexamples to M_p (p prime, p < 10000, n < 100k) for primality, but there are plenty where an answer isn't found in a reasonable time (I limited n to 100k). E.g. M_61, M_67, M_89, M_101, etc. all take a very long time (no surprise these correspond to numbers that are either prime or have large smallest factors). This makes it not very useful. For primes, we need to test n's all the way until (2*p*n+1)^2 > 2^p-1. For p=61 this comes at 12446724. For p=89 it's much larger.

The second page makes much more sense to me when I replace every occurrence of the word "theorem" with the word "conjecture". There is no proof or even handwaving explanation of why the conjectures should hold, other than some results on tiny numbers.

O(n) can't possibly be right. Calculating K_n is clearly not constant time with respect to the size of p. We may need to calculate K_n a stupendously large number of times. I think this is just a roundabout way of saying what Mini-Geek said earlier.

[QUOTE=danaj;381096]science_man_88, that code isnt' correct. Calculate the numerator and denominator separately. If the numerator is negative, then the claim is it is prime. If numerator mod demoninator is 0, then the claim is it is composite
[/QUOTE]

[CODE]%16 = (p)->for(n=1,2^p-1,if((((2^p-1)-(2*n*p+1)^2)/((6*p)*(2*n*p+1)))<0,print("Mersenne "p" is prime,"n);break(),if((((2^p-1)-(2*n*p+1)^2)/((6*p)*(2*n*p+1)))>0&&(((2^p-1)-(2*n*p+1)^2)/((6*p)*(2*n*p+1
))%1==0,print("Mersenne "p" is composite,"n);break())))

(20:16) gp > forprime(q=5,100,K(q))
Mersenne 5 is prime,1
Mersenne 7 is prime,1
Mersenne 11 is composite,1
Mersenne 13 is composite,1
Mersenne 17 is composite,1
Mersenne 19 is composite,1
Mersenne 23 is composite,1
Mersenne 29 is composite,1
Mersenne 31 is composite,1
Mersenne 37 is composite,1
Mersenne 41 is composite,1
Mersenne 43 is composite,1
Mersenne 47 is composite,1
Mersenne 53 is composite,1
Mersenne 59 is composite,1
Mersenne 61 is composite,1
Mersenne 67 is composite,1
Mersenne 71 is composite,1
Mersenne 73 is composite,1
Mersenne 79 is composite,1
Mersenne 83 is composite,1
Mersenne 89 is composite,1
Mersenne 97 is composite,1[/CODE]

edit:apparently I had to mod by 1. for it to work nevermind

This paper is so interesting. Not its content, which is poppycock at best, of course.

But it's interesting that they seem to manage to be both aware of (e.g. LL test run time complexity, largest known Mersenne) and ignorant of (e.g. Sn can be taken mod Mp, 2kp+1 are the only factors) existing knowledge at the same time, while coming up with a complicated but maybe-correct way to prove Mersenne primes (by brute force factorization). It's a bit like someone handed them a copy of the Wikipedia page on Mersenne numbers, but with every other paragraph removed (and no access to other research materials, of course), then gave them a computer and told them to get cracking.

They also (intentionally? accidentally? Hanlon's razor would suggest the latter) have graphs that suggest their method is better than the LL, which while accurate in what they portray, lead you to draw entirely incorrect conclusions (either by graphing too little, or by graphing the wrong thing). And if you graphed Fig 2 a little farther (maybe 17 or 19, definitely at 31), it would make their approach's main problem become crystal clear.

I'm not too inclined for this kind of thing though I'll take a couple more reads through anyway.

My point though is that even I picked up on the fact that they still need to find the correct n to make this work. I'd be interested in seeing them try some bigger numbers. I laughed when I saw M[SUB]11[/SUB] = 2047 as their first example.

"Look how good we are at trying the [B]really[/B] big ones!"

This journal is deservedly on the Beall's list.

Are the more mathematically inclined here able to immediately see that theorem 1 is true? Or is that some "it can be shown that..." bullshit that's fairly complicated?

Theorem 2 is trivial to prove (though not completely stupid) after the definition of Kn.

I was going to suggest we could eliminate all n's less than the k's which have already been attempted for trial factoring but if this method were good trial factoring would be eliminated altogether.

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.

[QUOTE=axn;381116]... And here I am out of ideas, so I stop.[/QUOTE]

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.

As we all know, as slow as it is, this algorithm is also at least [I]twice[/I] slower than it could have been because only half of the "n" values are eligible to produce a factor.

[QUOTE=axn;381116]

6p | Mp/(2pn+1) - (2pn+1). [/QUOTE] 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.

[QUOTE=Prime95;381082][url]http://www.ijcaonline.org/archives/volume100/number3/17505-8053[/url]

Anyone care to find a counter example?[/QUOTE]

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?

On [URL="http://scholarlyoa.com/individual-journals/"]Beall's list[/URL].

Here are [URL="http://scholarlyoa.com/2012/11/30/criteria-for-determining-predatory-open-access-publishers-2nd-edition/"]the criteria[/URL].

[QUOTE=Batalov;381147]On [URL="http://scholarlyoa.com/individual-journals/"]Beall's list[/URL].

Here are [URL="http://scholarlyoa.com/2012/11/30/criteria-for-determining-predatory-open-access-publishers-2nd-edition/"]the criteria[/URL].[/QUOTE]

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 [i]editor[/i] 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.

It makes me laugh that they never take S[SUB]n[/SUB] mod M[SUB]P[/SUB].

[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!)[/QUOTE]

A 292 digit residue for M[SUB]13[/SUB]. They effing quoted the largest Mersenne Prime, yet not one of them tried to extrapolate the size of S[SUB]n[/SUB] for such a test and come to the realization that they've missed a crucial detail because a LL test of 2[SUP]61[/SUP]-1 would require a few thousand Terabyte drives to store S[SUB]59[/SUB]?

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.

Not sure whether I should even feed this thread any more...

Looks like this is [URL="http://www.ieee.ma/biog/essaaidi.html"]the last author's bio[/URL]. 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.