mersenneforum.org User TJAOI
 Register FAQ Search Today's Posts Mark Forums Read

 2019-06-18, 13:30 #474 ATH Einyen     Dec 2003 Denmark 3·23·43 Posts Yes, you do 21723 mod q and 22447 mod q and see if you get 1.
 2019-06-18, 14:24 #475 2M215856352p1   May 2019 113 Posts Another possible method of factoring by q Factors of 2^p-1 for p prime are in the form q=2*k*p+1 for some non-negative 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 q-1, 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^p-1. 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 2019-06-18 at 14:25
 2019-06-18, 14:46 #476 LaurV Romulan Interpreter     Jun 2011 Thailand 22·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 2019-06-18 at 14:49
2019-06-18, 15:03   #477
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×3×13×59 Posts

Quote:
 Originally Posted by DukeBG Um, you don't need to divide that. You just calculate the ModPow (with all the speed improvements). Unless that is what you implied?
Right, for novices reading here, it's good you point that out. Long division is not the method of trial of a factor candidate. Raising 2 to the p power, mod the candidate factor along the way, is. It's far faster since it keeps the operands limited to dozens of bits in size, rather than thousands or millions or hundreds of millions. If 2p mod f is 1, 2p-1 mod f is zero and f is shown to be a factor of 2p-1.
ATH's descriptions should be understood as simplified overviews. There's quite a lot to the by-p method used in mfaktc, mfakto, and elsewhere. See https://www.mersenneforum.org/showpo...23&postcount=6

Last fiddled with by kriesel on 2019-06-18 at 15:17

2019-06-18, 15:14   #478
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

5,807 Posts

Quote:
 Originally Posted by kriesel Raising 2 to the p power, mod the candidate factor along the way, is. It's far faster since it keeps the operands limited to dozens of bits in size, rather than thousands or millions or hundreds of millions. If 2p mod f is 1, 2p-1 mod f is zero and f is shown to be a factor of 2p-1.
Long division would always shift in a new '1' bit at each step, so we don't need to store the entire number. The reason is not the size of the operands, but because there is a simple method that allows us to do powers in many fewer steps than it would take if we did naive division.

Last fiddled with by retina on 2019-06-18 at 15:14

2019-06-18, 15:58   #479
2M215856352p1

May 2019

1618 Posts

Quote:
 Originally Posted by LaurV 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).
My method consumes more memory and the factors will be found in increasing order.

2019-06-22, 13:04   #480
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·3·13·59 Posts

Quote:
 Originally Posted by retina Long division would always shift in a new '1' bit at each step, so we don't need to store the entire number. The reason is not the size of the operands, but because there is a simple method that allows us to do powers in many fewer steps than it would take if we did naive division.
Fully naive long division would be equivalent to how it is taught in school for general base 10 numbers, with the entire dividend present in memory versus on paper (storage) at the outset. Good point that it's perhaps wasted space for a mersenne number in binary; we know it's all ones so generating additional rightward bits on the fly as needed is simple. Sometimes space is traded for speed, including in naive algorithms. It might be that adding them a word width at a time in long division is less inefficient.

Last fiddled with by kriesel on 2019-06-22 at 13:07

2019-06-22, 14:06   #481
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·3·13·59 Posts

Quote:
 Originally Posted by retina Long division would always shift in a new '1' bit at each step, so we don't need to store the entire number. The reason is not the size of the operands, but because there is a simple method that allows us to do powers in many fewer steps than it would take if we did naive division.
Thanks, updated #12 of https://www.mersenneforum.org/showpo...23&postcount=6

2019-06-22, 14:45   #482
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

5,807 Posts

Quote:
 Originally Posted by kriesel Fully naive long division would be equivalent to how it is taught in school for general base 10 numbers, with the entire dividend present in memory versus on paper (storage) at the outset. Good point that it's perhaps wasted space for a mersenne number in binary; we know it's all ones so generating additional rightward bits on the fly as needed is simple. Sometimes space is traded for speed, including in naive algorithms. It might be that adding them a word width at a time in long division is less inefficient.
Quote:
 Originally Posted by kriesel Thanks, updated #12 of https://www.mersenneforum.org/showpo...23&postcount=6
We also don't care about the quotient so even if we did long division we can simply throw away the quotient and the final step reveals the remainder. So memory usage is of no concern here. Even if you did steps of 32-bits, or 64-bits, or whatever, this only gives a linear speed-up.

Last fiddled with by retina on 2019-06-22 at 14:47

 2019-08-21, 13:44 #483 alpertron     Aug 2002 Buenos Aires, Argentina 31·43 Posts Today TJAOI finished finding prime factors less than 266. The last one is the prime factor 73786932973062531511 of M193866301 (65.99999915 bits)
2019-08-23, 23:32   #484
Serpentine Vermin Jar

Jul 2014

29·113 Posts

Quote:
 Originally Posted by alpertron Today TJAOI finished finding prime factors less than 266. The last one is the prime factor 73786932973062531511 of M193866301 (65.99999915 bits)
I don't know who that user is, but if I ever meet him/her, I'll buy 'em a drink of their choice.

 Similar Threads Thread Thread Starter Forum Replies Last Post Unregistered Information & Answers 1 2012-10-18 23:31 retina Forum Feedback 5 2006-12-05 16:47 endless mike NFSNET Discussion 1 2004-10-31 19:38 KevinLee Hardware 6 2003-12-12 17:06 drakkar67 Software 3 2003-02-11 10:55

All times are UTC. The time now is 20:51.

Sat Oct 24 20:51:58 UTC 2020 up 44 days, 18:02, 0 users, load averages: 1.87, 1.84, 1.76