mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-02-09, 12:55   #1
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

29 Posts
Minus 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}];
mattprim is offline   Reply With Quote
Old 2021-02-09, 13:37   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

367410 Posts
Default

Quote:
Originally Posted by mattprim View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-02-09, 15:19   #3
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

29 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
mattprim is offline   Reply With Quote
Old 2021-02-09, 15:45   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·11·167 Posts
Default

Quote:
Originally Posted by mattprim View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-02-09, 16:07   #5
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

29 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
mattprim is offline   Reply With Quote
Old 2021-02-09, 16:16   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·11·167 Posts
Default

Quote:
Originally Posted by mattprim View Post
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).
paulunderwood is offline   Reply With Quote
Old 2021-02-10, 17:06   #7
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

29 Posts
Default

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
mattprim is offline   Reply With Quote
Old 2021-02-10, 17:53   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,431 Posts
Default

Quote:
Originally Posted by mattprim View Post
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.
Batalov is offline   Reply With Quote
Old 2021-02-11, 06:57   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

3·47·67 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
LaurV is offline   Reply With Quote
Old 2021-02-11, 07:06   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110010110102 Posts
Default

ta!
paulunderwood is offline   Reply With Quote
Old 2021-02-11, 11:12   #11
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

29 Posts
Default

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
mattprim is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Searching for m. primes is like playing lottery joblack Lounge 20 2009-01-05 15:18
to be faster at searching mersenne primes flosculus Information & Answers 6 2008-11-10 18:59
searching for Mersenne primes davieddy Math 7 2007-08-21 04:51
A Proposal for searching Recurrence Series Primes Erasmus Factoring 3 2004-05-14 09:26
Need help with math problem re: searching for all primes. daxm Miscellaneous Math 5 2003-07-20 19:32

All times are UTC. The time now is 12:56.

Fri May 14 12:56:58 UTC 2021 up 36 days, 7:37, 0 users, load averages: 1.23, 1.70, 1.65

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.