mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2014-04-13, 20:31   #1
boldi
 
Apr 2014

2×7 Posts
Default A (new) old, (faster) slower mersenne-(primality) PRP test

(First of all please excuse my bad English)

Conjecture: Let p be a odd prime number. Then the Mersenne number M = 2^p -1 holds the congruence relation

3^(M-1) ≡ 1 mod M

if, and only if M is prime. (In comparison to little Fermat theorem there is no Mersenne-pseudoprime who can hold the congruence relation.)

This can be used as a Mersenne primality test. To proof, if a Mersenne number is prime, only check if it holds the congruence relation 3^(M-1) ≡ 1 mod M

Example:
p=7: 3^(127-1)-1 mod 127 = 1 --> prime
p=11: 3^(2047-1)-1 mod 2047 = 1013 --> not prime

I have tested it and it is valid for all Mersenne numbers M = 2^p-1 for p=2 to 23209. But what it needs is a strong mathematical proof.

From the congruence relation we can extract a recursive calculation algorithm if a Mersenne number is prime or not. (It is pretty similar to Lucas-Lehmer test, but a little bit simpler and faster)

I will show an example how it works: Let be p=7 a prime number and the Mersenne number is M_7 = 2^7-1 = 127. Now we want to proof, that M_7 is prim or not. So we are calculating recursive the sequence

S_n = S_(n-1) ∙ S_(n-1) mod M with S_0=3

The sequence will be calculated from n=1 to n=p-1, in our case from 1 to 6:

S_1 = 3∙3 mod 127=9
S_2 = 9∙9 mod 127=81
S_3 = 81∙81 mod 127=84
S_4 = 84∙84 mod 127=71
S_5 = 71∙71 mod 127=88
S_6 = 88∙88 mod 127=124

As result we have got 124. Now we are test, if 124 + S_0 = M_7. If yes, then M ist prime, if no, M is no prime. In our case we have 124 + 3 = 127 = M_7, so M_7 is prime.

Here the code in C:

bool MersennnePrimeTest(p)
{
Bigint n, M, S;

M = 2^p – 1;
S = 3;

for(n = 1, n <= p – 1, n++) S = S*S % M;

if(S + 3 == M) return(true); //M = prime;
else return(false); //M = not prime
}

This test is simpler and faster than the Lucas-Lehmer test, because we have no subtraction. (In Lucas-Lehmer-test we have to calculate the sequence S_n=S_(n-1)∙S_(n-1) - 2 mod M)

greetings
boldi

Last fiddled with by boldi on 2014-04-13 at 21:21
boldi is offline   Reply With Quote
Old 2014-04-13, 20:52   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

9,791 Posts
Default

