20110520, 14:11  #23 
"Forget I exist"
Jul 2009
Dartmouth NS
10000011100010_{2} Posts 
yeah I'm confused but mostly because I don't see the math of the (Mp1) part I see how x is easily 0 mod Mp ( both terms use Mp).

20110520, 14:28  #24 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
Code:
(11:16)>(Mp^2 + 2*Mp)%(Mp^2Mp) %232 = Mp 
20110520, 15:47  #25  
"Forget I exist"
Jul 2009
Dartmouth NS
10000011100010_{2} Posts 
Quote:
Code:
(12:44)>Mp^2*(p1)  Mp*(p2) %1 = (p  1)*Mp^2 + (p + 2)*Mp (12:44)>%%(Mp1) %2 = 1 (12:45)>Mp^2*(p1)  Mp*(p2) %3 = (p  1)*Mp^2 + (p + 2)*Mp (12:45)>%%(Mp) %4 = 0 (12:45)> 

20110520, 16:11  #26 
"Forget I exist"
Jul 2009
Dartmouth NS
10000011100010_{2} Posts 
and now the simplification I got the last time is lining up to the same, almost like I didn't have simplify on.

20110520, 16:19  #27  
Einyen
Dec 2003
Denmark
6552_{8} Posts 
Quote:
x1 = M_{p}^{2}*(p1)  M_{p}*(p2)  1 = M_{p}^{2}*p  M_{p}^{2}  M_{p}*p + 2*M_{p}  1 = (M_{p}1) * (M_{p}*pM_{p}+1) I don't know why I couldn't see this before, of course it's Fermat's PRP test :( Last fiddled with by ATH on 20110520 at 16:20 

20110520, 16:40  #28 
"Bob Silverman"
Nov 2003
North of Boston
1110101010010_{2} Posts 
But it's a BAD way to do it. The exponent is twice as long as necessary!

20110520, 17:45  #29 
Einyen
Dec 2003
Denmark
2·17·101 Posts 
See the OP. This was meant to be a new primality test for mersenne numbers, not a PRP test, written in an obscure way. I cleaned up the expressions some but missed the last step that showed it was just a Fermat PRP test.
Probably because I was hoping this was a new and interesting primality test and disregarding the logic of how improbable it all was, also because numerically it seemed to work. Last fiddled with by ATH on 20110520 at 17:49 
20110520, 17:55  #30  
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
Quote:


20110520, 19:35  #31  
"Bob Silverman"
Nov 2003
North of Boston
7506_{10} Posts 
Quote:
Modular exponentiation is certainly not any easier than LL. Any purported new tests must perform fewer than p multiplications to test M_p, otherwise it is just reinventing a square wheel. 

20110520, 19:48  #32 
"Forget I exist"
Jul 2009
Dartmouth NS
20E2_{16} Posts 
so (p2) squaring + (p2) subtraction + (p2) remainder = p multiplication ?

20110520, 22:41  #33 
Aug 2006
5,987 Posts 
The squarings and modulus you speak of are parts of a single modular squaring (which may not have distinct "squaring" and "reducing" steps). The subtractions are cheap compared to the squarings. Technically, squaring is different from (easier than) multiplication, but at a minimum a test designed to supplant LL can't do more than p fulllength multiplications, because those alone would take longer than the LL.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED!  dabaichi  News  571  20201026 11:02 
Another way to PRP test Mersenne numbers  paulunderwood  Miscellaneous Math  18  20170126 20:33 
How do I test if it is a mersenne prime on GIMPS?  spkarra  Math  21  20150123 18:13 
another mersenne prime test  jocelynl  Math  8  20061020 19:36 
The 40th known Mersenne prime, 2209960111 is not PRIME!  illmanq  Miscellaneous Math  33  20040919 05:02 