20200127, 02:19  #1 
Jan 2020
1_{16} 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^p1, we just need to search for such p in the prime factors of q1 (Because if q is a prime divisor of a Mersenne number 2^p1, 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^p1 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.ubordeaux.fr/gp.html): forprime(q=1,1000,v=factor(q1)[,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^p1. I wonder if my method is feasible ? Last fiddled with by Uncwilly on 20200127 at 02:31 Reason: Fixed URL issues 
20200127, 03:14  #2 
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 
20200127, 15:14  #3  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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? 

20200127, 18:12  #4 
Einyen
Dec 2003
Denmark
CB5_{16} Posts 
There is already a user who have been running this method for several years, he reached 9.17*10^{19} ~ 2^{66.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  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New PC dedicated to Mersenne Prime Search  Taiy  Hardware  12  20180102 15:54 
Can I specify the range to search the Mersenne Prime?  Unregistered  Information & Answers  22  20120320 11:38 
Sum of prime divisors for Mersenne Numbers?  kurtulmehtap  Math  3  20110119 18:48 
Search for Mersenne primes by checking for perfect numbers  dsouza123  Miscellaneous Math  33  20030902 16:18 