A (new) old, (faster) slower mersenne-(primality) PRP test

[boldi]

Originally Posted by tapion64

I swear I've seen that conjecture somewhere on the multitude of sites I've been looking at over the past week, but I can't seem to find it. I believe there's a link in one of the GIMPS section threads that mentions it. A similar test is Pepin's:

3^[(Fn-1)/2] = (-1) mod Fn

For Fermat numbers. It seems reasonable that someone conjectured an analogue for Mersenne primes, I just can't find it at the moment. Actually, square both sides of the above and you get 3^(Fn-1) = 1 mod Fn, so maybe you had it mixed up that the conjecture was for Mersenne primes. Clearly if it holds for Fermat numbers, then it doesn't just hold for Mersenne primes.

Thx,

I will keep this in mind.

Greetings
boldi

[R.D. Silverman]

Originally Posted by boldi

Thx,

I will keep this in mind.

Greetings
boldi

And of course, you ignore the request to provide reasoning as to
why you think the "conjecture" should be true.

[boldi]

Originally Posted by R.D. Silverman

And of course, you ignore the request to provide reasoning as to
why you think the "conjecture" should be true.

Far from it.

Please give me a little time, You will get the answer. First I have to show a proof for something other. I think, You know what I mean. ;-)

Greetings
boldi

[boldi]

Hi folks,

as I have said, if the conjecture holds, it leads to a faster Mersenne prime test. So it is worth to think about it. Here I give the proof that the algorithm I have shown, is faster than the Lucas-Lehmer test.

We take a number-cruncher like Pari/GP from http://pari.math.u-bordeaux.fr/ and write down 2 routines:


/*----------------------------------------------------------
Lucas Lehmer Test
------------------------------------------------------------*/
LucasLehmerTest(p)={

local(M, s, i);

M = 1<<p - 1;
s = 4;

for(i=2, p-1, s = Mod(s*s - 2, M));

if(s == 0, print(p, " prime"), print(p, " no prime"));
}


/*------------------------------------------------------------
New Mersenne Test
--------------------------------------------------------------*/
NewMersenneTest(p)={

local(M, b, i);

M = 1<<p - 1;
b = 3;

for(i=1, p-1, b = Mod(b*b, M));

if (b+3 == M, print(p, " prime"), print(p, " no prime"));
}
/*------------------------------------------------------------*/


As You can see, both routines ar written similar. Running a test I have got follow results:

LucasLehmerTest(132049) needs 11min, 41,686ms
NewMersenneTest(132049) needs 11min, 37,448ms

So the new test is 4,2 sec faster.

But the next thing is, I have never told, that the recursive algorithm is the best way, to calculate the congruence. I have shown it only as an example to point out, that the congruence leads at least to an algorithm, wich is similar and simple as LL.

The best way for calculating the congruence is, to find a fast modular exponentiation. (It would be great, if we could discuse this topic here.) For the moment I show the difference between best programmed Lucas Lehmer test and best programmed new Mersenne test with modular exponentiation in Pari.

We write down 2 routines: The fastest way to implement Lucas Lehmer and the new Mersenne test on Pari/GP is the following code:

/*----------------------------------------------------------
Lucas Lehmer test as fast as possible in Pari/GP
------------------------------------------------------------*/
LucasLehmerFast(p)={

local(s,n);

my(s = Mod(4, 1<<p-1));
for(n = 3, p, s = s^2 - 2);

if (s == 0, print(p, " prime"), print(p, " no prime"));
}

/*----------------------------------------------------------
New Mersenne test as fast as possible in Pari/GP
------------------------------------------------------------*/
NewMersenneFast(p) = {

local(m, m1, m2, b);

m = 1<<p - 1;
m1 = m - 1;
m2 = m1 / 2;

b = lift(Mod(3, m)^m2);

if (b == M1, print(p, " prime"), print(p, " no prime"));
}
/*------------------------------------------------------------*/

Running a test I have got the following results:

LucasLehmerFast(132049) needs 11min, 39,555ms
NewMersenneFast(132049) needs 10min, 29,338ms

