mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-01-27, 02:19   #1
Jinyuan Wang
 
Jan 2020

12 Posts
Default 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
Jinyuan Wang is offline   Reply With Quote
Old 2020-01-27, 03:14   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

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
CRGreathouse is offline   Reply With Quote
Old 2020-01-27, 15:14   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Jinyuan Wang View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2020-01-27, 18:12   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

52×127 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New PC dedicated to Mersenne Prime Search Taiy Hardware 12 2018-01-02 15:54
Can I specify the range to search the Mersenne Prime? Unregistered Information & Answers 22 2012-03-20 11:38
Sum of prime divisors for Mersenne Numbers? kurtulmehtap Math 3 2011-01-19 18:48
Search for Mersenne primes by checking for perfect numbers dsouza123 Miscellaneous Math 33 2003-09-02 16:18

All times are UTC. The time now is 03:57.


Fri Oct 22 03:57:22 UTC 2021 up 90 days, 22:26, 1 user, load averages: 0.94, 1.18, 1.41

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.