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 29 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

2·1,811 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

111012 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

1110001001102 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

2×1,811 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

939110 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

Jun 2011
Thailand

222438 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 2×1,811 Posts ta!
 2021-02-11, 11:12 #11 mattprim     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^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 22:07.

Mon Apr 19 22:07:00 UTC 2021 up 11 days, 16:47, 0 users, load averages: 3.56, 3.29, 3.76