 mersenneforum.org Searching Mersenne Primes with Mathematica
 Register FAQ Search Today's Posts Mark Forums Read  2021-02-19, 10:36   #56
mattprim

Feb 2021
Salt Lake City, UT

111012 Posts Quote:
 Originally Posted by paulunderwood You are still calculaing Mp for composite p. Read Wiki on Mersenne primes. p needs to be prime. Put an if statement at the beginning of the loop to check p is prime. This is bad: s = 4; Do[s = Mod[(s*s - 2), Mp] .... This is good: s = Mod[4, Mp]; Do[s = s^2-2 .... When you have your MMA code running on a 1572864 core computer we will believe your absurd claims. What the hell do you think Mp = 2^Prime[p] - 1 does?
Here p is prime because it is Prime[p] i.e. p->Prime[p]. Mathematica function Prime[p] returns the p-th prime number i.e. Prime=2, Prime=3, Prime=5 etc. I am not running it on 1572864 core computer. It is the EFF https://www.eff.org/ which posted the 150 000 \$ prize to find the 100 000 digits Mersenne prime and IBM constructed this computer so they can find it by themselves even with general problems Mathematica and they expect you to run something else. I only say that it is possible to find those fast there and only using this code. My 1GHz to confirm the biggest known takes some 1 year of the constant run. The multicore IBM is also strategic computer capable to calculate optimal orders for simulated war (like chess playing code but simulating the military operations in real time) so it has most likely the classified access i.e. for the people with security clearance Q from the governmental labs like the Los Alamos. Did not check that yet who can get CPU time account there.

Last fiddled with by mattprim on 2021-02-19 at 11:24   2021-02-19, 10:50 #57 mattprim   Feb 2021 Salt Lake City, UT 29 Posts Here is the PariGP code which is running more less the same fast (one night on 1.5 GHz) to check the same what which my Mathematica compiled code: LL(p)={ my(m=Mod(4,1< 2021-02-19, 11:20 #58 paulunderwood   Sep 2002 Database er0rr 3,863 Posts Okay grasshopper, now implement modular reduction over Mp either in Pari/GP or MMA. Then do some shallow trial division by 2*k*p+1. I expect this to speed up your codes by 20 fold.   2021-02-19, 11:33 #59 mattprim   Feb 2021 Salt Lake City, UT 1D16 Posts Sorry, I am only mathematician with PhD trying to do some research how to get 150 thousand dollars prize for 100 million digits prime. I actually believe there is some Fermat Last (Great) Theorem like theorem which Mersennes are primes stating like "The Mersenne number is the prime if and only if ... " i.e. its prime exponent fulfills some conditions which then I would call a superprime or prime prime. The theorem than would allow to simply construct the next larger Mersenne prime. For example: the Mersenne prime is the prime if and only its exponent Modulo division by all the lower primes is the prime. Or: The Mersenne prime is the prime if and only if its position in primes number factorization does not contain 13 etc. i.e. the result of the LL test can be predicted from it. Last fiddled with by mattprim on 2021-02-19 at 12:13   2021-02-19, 14:26 #60 mattprim   Feb 2021 Salt Lake City, UT 111012 Posts The prove of LL test not getting out of the integer number space is comparatively easy for n=3 but it does not want go that way easy for larger: let s = x^2 Then let s_1 = x^2*x^2 - x = x^4 - x = x*(x^3-1) = x (x-1)(1+x+x^2) but from the geometric series 1+x+x^2 = (1-x^3)/(1-x) so s1 is devisable by (1-x^3)/(1-x) which for x=2 is exactly the Mersenne prime 2^3-1=7 But if you generate this polynomials in general higher not much can be done and seen that way. Simply gets worse than the normal Great Fermat theorem that some polynomial in x of 2p-2 order for x integer is integer-proportional to x^n-1 only for n a certain prime and x=2. Last fiddled with by mattprim on 2021-02-19 at 14:36   2021-02-19, 15:50   #61
CRGreathouse

Aug 2006

3·1,993 Posts Quote:
 Originally Posted by mattprim Sorry, I am only mathematician with PhD trying to do some research how to get 150 thousand dollars prize for 100 million digits prime.
...but you don't know the 165-year-old Lucas-Lehmer test. For comparison, this is what cars looked like 165 years ago, and this was the current state of the art research toward the internal combustion engine. Please, update your knowledge -- if you want to make a breakthrough, you can't start from 19th-century tech.   2021-02-19, 16:18 #62 retina Undefined   "The unspeakable one" Jun 2006 My evil lair 11000100010102 Posts This whole thread is pointless. Mathematica is not the tool to use. Is it for general purpose, and not optimised for Mersenne primes. The OP is wasting time trying to use it.   2021-02-19, 16:54   #63
Dr Sardonicus

Feb 2017
Nowhere

5·997 Posts Quote:
 Originally Posted by mattprim I actually believe there is some Fermat Last (Great) Theorem like theorem which Mersennes are primes stating like "The Mersenne number is the prime if and only if ... " i.e. its prime exponent fulfills some conditions which then I would call a superprime or prime prime.
AFAIK the greatest mathematical importance of Fermat's Last Theorem is that no proof was known, and efforts to find a proof greatly advanced the subject of Algebraic Number Theory

Fermat's "little theorem" is much more pertinent, leading to a simple explanation of the fact that if p is prime and q divides 2p - 1, then p divides q-1.

If you think there's a way to test whether the prime p is such that 2p - 1 is prime, which is significantly cheaper computationally than the methods currently known and used, I doubt you would be able to discover it by testing exponents in the known range.

Mersenne himself thought he had a way of determining which exponents p gave prime values of 2p - 1. He didn't.

Last fiddled with by Dr Sardonicus on 2021-02-19 at 16:55   2021-02-19, 16:57   #64
CRGreathouse

Aug 2006

10111010110112 Posts Quote:
 Originally Posted by Dr Sardonicus Mersenne himself thought he had a way of determining which exponents p gave prime values of 2p - 1. He didn't.
See A109461 and Mersenne Primes: Early history.   2021-02-19, 21:22   #65
mattprim

Feb 2021
Salt Lake City, UT

2910 Posts Quote:
 Originally Posted by CRGreathouse ...but you don't know the 165-year-old Lucas-Lehmer test. For comparison, this is what cars looked like 165 years ago, and this was the current state of the art research toward the internal combustion engine. Please, update your knowledge -- if you want to make a breakthrough, you can't start from 19th-century tech.
I am just proving it to you for one 3-2=1 iteration: 2^3-1=7 is the Mersenne prime and it is dividing s_1:

The prove of LL test not getting out of the integer number space is comparatively easy for n=3 but it does not want go that way
easy for larger:

let s_0 = x^2

Then let

s_1 = x^2*x^2 - x = x^4 - x = x*(x^3-1) = x (x-1)(1+x+x^2)

but from the geometric series 1+x+x^2 = (1-x^3)/(1-x)

so s1 is devisable by (1-x^3)/(1-x) which for x=2 is exactly the Mersenne prime 2^3-1=7

But if you generate this polynomials in general higher not much can be done and seen that way. Simply gets worse than the normal Great Fermat theorem that some polynomial in x of 2p-2 order for x integer is integer-proportional to x^n-1 only for n a certain prime and x=2.

Last fiddled with by mattprim on 2021-02-19 at 21:39   2021-02-19, 21:26 #66 Uncwilly 6809 > 6502   """"""""""""""""""" Aug 2003 101×103 Posts 10,007 Posts Have you thought about programing LL up in Excel instead?   Thread Tools Show Printable Version Email this Page 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 09:37.

Thu Oct 21 09:37:27 UTC 2021 up 90 days, 4:06, 1 user, load averages: 0.82, 0.87, 0.97