mersenneforum.org Searching Mersenne Primes with Mathematica
 Register FAQ Search Today's Posts Mark Forums Read

 2021-02-09, 12:55 #1 mattprim     Feb 2021 Salt Lake City, UT 111012 Posts Searching Mersenne Primes with Mathematica 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}];
2021-02-09, 13:37   #2
paulunderwood

Sep 2002
Database er0rr

3×1,327 Posts

Quote:
 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}];
Code:
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.

Last fiddled with by paulunderwood on 2021-02-09 at 13:40

2021-02-09, 15:19   #3
mattprim

Feb 2021
Salt Lake City, UT

358 Posts

Quote:
 Originally Posted by paulunderwood Code: 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:

Last fiddled with by mattprim on 2021-02-09 at 16:18

2021-02-09, 15:45   #4
paulunderwood

Sep 2002
Database er0rr

3×1,327 Posts

Quote:
 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.

Last fiddled with by paulunderwood on 2021-02-09 at 15:51

2021-02-09, 16:07   #5
mattprim

Feb 2021
Salt Lake City, UT

29 Posts

Quote:
 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.

Last fiddled with by mattprim on 2021-02-09 at 16:16

2021-02-09, 16:16   #6
paulunderwood

Sep 2002
Database er0rr

3·1,327 Posts

Quote:
 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).

 2021-02-10, 17:06 #7 mattprim     Feb 2021 Salt Lake City, UT 29 Posts 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
2021-02-10, 17:53   #8
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

25DB16 Posts

Quote:
 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.

2021-02-11, 06:57   #9
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

71·139 Posts

Quote:
 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.

Last fiddled with by LaurV on 2021-02-11 at 07:07

 2021-02-11, 07:06 #10 paulunderwood     Sep 2002 Database er0rr 1111100011012 Posts ta!
 2021-02-11, 11:12 #11 mattprim     Feb 2021 Salt Lake City, UT 1D16 Posts 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. Last fiddled with by mattprim on 2021-02-11 at 11:16

 Similar Threads Thread Thread Starter Forum Replies Last Post joblack Lounge 20 2009-01-05 15:18 flosculus Information & Answers 6 2008-11-10 18:59 davieddy Math 7 2007-08-21 04:51 Erasmus Factoring 3 2004-05-14 09:26 daxm Miscellaneous Math 5 2003-07-20 19:32

All times are UTC. The time now is 11:33.

Sun Jan 23 11:33:43 UTC 2022 up 184 days, 6:02, 0 users, load averages: 1.51, 1.32, 1.20