20140413, 20:31  #1 
Apr 2014
16_{8} 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^(M1) ≡ 1 mod M if, and only if M is prime. (In comparison to little Fermat theorem there is no Mersennepseudoprime 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^(M1) ≡ 1 mod M Example: p=7: 3^(1271)1 mod 127 = 1 > prime p=11: 3^(20471)1 mod 2047 = 1013 > not prime I have tested it and it is valid for all Mersenne numbers M = 2^p1 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 LucasLehmer 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^71 = 127. Now we want to proof, that M_7 is prim or not. So we are calculating recursive the sequence S_n = S_(n1) ∙ S_(n1) mod M with S_0=3 The sequence will be calculated from n=1 to n=p1, 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 LucasLehmer test, because we have no subtraction. (In LucasLehmertest we have to calculate the sequence S_n=S_(n1)∙S_(n1)  2 mod M) greetings boldi Last fiddled with by boldi on 20140413 at 21:21 
20140413, 20:52  #2 
∂^{2}ω=0
Sep 2002
República de California
3×5^{3}×31 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 readingyourself) in elementary number theory.

20140413, 20:56  #3  
Jan 2014
2×19 Posts 
Quote:
Last fiddled with by Qubit on 20140413 at 20:57 

20140413, 21:01  #4 
Apr 2014
5×17 Posts 

20140413, 21:02  #5 
Jan 2014
26_{16} Posts 
edit: Whoops, miscalculation.
Last fiddled with by Qubit on 20140413 at 21:12 
20140413, 21:09  #6  
Apr 2014
1110_{2} Posts 
Quote:
Conjecture: Let p be a odd prime number. Then the Mersenne number M = 2^p 1 holds the congruence relation 3^(M1) ≡ 1 mod M if, and only if M is prime. (In comparison to little Fermat theorem there is no Mersennepseudoprime who can hold the congruence relation.) Greetings boldi 

20140413, 21:17  #7  
Apr 2014
2·7 Posts 
You have forgotten to name the paper, where this topic is discused.
Quote:
Quote:
greetings boldi 

20140413, 21:28  #8  
∂^{2}ω=0
Sep 2002
República de California
3·5^{3}·31 Posts 
Quote:
Quote:
Quote:
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.) 

20140413, 21:44  #9  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:
Quote:
Last fiddled with by science_man_88 on 20140413 at 21:44 

20140413, 21:47  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3^{2}×7×149 Posts 
Must be the springtime! Not just one, but two eloquent cranks, at once!

20140413, 21:55  #11  
Nov 2003
2^{2}×5×373 Posts 
Quote:
so many places that it would be impossible to keep track. It has been discussed numerous times in this forum. Quote:
Quote:
Quote:
Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fastest software for Mersenne primality test?  JonathanM  Information & Answers  25  20200616 02:47 
New Mersenne primality test  Prime95  Miscellaneous Math  19  20140823 04:18 
LLT Cycles for Mersenne primality test: a draft  T.Rex  Math  1  20100103 11:34 
Mersenne Primality Test in Hardware  Unregistered  Information & Answers  4  20070709 00:32 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 