So the new test ist 1min 10 sec faster than Lucas Lehmer. In other words: If it needs 110 days with LL to check if the next big Mersenne is prime or not, with the new test it needs only 100 days. But please be aware: We are testing a lot of numbers, so in sum with the new test we could save a lot of time.

As the member axn has correct pointed out, for this test I have not used the congruence

As I have said, further optimizations are possible. There are several ways to write down the congruence. For the last test I have used the congruence wich is also valid.


Greetings
boldi

[Batalov]

Originally Posted by boldi

Thank You for the link.

First of all: In my postings I have never said my conjecture must be true.

On the contrary: In my first post I have pointed out, the conjecture needs a strong mathematical proof.

And all I ask is: Is there a proof for the conjecture, that only Mersenne primes can pass the congruence

mod

You tell me, they have proved a theorem -- thanks (I mean this seriosley), but where is this proof? In the paper You have linked I can see no answer for my question.

Greetings
boldi

Well, there, you've demonstrated that you also cannot read.

They have proved their theorem. I repeat: their theorem.
"Your" "conjecture" is the converse of little Fermat and is known for centuries to be proven - that is, proven false. Did you get this? I repeat: proven false.

[R.D. Silverman]

Originally Posted by boldi

Hi folks,

as I have said, if the conjecture holds, it leads to a faster Mersenne prime test.

When one continues to spout incorrect dogma when presented with
facts that contradict that dogma, one tends to lose all credibility.

Your test is NOT faster. It is slower. It requires MORE multi-precision
multiplications. It is more work to perform multi-precision exponentiation
with an exponent of length k when the exponent contains 1 bits
(indeed; almost all bits are 1 for M_p) than it is to do k squarings.

So it is worth to think about it. Here I give the proof that the algorithm I have shown, is faster than the Lucas-Lehmer test.

/*----------------------------------------------------------
Lucas Lehmer Test
------------------------------------------------------------*/
LucasLehmerTest(p)={

local(M, s, i);

M = 1<<p - 1;
s = 4;

for(i=2, p-1, s = Mod(s*s - 2, M));

if(s == 0, print(p, " prime"), print(p, " no prime"));
}


/*------------------------------------------------------------
New Mersenne Test
--------------------------------------------------------------*/
NewMersenneTest(p)={

local(M, b, i);

M = 1<<p - 1;
b = 3;

for(i=1, p-1, b = Mod(b*b, M));

if (b+3 == M, print(p, " prime"), print(p, " no prime"));
}
/*------------------------------------------------------------*/


As You can see, both routines ar written similar. Running a test I have got follow results:

LucasLehmerTest(132049) needs 11min, 41,686ms
NewMersenneTest(132049) needs 11min, 37,448ms

So the new test is 4,2 sec faster.

Moron. Complete Moron. Actually, I take it back. You'd have to
become a good deal more intelligent to become a moron.

(1) Your second piece of code does NOT COMPUTE 3^(N-1) mod N.
(2) If you imagine that tiny run time differences in *interpreted*
code with "similar" code proves one method is better, then you truly
are not only a moron, you are an imbecile studying to be a moron.
This is especially true when one of the pieces of code DOES NOT COMPUTE
WHAT YOU CLAIM.


<rest of nonsense deleted>

I bring back my old signature. It is relevant here.

"You can lead a horse's ass to knowledge, but you can't make him think"

[tapion64]

Originally Posted by R.D. Silverman

When one continues to spout incorrect dogma when presented with
facts that contradict that dogma, one tends to lose all credibility.

Your test is NOT faster. It is slower. It requires MORE multi-precision
multiplications. It is more work to perform multi-precision exponentiation
with an exponent of length k when the exponent contains 1 bits
(indeed; almost all bits are 1 for M_p) than it is to do k squarings.




Moron. Complete Moron. Actually, I take it back. You'd have to
become a good deal more intelligent to become a moron.

(1) Your second piece of code does NOT COMPUTE 3^(N-1) mod N.
(2) If you imagine that tiny run time differences in *interpreted*
code with "similar" code proves one method is better, then you truly
are not only a moron, you are an imbecile studying to be a moron.
This is especially true when one of the pieces of code DOES NOT COMPUTE
WHAT YOU CLAIM.


<rest of nonsense deleted>

I bring back my old signature. It is relevant here.

