 mersenneforum.org A way to search prime divisors of Mersenne numbers
 Register FAQ Search Today's Posts Mark Forums Read 2020-01-27, 02:19 #1 Jinyuan Wang   Jan 2020 116 Posts A way to search prime divisors of Mersenne numbers I'm a fan of searching for Mersenne primes. In the website, I found that for every Mersenne number, we need to run "Factor=~, 68, 69" on p95 software to search whether it has a prime divisor. I have a way to find out all prime factors between 2^68 and 2^69 of Mersenne numbers in just one run: To know if there is a p, so that q is a prime divisor of 2^p-1, we just need to search for such p in the prime factors of q-1 (Because if q is a prime divisor of a Mersenne number 2^p-1, then q=2*k*p+1). In this way, for every q, one calculation is enough. And it's not necessary to compute whether q is a prime factor of 2^p-1 for every p. I came up with this method after referring to the sequence A122094 in OEIS (http://oeis.org/A122094): For example, to find all prime divisors less than 1000, you can try the code (run on https://pari.math.u-bordeaux.fr/gp.html): forprime(q=1,1000,v=factor(q-1)[,1];for(r=1,#v,p=v[r];if(Mod(2,q)^p==1,print1("["q", "p"], ")))) Program output as [q, p], which means q is a prime divisor of 2^p-1. I wonder if my method is feasible ? Last fiddled with by Uncwilly on 2020-01-27 at 02:31 Reason: Fixed URL issues   2020-01-27, 03:14 #2 CRGreathouse   Aug 2006 3·1,993 Posts The difficulty is that factoring is much, much harder than dividing, and these numbers grow very quickly. This could become interesting if quantum computers get much better error rates (and a few more qubits): https://crypto.stackexchange.com/a/44490/2028   2020-01-27, 15:14   #3
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by Jinyuan Wang I'm a fan of searching for Mersenne primes. In the website, I found that for every Mersenne number, we need to run "Factor=~, 68, 69" on p95 software to search whether it has a prime divisor. I have a way to find out all prime factors between 2^68 and 2^69 of Mersenne numbers in just one run: To know if there is a p, so that q is a prime divisor of 2^p-1, we just need to search for such p in the prime factors of q-1 (Because if q is a prime divisor of a Mersenne number 2^p-1, then q=2*k*p+1). In this way, for every q, one calculation is enough. And it's not necessary to compute whether q is a prime factor of 2^p-1 for every p. I came up with this method after referring to the sequence A122094 in OEIS (http://oeis.org/A122094): For example, to find all prime divisors less than 1000, you can try the code (run on https://pari.math.u-bordeaux.fr/gp.html): forprime(q=1,1000,v=factor(q-1)[,1];for(r=1,#v,p=v[r];if(Mod(2,q)^p==1,print1("["q", "p"], ")))) Program output as [q, p], which means q is a prime divisor of 2^p-1. I wonder if my method is feasible ?
(1) Claiming it as "your method" is arrogant and unwarranted. It is merely a disguised
form of trial division in which one first fixes the divisor and then searches over different
exponents rather than first fixing an exponent and then searching over divisors. The
amount of computation is the same in both cases; just done in a different order.

(2) Your claim of "one run" is gibberish. It is meaningless. The same can be said of the
"standard" order for doing trial division. Both cases are a double loop over the same
bounds.

(3) May I suggest that you study existing methods by (say) reading Crandall and
Pomerance before making future pronouncements?   2020-01-27, 18:12 #4 ATH Einyen   Dec 2003 Denmark CB516 Posts There is already a user who have been running this method for several years, he reached 9.17*1019 ~ 266.3 by now. https://mersenne.org/M700199783 Here is an explanation of the 3 different ways you can trial factor Mersenne numbers: https://mersenneforum.org/showpost.p...&postcount=471  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Taiy Hardware 12 2018-01-02 15:54 Unregistered Information & Answers 22 2012-03-20 11:38 kurtulmehtap Math 3 2011-01-19 18:48 dsouza123 Miscellaneous Math 33 2003-09-02 16:18

All times are UTC. The time now is 15:34.

Sat Jan 22 15:34:13 UTC 2022 up 183 days, 10:03, 0 users, load averages: 1.65, 1.46, 1.29