20210209, 12:55  #1 
Feb 2021
Salt Lake City, UT
29 Posts 
Searching Mersenne Primes with Mathematica
I independently confirmed two Mersenne nonprimes below 1GHz x 1 min https://www.mersenne.ca/exponent/172279571 and https://www.mersenne.ca/exponent/172279589
with the following Mathematica code: Do[a = RandomInteger[100000]; b = PrimeQ[a*2*172279571 + 1]; If[b == True, Print[b, " ", a, " ", IntegerQ[(2^(172279571)  1)/(a*2*172279571 + 1)]]], {i, 1, 10000}]; 
20210209, 13:37  #2  
Sep 2002
Database er0rr
3,617 Posts 
Quote:
Code:
p=17227971;for(a=1,100000,if(Mod(2,2*a*p+1)^p==1,print([p,a]))) Last fiddled with by paulunderwood on 20210209 at 13:40 

20210209, 15:19  #3  
Feb 2021
Salt Lake City, UT
29 Posts 
Quote:
? p=172279571 %9 = 172279571 ? for(a=1,100000000,if(Mod(2,2*a*p+1)^p==1,print([p,a]))) [172279571, 25] [172279571, 1138120] I mean I did not know and did not check in the databases if they were primes and found them independently simply guessing them primes and then finding that those factors are small recovering the old result by random toss of a in a narrow belt: Last fiddled with by mattprim on 20210209 at 16:18 

20210209, 15:45  #4  
Sep 2002
Database er0rr
7041_{8} Posts 
Quote:
The heavy lifting is done with Mod(2,2*a*p+1)^p==1. There is no need for lots of memory to hold the full Mp number. I am not sure testing the primaiity of a potential factor is quicker. Perhaps you could translate my Pari/GP code into Mathematica code as an exercise and let us how fast it runs. Last fiddled with by paulunderwood on 20210209 at 15:51 

20210209, 16:07  #5  
Feb 2021
Salt Lake City, UT
29 Posts 
Quote:
Last fiddled with by mattprim on 20210209 at 16:16 

20210209, 16:16  #6 
Sep 2002
Database er0rr
3617_{10} Posts 
In order: TF (trial factoring), P1 factoring and finally a lengthy PRP (probable prime) test is done (and an LL (Lucas Lehmer) test if successful).

20210210, 17:06  #7 
Feb 2021
Salt Lake City, UT
29 Posts 
Giant 2^585011209011 is divisible by 13384*2*58501120901+1 = 1565958004277969 (about 1Ghz x hour to test it knowing it from PariGP on the same Ghz)
PrimeQ[58501120901] True IntegerQ[(2^(58501120901)  1)/(13384*2*58501120901 + 1)] True Giant 2^137305394691 is divisible by 19*2*13730539469+1 = 521760499823 (1 Ghz x min Mathematica): Do[c = False; a = RandomInteger[100]; b = PrimeQ[a*2*13730539469 + 1]; If[b == True, c = IntegerQ[(2^(13730539469)  1)/(a*2*13730539469 + 1)]]; If[b == True, Print[" ", a, " ", c]], {i, 1, 100}] 34 False 30 False 79 False 45 False 79 False 12 False 12 False 34 False 19 True 30 False 30 False 
20210210, 17:53  #8  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
5×1,877 Posts 
Quote:
You are trying to fix a wristwatch with a bread knife. Read the suggested literature first, then rethink your breadknife strategy. 

20210211, 06:57  #9  
Romulan Interpreter
Jun 2011
Thailand
2×4,679 Posts 
Quote:
Even mfakt[co], they won't test if the potential factors are prime, they just make a list of factors, sieve them for a while (which is much faster than xPRP testing) and then do exponentiation (divisibility test) for the surviving candidates. This way, few percents of the surviving candidates are not prime, but it becomes faster to just do the exponentiation for them, than continue sieving (percent of composite factors depending on how large the sieving prime was). I think there was once a composite factor found this way, but I don't remember the exponent. Last fiddled with by LaurV on 20210211 at 07:07 

20210211, 07:06  #10 
Sep 2002
Database er0rr
7041_{8} Posts 
ta!

20210211, 11:12  #11 
Feb 2021
Salt Lake City, UT
29 Posts 
Mathematica has the native prime Number Theory routines: PrimeQ, NextPrime, PrimePi etc. Just was mainly curious how PrimeQ[2^n1] giving the answer if 2^n1 is prime. You can actually link stuff like PariGP to Mathematica using Mathlink so you can include own faster routines for Mersenne.
Last fiddled with by mattprim on 20210211 at 11:16 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Searching for m. primes is like playing lottery  joblack  Lounge  20  20090105 15:18 
to be faster at searching mersenne primes  flosculus  Information & Answers  6  20081110 18:59 
searching for Mersenne primes  davieddy  Math  7  20070821 04:51 
A Proposal for searching Recurrence Series Primes  Erasmus  Factoring  3  20040514 09:26 
Need help with math problem re: searching for all primes.  daxm  Miscellaneous Math  5  20030720 19:32 