"You can lead a horse's ass to knowledge, but you can't make him think"

The code squares b mod M a total of p-1 times. b^2 -> b^4 -> ... b^(2^p) or b^(2^(p-1)). 2^(p-1) = (M+1)/2 times, then from there you can see that if (M-1)/2 as the exponent yields -1, then 3^(M+1)/2 = -3 mod M, which is why the part at the end says b + 3 == M, although it may be necessary to take it mod M and check for 0. Not sure if it matters.

Either way, he's stated that he's not using 3^(N-1) mod N, pay attention.

[boldi]

Originally Posted by R.D. Silverman

When one continues to spout incorrect dogma when presented with facts that contradict that dogma, one tends to lose all credibility.

Where are Your facts? I can only see unproved claims.

Your test is NOT faster. It is slower. It requires MORE multi-precision multiplications. It is more work to perform multi-precision exponentiation with an exponent of length k when the exponent contains 1 bits (indeed; almost all bits are 1 for M_p) than it is to do k squarings.

Code the routines and run a test: You will see, it is faster. Please also remember what I have said: The conjecture leads to a faster primality test, I have nothing said about the way it does. I have nowhere claimed to use the congruence 3^(M-1) mod M for practical calculations.

You should read more seriosley.

(1) Your second piece of code does NOT COMPUTE 3^(N-1) mod N.

You are absolutely right, but where have I claimed to do so?

I surely I take the optimization.

(2) If you imagine that tiny run time differences in *interpreted* code with "similar" code proves one method is better, then you truly are not only a moron, you are an imbecile studying to be a moron. This is especially true when one of the pieces of code DOES NOT COMPUTE WHAT YOU CLAIM.

I can give You the proof also in compiled code, if You wish.

But another question: Where is Your proof, that LL is faster?

I have not seen any programm code from You. All I can read from You are claims.

Moron. Complete Moron. Actually, I take it back. You'd have to
become a good deal more intelligent to become a moron.
<rest of nonsense deleted>
I bring back my old signature. It is relevant here.
"You can lead a horse's ass to knowledge, but you can't make him think"

Your insults are unnecessary and unscientific. If you want to be taken seriousley, please behave yourself as a scientist.

Ok folks, I think, now I have earned a coffee break. See You later.


Greetings
boldi

[paulunderwood]

Originally Posted by boldi

Hi folks,

...So the new test ist 1min 10 sec faster than Lucas Lehmer. In other words: If it needs 110 days with LL to check if the next big Mersenne is prime or not, with the new test it needs only 100 days. But please be aware: We are testing a lot of numbers, so in sum with the new test we could save a lot of time...

Greetings
boldi

I don't think you can compare optimized Pari-GP internals for expmod with other unoptimized code. Therefore you cannot extrapolate to Prime95/mprime timings. Even if your test was a proof, it might save less than one second on a test which takes P95 60 days

[science_man_88]

Originally Posted by boldi

Code the routines and run a test: You will see, it is faster. Please also remember what I have said: The conjecture leads to a faster primality test, I have nothing said about the way it does. I have nowhere claimed to use the congruence 3^(M-1) mod M for practical calculations.

I have copied your code, and get that is not prime.

? NewMersenneFast(p) = {

local(m, m1, m2, b);

m = 1<<p - 1;
m1 = m - 1;
m2 = m1 / 2;

b = lift(Mod(3, m)^m2);

if (b == M1, print(p, " prime"), print(p, " no prime"));
}
? NewMersenneFast(132049)
  ***   at top-level: NewMersenneFast(1320
  ***                 ^--------------------
  ***   in function NewMersenneFast: ...1;m2=m1/2;b=lift(Mod(3,m)^m2);if(b==M1,print(
  ***                                                            ^--------------------
  *** _^_: user interrupt after 1min, 45,507 ms.

  ***   Break loop: type <Return> to continue; 'break' to go back to GP
break>
? NewMersenneFast(1061)
1061 no prime
? NewMersenneFast(7)
7 no prime

Though I've said things that you might like, I get why in the end you need to prove it works to only find primes, namely Pseudoprimes

[paulunderwood]

There is an error in the code as pari is case sensitive: m1 is not M1