Searching Mersenne Primes with Mathematica

[mattprim]

I independently confirmed two Mersenne non-primes 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}];

[paulunderwood]

Originally Posted by mattprim

I independently confirmed two Mersenne non-primes 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}];

p=17227971;for(a=1,100000,if(Mod(2,2*a*p+1)^p==1,print([p,a])))

Pari/GP runs this in 1/7 of a second and gives a=25 for a factor.

[mattprim]

Originally Posted by paulunderwood

p=172279571;for(a=1,100000,if(Mod(2,2*a*p+1)^p==1,print([p,a])))

Pari/GP runs this in 1/7 of a second and gives a=25 for a factor.

Sure, https://www.mersenne.ca/exponent/172279571 and my Pari/GP run:

? 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:

[paulunderwood]

Originally Posted by mattprim

Sure, 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.

Taking a 10000 samples in a 100000 space is silly!? You may as well iterate over the whole space.

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.

[mattprim]

Originally Posted by paulunderwood

Taking a 10000 samples in a 100000 space is silly!? You may as well iterate over the whole space.

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.

This was one of my fist runs on my own guessed numbers to check if the line of code works. The test was showing me the estimated time on Prime95 https://www.mersenne.org/download/ clustering software as above 1 year for both.

[paulunderwood]

Originally Posted by mattprim

This was one of my fist runs on my own guessed numbers to check if the line of code works. The test was showing me the estimated time on Prim95 clustering software as above 1 year.

In order: TF (trial factoring), P-1 factoring and finally a lengthy PRP (probable prime) test is done (and an LL (Lucas Lehmer) test if successful).

[mattprim]

Giant 2^58501120901-1 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^13730539469-1 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

[Batalov]

Originally Posted by mattprim

Giant 2^58501120901-1 is divisible by 13384*2*58501120901+1 = 1565958004277969 (about 1Ghz x hour to test it knowing it from PariGP on the same Ghz)

This is immensely slow. (like others already told you)
You are trying to fix a wristwatch with a bread knife.
Read the suggested literature first, then rethink your bread-knife strategy.

[LaurV]

Originally Posted by paulunderwood

I am not sure testing the primaiity [sic] of a potential factor is quicker.

Your feeling is right, it is not quicker. It is in fact way WAY slower. When you get to reasonable large factors, even a much faster 2-PRP test is slower than doing directly the modular exponentiation. That is because if you want to test if q=2kp+1 is (2-probable-)prime, you need to compute 2^(q-1)==1 (mod q), i.e. 2^(2kp)==1 (mod q) which is much slower than testing the divisibility, for which you do 2^p==1 (mod q). As the candidate gets larger, this gets slower/heavier, i.e. for larger k, needs additional iterations.

Even mfakt[c|o], 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 x-PRP 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.

[paulunderwood]

ta!

[mattprim]

Mathematica has the native prime Number Theory routines: PrimeQ, NextPrime, PrimePi etc. Just was mainly curious how PrimeQ[2^n-1] giving the answer if 2^n-1 is prime. You can actually link stuff like PariGP to Mathematica using Mathlink so you can include own faster routines for Mersenne.