20110519, 21:09  #12 
"Forget I exist"
Jul 2009
Dartmouth NS
8418_{10} Posts 

20110519, 22:14  #13 
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 

20110519, 22:20  #14 
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
the exponent (x1) is 1 mod k the base is n+2 mod k , could we not use this to solve for n that work with this ? maybe the same modular arithmetic we used.
Last fiddled with by science_man_88 on 20110519 at 22:28 
20110520, 01:40  #15  
Aug 2006
5987_{10} Posts 
Quote:
http://rosettacode.org/wiki/Extreme_...lues#PARI.2FGP: On a 64bit machine, Pari t_REAL numbers have a maximum value of where ε is the machine epsilon at the selected precision. So if x is about 4^n then PARI can handle n up to about 2e18. Last fiddled with by CRGreathouse on 20110520 at 01:40 

20110520, 11:31  #16 
Einyen
Dec 2003
Denmark
2·17·101 Posts 
This conjecture is also true for exponents
19937,21701,23209,44497,86243,110503,132049,216091 corrensponding to Mersenne primes number 24 to 31. But I haven't tested all numbers up to 216091, only up to 18,000. To summarize the conjecture: M_{p}=2^{p}1 is prime if: (M_{p}p+2)^{x1} == 1 (mod M_{p}) where x = M_{p}^{2}*(p1)  M_{p}*(p2). Is this conjecture interesting or just a rewriting of the LL test or is it false? I hope someone smarter than me read this :) To me it seems significant if it's proven true, since it's a "simple" modular exponentiation compared to LL test algorithm where you square and substract 2 each iteration. How about the runtime of this test? x is of the order M_{p}^{2}, so it needs around M_{p} squarings same as the LL test? 
20110520, 11:49  #17 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
11×389 Posts 
I wrote straightforward implementations of both this and the LL test in C using GMP, and compared them to each other. The new test takes about 2.1 times as long as the LL. (the program is attached, if anyone wants to look at how I did it, make improvements, etc.) But I couldn't tell you if it were optimized, which would really be faster. If it really only needs about the same squarings as the LL test, as ATH suggested, it might be even faster than the LL because you don't need to subtract 2 on each iteration, you must have to do modular exponentiation.
Testing M11213 took 4.84 seconds using the LL, and 10.25 seconds using this new method. Testing M21701 took 25.76 seconds using LL, and 56.01 seconds using this new method. As for its accuracy, it certainly seems to be correct from the tests you've done. At worst, I'd say it's a way to PRP test a Mersenne. But a proof of it being true, whether as a 'rewording' of the LL or not, would be great! Last fiddled with by TimSorbet on 20110520 at 12:00 
20110520, 12:27  #18  
"Bob Silverman"
Nov 2003
North of Boston
1D54_{16} Posts 
Quote:
simple, based on elementary number theory and elementary algebra? (1) The exponent is ~ (M_p)^2 for doing essentially a PRP test. This is TWICE the work for an LL test. (the number of squarings is double that for LL) (2) Hasn't anyone observed that this obscure value for x gives that x1 is a multiple of (M_p 1)? (!!!!!!!!!!) Put M_p = 2^p  1, and expand the expression for x1. Now simplify. Hasn't anyone observed that by Fermat's little theorem a^z = 1 mod M_p whenever z is a multiple of (M_p  1)??? (and (a, M_p) == 1)?????? This so called 'new' conjecture simply amounts to saying that a = (M_p  p + 2) is not a false witness for M_p. Of course a^(x1) = 1 mod M_p whenever M_p is prime and (a, M_p) = 1. This is just Fermat's little theorem. But it does so by creating this artificial exponent (x1) that is TWICE AS LONG AS NECESSARY to do a PRP test! This is all elementary. 

20110520, 12:48  #19  
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
Quote:


20110520, 13:13  #20  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
term somewhere in doing the expansion. I can make transcription errors as easily as anyone else. However, just as a test, put p = 5, M_p = 31. M_p  1 = 30. Then x = 31^2 (5  1)  31 (5  2) = 3751. This is definitely not 0 mod 30. It is the case, however, that x1 = 3750 is a multiple of 30 (which is M_p  1) as I stated before. Further, if your claim is true, then something is [b] really[\b] weird/wrong. If x = 0 mod (M_p  1) then [working mod M_p] we have x = k (M_p  1) for some k, whence a^(x1) = a^( k(M_p 1)  1) = a^(k (M_p1)) * a^1 = 1 * a^1 = 1/a mod M_p. a = M_p  p + 2 and 1/a definitely isn't 1. Recheck your calculations. 

20110520, 13:20  #21  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:
Code:
(09:40)>Mp^2*(p1)  Mp*(p2) %215 = (Mp^2  Mp)*p + (Mp^2 + 2*Mp) (09:40)>%%(Mp1) %216 = 0 (10:12)>Mp^2*(p1)  Mp*(p2) %227 = (Mp^2  Mp)*p + (Mp^2 + 2*Mp) (10:12)>%%(Mp) %228 = 0 Last fiddled with by science_man_88 on 20110520 at 13:23 

20110520, 14:05  #22  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,877 Posts 
Quote:
checked my arithmetic. I keep getting that x1 is divisible by (M_p1), not that x is divisible by (M_p  1). Might we have a third party weigh in here? 

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 