20190618, 13:30  #474 
Einyen
Dec 2003
Denmark
3·23·43 Posts 
Yes, you do 2^{1723} mod q and 2^{2447} mod q and see if you get 1.

20190618, 14:24  #475 
May 2019
113 Posts 
Another possible method of factoring by q
Factors of 2^p1 for p prime are in the form q=2*k*p+1 for some nonnegative integer k.
Initialisation/Initialization Step 1. For each prime p on the interval [pmin, pmax], we find the smallest q>=qmin such that 2p divides q1, and push the corresponding tuple (q, p) into a priority queue. Main logic Step 2: Retrieve and pop the smallest (q, p) tuple out of the priority queue. To optimise, we check if a small prime (say at most m) divides q by computing q mod m# and precomputing a list of possible remainders mod m#. Check if q divides 2^p1. If it does, output the corresponding (q, p). Insert (q+2p, p) inside the priority queue. This avoids the trial factoring step. As Gerbicz pointed out, pmin should be at least 10^6 since exponents with factoring done have been deeply trial factored and/or ECMed. If I have made a mistake, please correct me. Last fiddled with by 2M215856352p1 on 20190618 at 14:25 
20190618, 14:46  #476 
Romulan Interpreter
Jun 2011
Thailand
2^{2}·3·739 Posts 
Where is the difference to "by p", except that your method is much MUCH slower?
This is what GIMPS does, except that each p has "its own queue" and "there is no physical queue". The issue is that your method tests (almost) all k's and most of them no need to be tested at all (ex: k=2 mod 4 should never be tested, also k=p mod 4 should not be tested, etc). Last fiddled with by LaurV on 20190618 at 14:49 
20190618, 15:03  #477  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
2×3×13×59 Posts 
Quote:
ATH's descriptions should be understood as simplified overviews. There's quite a lot to the byp method used in mfaktc, mfakto, and elsewhere. See https://www.mersenneforum.org/showpo...23&postcount=6 Last fiddled with by kriesel on 20190618 at 15:17 

20190618, 15:14  #478  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
5,807 Posts 
Quote:
Last fiddled with by retina on 20190618 at 15:14 

20190618, 15:58  #479  
May 2019
161_{8} Posts 
Quote:


20190622, 13:04  #480  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
2·3·13·59 Posts 
Quote:
Last fiddled with by kriesel on 20190622 at 13:07 

20190622, 14:06  #481  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
2·3·13·59 Posts 
Quote:


20190622, 14:45  #482  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
5,807 Posts 
Quote:
Quote:
Last fiddled with by retina on 20190622 at 14:47 

20190821, 13:44  #483 
Aug 2002
Buenos Aires, Argentina
31·43 Posts 
Today TJAOI finished finding prime factors less than 2^{66}.
The last one is the prime factor 73786932973062531511 of M193866301 (65.99999915 bits) 
20190823, 23:32  #484 
Serpentine Vermin Jar
Jul 2014
29·113 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Old User  Unregistered  Information & Answers  1  20121018 23:31 
The user CP has gone :(  retina  Forum Feedback  5  20061205 16:47 
Changing My User ID  endless mike  NFSNET Discussion  1  20041031 19:38 
OSX yet? new user here  KevinLee  Hardware  6  20031212 17:06 
help for a Mac user  drakkar67  Software  3  20030211 10:55 