20190314, 20:23  #1 
"James Short"
Mar 2019
Canada
11 Posts 
Factoring composite Mersenne numbers using Pollard Rho
First post here  sorry if this is either an obvious or mundane question.
The Pollard Rho factoring method is suppose to have a running time proportional to , however if you're trying to factor a composite Mersenne number and you are using the same iterating function as the one used in the LucasLehmer primality test (that is over mod of with ), is it known to factor considerably faster ? I've tested it on the first three composite Mersenne integers and and the above iterating function becomes periodic after and iterations (the first two return to the starting . ………...…………………......…. (Note  Carl Pomerance suggests using an iterating function of where and the constant can be arbitrarily chosen. I can see the logic here as well since , however this is a different strategy all together it appears.) 
20190316, 13:23  #2 
Nov 2005
63_{16} Posts 
Hello, welcome to the forum.
The pollard rho can be tweaked to work nicely for Fermat numbers. The Funktion to generate the numbers has to be modified here. With this modification it was possible to give one factor of F_8 = 2^(2^8) + 1 by choosing f(x) = x^(2^(8+2)) + 1 see : https://mathspeople.anu.edu.au/~brent/pd/rpb061.pdf I did not read the article but the same approach might also work for Mersenne numbers. Brent has found factors of M227, M199 with it. http://centaur.reading.ac.uk/4571/1/...ne_Numbers.pdf 
20190317, 23:45  #3 
"James Short"
Mar 2019
Canada
11 Posts 
Thanks for the reference ThilaHarich….
Yeah the factorization of was the most successful application of the Pollard Rho method to date for sure. Interestingly Brent mentions that there could've been further speedups, however decided to keep things simple in his paper. As you mentioned, he applied the iteration function and the reason he did this is because for any Fermat number , any prime divisor must satisfy . Thus the above iterating function can only generate integers over a set that contains elements. This drastically decreases the average numbers of iterations that will need to be performed before the sequence starts to repeat itself. I won't go into the specific details. They are based on probabilistic assumptions or heuristic arguments, however many textbooks like to use the Birthday Problem as an explanatory analogy: https://en.wikipedia.org/wiki/Birthday_problem Re  further speedups to the above Brent was likely aware of this, however the iteration function he used could've been given another boost! He used the function which would've required a total of 11 multiplications (the extra +1 bit I believe is due to a reduction modulo F_8). However had Brent used the iterating function instead, he would've only added one extra squaring operation cost, however because , the above function would've still been iterating over a set of at most integers and there is a 50% chance that it would've been iterating over integers if so happened that . In the case of this happens to be true. In general, if we let for some relatively small integer , if we are already aware that for some relatively large integer m, it actually makes sense to use the iterating function . This can be applied to Mersenne integers as well, since any prime factor must satisfy . You could call it a combined factorization algorithm. Anyway, this doesn't have anything to do with the idea of using strategy to factor Mersenne integers, but its still interesting. I'll try to say something about factoring M227 and M199 using these methods in another post. 
20190318, 17:34  #4 
Sep 2009
19×97 Posts 
Would it be possible to combine Rho factoring with a LL test? If residues in a LL test start to repeat would that mean you have found a factor? How likely would it be to find a factor that hasn't been found by TF or P1?
This assumes the overhead for the extra calculations would be paid for by the chance of finding a factor. Chris 
20190318, 18:41  #5 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
7·811 Posts 
Experiments would have to be done but I suspect that it might always need more iterations for rho to find a factor than to test primality via LL. Plus you would have to store all the full iterations which would be nontrivial for the huge numbers we test nowadays. It would be great if someone could prove me wrong though. I suspect it possible to prove me right though. Who will accept this challenge?

20190318, 18:58  #6 
Sep 2002
Vienna, Austria
333_{8} Posts 
I believe that using x>x^22 in the rho method causes the cycle to be length O(p) instead of O(sqrt(p)).
For instance, for the prime factor 228479 of M71, x>x^21 finds a cycle in 658 iterations, while x>x^22 requires 7035 iterations. 
20190319, 16:37  #7  
Sep 2009
19×97 Posts 
Quote:
My plan was to run rho for a suitable number of cycles, then switch to a normal LL test if we havn't found a factor. If it's worth doing any rho cycles though. Chris 

20190320, 06:53  #8 
Romulan Interpreter
Jun 2011
Thailand
3·2,861 Posts 
That is not feasible, you need to store ALL residues, and check at every iteration, because you don't know the period after which they repeat. If you know the period, then you know an order of some nonsquare, so you can find a factor. Of course, you may store only a part of each residue, or some CRC/hash of it, to be easy to check, but in that case, when you have a match you have to repeat the test and keep full residues to see if it is really a match.
Also, residues repeat after some order of the factors, and because factors are 2kp+1, it may be that this order is larger than p. For example, order of 3 in 2^111 is 88. If you know this, you get immediately the factor (89), but as you only make p1 iterations (here 10), you will never find the fact that residues repeat. If you start a PRP test with base 3, the residues will start repeating after 88 iterations, and for LL test, they may repeat after 60. Edit: @jshort: can you factor M727, or at least M523 with that "combined" method? If so, I would be interested in it... :) Last fiddled with by LaurV on 20190320 at 07:46 
20190320, 22:52  #9  
"James Short"
Mar 2019
Canada
11 Posts 
Quote:
You generally only need to store one residue. It's a "reference" point that we assume is already inside the periodic cycle for which we compare future residues with. If our assumption is wrong, then we abandon this residue and pick one further down in the sequence. Another method which requires no storing and very easy to program is to simply define two sequences where one is simply a double iteration of the other. Here is a pari/gp example of this method: rho(n) = { my(x=4, y=14); while (gcd(yx,n) == 1, x = (x^2 2) % n; y = (y^2  2) % n; y = (y^2  2) % n; ); gcd(yx,n); } For arbitrary integers n, x^2  2, should be avoided because it doesn't form a Monte Carlo random walk over . For arbitrary n, you might want to use this algorithm rho(n) = { my(x=2, y=5); while (gcd(yx,n) == 1, x = (x^2 + 1) % n; y = (y^2 + 1) % n; y = (y^2  2) % n; ); gcd(yx,n); } Quote:
Do you mind posting your code or describing the algorithm you used? Quote:


20190409, 16:34  #10  
"Luke Richards"
Jan 2018
Birmingham, UK
283_{10} Posts 
Quote:
https://en.wikipedia.org/wiki/Pollar...ithm#Algorithm https://en.wikipedia.org/wiki/Cycle_...toise_and_Hare 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring Mersenne numbers  paulunderwood  Miscellaneous Math  18  20170827 14:56 
2 holes in bizarre theorem about composite Mersenne Numbers  wildrabbitt  Math  120  20160929 21:52 
lag in factoring Mersenne numbers (P < 10000)?  ixfd64  Factoring  1  20060102 08:25 
Factoring highly composite Mersenne numbers  philmoore  Factoring  21  20041118 20:00 