mersenneforum.org A (new) old, (faster) slower mersenne-(primality) PRP test
 Register FAQ Search Today's Posts Mark Forums Read

 2014-04-13, 20:31 #1 boldi   Apr 2014 11102 Posts 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
 2014-04-13, 20:52 #2 ewmayer ∂2ω=0     Sep 2002 República de California 2DD816 Posts 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.
2014-04-13, 20:56   #3
Qubit

Jan 2014

2·19 Posts

Quote:
 Originally Posted by boldi 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

2014-04-13, 21:01   #4
tapion64

Apr 2014

5516 Posts

Quote:
 Originally Posted by Qubit 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.

 2014-04-13, 21:02 #5 Qubit     Jan 2014 2·19 Posts edit: Whoops, miscalculation. Last fiddled with by Qubit on 2014-04-13 at 21:12
2014-04-13, 21:09   #6
boldi

Apr 2014

2·7 Posts

Quote:
 Originally Posted by Qubit 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

2014-04-13, 21:17   #7
boldi

Apr 2014

2×7 Posts

Quote:
 Originally Posted by ewmayer 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

2014-04-13, 21:28   #8
ewmayer
2ω=0

Sep 2002
República de California

23×32×163 Posts

Quote:
 Originally Posted by boldi 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.)

2014-04-13, 21:44   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by boldi (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

 2014-04-13, 21:47 #10 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 27×7×11 Posts Must be the springtime! Not just one, but two eloquent cranks, at once!
2014-04-13, 21:55   #11
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

746010 Posts

Quote:
 Originally Posted by boldi 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post JonathanM Information & Answers 25 2020-06-16 02:47 Prime95 Miscellaneous Math 19 2014-08-23 04:18 T.Rex Math 1 2010-01-03 11:34 Unregistered Information & Answers 4 2007-07-09 00:32 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 12:59.

Fri Jul 1 12:59:45 UTC 2022 up 78 days, 11:01, 2 users, load averages: 1.63, 1.73, 1.74