If you think is either new (it isn't), or faster than LL (also false), or a rigorous test of primality (again, no), you are in dire need of a course (or reading-yourself) in elementary number theory.
ewmayer is offline   Reply With Quote
Old 2014-04-13, 20:56   #3
Qubit
 
Qubit's Avatar
 
Jan 2014

2×19 Posts
Default

Quote:
Originally Posted by boldi View Post
Conjecture: Let p be a prime number. Then the Mersenne number M = 2^p -1 holds the congruence relation

3^(M-1) ≡ 1 mod M

if, and only if M is prime.

I have tested it and it is valid for all Mersenne numbers M = 2^p-1 for p=2 to 23209. But what it needs is a strong mathematical proof.
Perhaps I misunderstood, but for M = 3 we get 3^2 = 9, which is 0 mod 3.

Last fiddled with by Qubit on 2014-04-13 at 20:57
Qubit is offline   Reply With Quote
Old 2014-04-13, 21:01   #4
tapion64
 
Apr 2014

5×17 Posts
Default

Quote:
Originally Posted by Qubit View Post
Perhaps I misunderstood, but for M = 3 we get 3^2 = 9, which is 0 mod 3.
That's because 3 is the only Mersenne prime index with an even multiplicative order mod 2, which in general just makes all these special rules not apply to it. I'll have to look into this.
tapion64 is offline   Reply With Quote
Old 2014-04-13, 21:02   #5
Qubit
 
Qubit's Avatar
 
Jan 2014

2×19 Posts
Default

edit: Whoops, miscalculation.

Last fiddled with by Qubit on 2014-04-13 at 21:12
Qubit is offline   Reply With Quote
Old 2014-04-13, 21:09   #6
boldi
 
Apr 2014

2×7 Posts
Default

Quote:
Originally Posted by Qubit View Post
Perhaps I misunderstood, but for M = 3 we get 3^2 = 9, which is 0 mod 3.
Thank You for this statement. I have to specify the conjecture:

Conjecture: Let p be a odd prime number. Then the Mersenne number M = 2^p -1 holds the congruence relation

3^(M-1) ≡ 1 mod M

if, and only if M is prime. (In comparison to little Fermat theorem there is no Mersenne-pseudoprime who can hold the congruence relation.)

Greetings
boldi
boldi is offline   Reply With Quote
Old 2014-04-13, 21:17   #7
boldi
 
Apr 2014

168 Posts
Default

Quote:
Originally Posted by ewmayer View Post
If you think is either new (it isn't)
You have forgotten to name the paper, where this topic is discused.


Quote:
or faster than LL (also false),
If conjecture holds, it is faster, because there is no subtraction. Because there is no subtraction, further optimazions are possible. Programming my code and measure the time!


Quote:
or a rigorous test of primality (again, no), you are in dire need of a course (or reading-yourself) in elementary number theory.
If conjecture holds it is an rigorous test. Perhaps You need a course in quoting papers, all I can read from You are unprooven allegations.

greetings
boldi
boldi is offline   Reply With Quote
Old 2014-04-13, 21:28   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

9,791 Posts
Default

Quote:
Originally Posted by boldi View Post
You have forgotten to name the paper, where this topic is discused.
I have not - any elementary NT text discusses these kinds of tests, which date back to Fermat himself.

Quote:
If conjecture holds, it is faster, because there is no subtraction. Because there is no subtraction, further optimazions are possible. Programming my code and measure the time!
The -2 is an utterly trivially time component of an LL test. I *have* programmed both kinds of tests (the test you describe differs from what *is* a rigorous primality test for Fermat numbers only by having one extra modmul), at a very high level of code sophistication, and regularly compare timings. You go program your own code and get back to us when you have results and code others can inspect.

Quote:
If conjecture holds it is an rigorous test. Perhaps You need a course in quoting papers, all I can read from You are unprooven allegations.
It is you making unproven - in fact long-since-disproven - "allegations".

And your blustery "how dare you question my brilliant insight?" reply just raised your crank score even higher. I suggest you learn at least a little bit of the relevant math and algorithmics before spouting off further.

(But you probably won't take the latter advice, which is OK, as that will serve for amusement.)
ewmayer is offline   Reply With Quote
Old 2014-04-13, 21:44   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by boldi View Post
(First of all please excuse my bad English)

Conjecture: Let p be a odd prime number. Then the Mersenne number M = 2^p -1 holds the congruence relation

3^(M-1) ≡ 1 mod M
Okay this follows from Fermat's little theorem.

Quote:
The sequence will be calculated from n=1 to n=p-1, in our case from 1 to 6:

S_1 = 3∙3 mod 127=9
S_2 = 9∙9 mod 127=81
S_3 = 81∙81 mod 127=84
S_4 = 84∙84 mod 127=71
S_5 = 71∙71 mod 127=88
S_6 = 88∙88 mod 127=124

As result we have got 124. Now we are test, if 124 + S_0 = M_7. If yes, then M ist prime, if no, M is no prime. In our case we have 124 + 3 = 127 = M_7, so M_7 is prime.
so we are testing 3^{2^{p-1}} here ? if 3^{2^{p-1}} = -3 mod M then we can say 3^{2^{p-1}-1} = -1 mod M, and 3^{2^{p}-2} is 1 mod M, and 3^{2^{p}-1} = 3 mod M no ? can you explain this more. (I really can't say I'm correct as I'm trying to use Fermat's little theorem as well recently, yet didn't read the part talking about Lehmer's theorem in relation to the LL test., and of course as mentioned it's almost positive to have come up before.)

Last fiddled with by science_man_88 on 2014-04-13 at 21:44
science_man_88 is offline   Reply With Quote
Old 2014-04-13, 21:47   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

912310 Posts
Default

Must be the springtime! Not just one, but two eloquent cranks, at once!
Batalov is offline   Reply With Quote
Old 2014-04-13, 21:55   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by boldi View Post
You have forgotten to name the paper, where this topic is discused.
It has been discussed EXTENSIVELY in
so many places that it would be impossible to keep track.
It has been discussed numerous times in this forum.


Quote:
If conjecture holds, it is faster, because there is no subtraction.
HORSESHIT. Analyze the complexity.


Quote:
Because there is no subtraction, further optimazions are possible. Programming my code and measure the time!
A pointless exercise.



Quote:
If conjecture holds it is an rigorous test.
And there is no proof.

Quote:
Perhaps You need a course in quoting papers, all I can read from You are unprooven allegations.
You need a course in how to respect your elders and those possessing
superior education and knowledge. How many papers have YOU published
in this subject area?? Ernst is a acknowledged expert in this subject.
Go to any number theory conference and ask.

Now what have YOU done to earn respect?

You come across as an arrogant and ignorant ass.
R.D. Silverman 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
New Mersenne primality test Prime95 Miscellaneous Math 19 2014-08-23 04:18
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
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 06:45.

Thu Oct 22 06:45:59 UTC 2020 up 42 days, 3:56, 0 users, load averages: 1.21, 1.30, 1.33

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.