Factoring composite Mersenne numbers using Pollard Rho

jshort · 2019-03-14, 20:23

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 $n^{\frac{1}{4}}$ , however if you're trying to factor a composite Mersenne number $M_{p}$ and you are using the same iterating function as the one used in the Lucas-Lehmer primality test (that is $x_{n+1} = x_{n}^{2} - 2$ over mod of $M_{p}$ with $x_0 = 4$
), is it known to factor $M_{p}$ considerably faster ?

I've tested it on the first three composite Mersenne integers $2^{11} - 1, 2^{23} - 1$ and $2^{29} - 1$ and the above iterating function becomes periodic after $5,11$ and $13$ iterations (the first two return to the starting $x_0 = 4$ .

………...…………………......….

(Note - Carl Pomerance suggests using an iterating function of $x_{n+1} = x_{n}^{2p} + a$ where $x_0$ and the constant $a$ can be arbitrarily chosen. I can see the logic here as well since $M_{p} \equiv 1 mod M_{p}$ , however this is a different strategy all together it appears.)

ThiloHarich · 2019-03-16, 13:23

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://maths-people.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

jshort · 2019-03-17, 23:45

Thanks for the reference ThilaHarich….

Yeah the factorization of $F_{8}$ was the most successful application of the Pollard Rho method to date for sure. Interestingly Brent mentions that there could've been further speed-ups, however decided to keep things simple in his paper.

As you mentioned, he applied the iteration function $x_{n+1} = x_{n}^{2^{10}} + 1$ and the reason he did this is because for any Fermat number $F_{k}$ , any prime divisor $p_{k} \mid F_{k}$ must satisfy $p_{k} \equiv 1 mod 2^{k+2}$ . Thus the above iterating function can only generate integers $x_{n}$ over a set that contains $\frac{p_{k} - 1}{2^{k+2}}$ elements. This drastically decreases the average numbers of iterations that will need to be performed before the sequence ${x_{i}$ 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 speed-ups 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 $x_{n+1} = x_{n}^{2^{10}} + 1$ 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 $x_{n+1} = x_{n}^{2^{11}} + 1$ instead, he would've only added one extra squaring operation cost, however because $2^{10} \mid 2^{11}$ , the above function would've still been iterating over a set of at most $\frac{p_{k} -1}{2^{10}}$ integers and there is a 50% chance that it would've been iterating over $\frac{p_{k}-1}{2^{11}}$ integers if so happened that $p_{k} \equiv 1 mod 2^{11}$ . In the case of $F_{8}$ this happens to be true.

In general, if we let $s = lcm(1,2,3...k)$ for some relatively small integer $k$ , if we are already aware that $p_{k} \equiv 1 mod m$ for some relatively large integer m, it actually makes sense to use the iterating function $x_{n+1} = x_{n}^{sm}+ 1$ .

This can be applied to Mersenne integers as well, since any prime factor $q \mid 2^{p} - 1$ must satisfy $q \equiv 1 mod (2p)$ . You could call it a combined $P - 1 / Pollard Rho$ factorization algorithm.

Anyway, this doesn't have anything to do with the idea of using $n_{n+1} = x_{n}^{2} - 2, x_0 = 4$ 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.

chris2be8 · 2019-03-18, 17:34

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 P-1?

This assumes the overhead for the extra calculations would be paid for by the chance of finding a factor.

Chris

henryzz · 2019-03-18, 18:41

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?

wpolly · 2019-03-18, 18:58

I believe that using x-->x^2-2 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^2-1 finds a cycle in 658 iterations, while x-->x^2-2 requires 7035 iterations.

chris2be8 · 2019-03-19, 16:37

Quote:

Originally Posted by wpolly

I believe that using x-->x^2-2 in the rho method causes the cycle to be length O(p) instead of O(sqrt(p)).

That may be why Knuth says x^2-2 should be avoided.

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

LaurV · 2019-03-20, 06:53

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 non-square, 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^11-1 is 88. If you know this, you get immediately the factor (89), but as you only make p-1 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... :)

jshort · 2019-03-20, 22:52

Quote:

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 non-square, 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.

Re - storing residues

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(y-x,n) == 1,

x = (x^2 -2) % n;

y = (y^2 - 2) % n; y = (y^2 - 2) % n;
);

gcd(y-x,n);
}

For arbitrary integers n, x^2 - 2, should be avoided because it doesn't form a Monte Carlo random walk over $\Z_p$ . For arbitrary n, you might want to use this algorithm

rho(n) = { my(x=2, y=5);

while (gcd(y-x,n) == 1,

x = (x^2 + 1) % n;

y = (y^2 + 1) % n; y = (y^2 - 2) % n;
);

gcd(y-x,n);
}

Quote:

I believe that using x-->x^2-2 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^2-1 finds a cycle in 658 iterations, while x-->x^2-2 requires 7035 iterations.

Thanks for sharing. 228,479 is a factor of $2^{71} - 1$ and 7035 iterations is enormous.

Do you mind posting your code or describing the algorithm you used?

Quote:

Edit: @jshort: can you factor M727, or at least M523 with that "combined" method? If so, I would be interested in it... :)

Unless the least prime factors were relatively smooth, the "combined" method would fail miserably for numbers that size. Fyi --- the idea doesn't turn Pollard rho or P-1 into something fundamentally much better/faster. It also can't be generalized to Elliptic Curves in any clear way.

lukerichards · 2019-04-09, 16:34

Quote:

Originally Posted by jshort

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.

This is the approach which is applied in efficient implementation's of Pollard's Rho:

https://en.wikipedia.org/wiki/Pollar...ithm#Algorithm

https://en.wikipedia.org/wiki/Cycle_...toise_and_Hare

2019-03-14, 20:23	#1
jshort "James Short" Mar 2019 Canada 2·3² 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 $n^{\frac{1}{4}}$ , however if you're trying to factor a composite Mersenne number $M_{p}$ and you are using the same iterating function as the one used in the Lucas-Lehmer primality test (that is $x_{n+1} = x_{n}^{2} - 2$ over mod of $M_{p}$ with $x_0 = 4$ ), is it known to factor $M_{p}$ considerably faster ? I've tested it on the first three composite Mersenne integers $2^{11} - 1, 2^{23} - 1$ and $2^{29} - 1$ and the above iterating function becomes periodic after $5,11$ and $13$ iterations (the first two return to the starting $x_0 = 4$ . ………...…………………......…. (Note - Carl Pomerance suggests using an iterating function of $x_{n+1} = x_{n}^{2p} + a$ where $x_0$ and the constant $a$ can be arbitrarily chosen. I can see the logic here as well since $M_{p} \equiv 1 mod M_{p}$ , however this is a different strategy all together it appears.)

2019-03-20, 06:53	#8
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 41×251 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 non-square, 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^11-1 is 88. If you know this, you get immediately the factor (89), but as you only make p-1 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 2019-03-20 at 07:46

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factoring Mersenne numbers	paulunderwood	Miscellaneous Math	18	2017-08-27 14:56
2 holes in bizarre theorem about composite Mersenne Numbers	wildrabbitt	Math	120	2016-09-29 21:52
lag in factoring Mersenne numbers (P < 10000)?	ixfd64	Factoring	1	2006-01-02 08:25
Factoring highly composite Mersenne numbers	philmoore	Factoring	21	2004-11-18 20:00

2019-03-16, 13:23	#2
ThiloHarich Nov 2005 2²×3³ 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://maths-people.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

2019-03-17, 23:45	#3
jshort "James Short" Mar 2019 Canada 18₁₀ Posts	Thanks for the reference ThilaHarich…. Yeah the factorization of $F_{8}$ was the most successful application of the Pollard Rho method to date for sure. Interestingly Brent mentions that there could've been further speed-ups, however decided to keep things simple in his paper. As you mentioned, he applied the iteration function $x_{n+1} = x_{n}^{2^{10}} + 1$ and the reason he did this is because for any Fermat number $F_{k}$ , any prime divisor $p_{k} \mid F_{k}$ must satisfy $p_{k} \equiv 1 mod 2^{k+2}$ . Thus the above iterating function can only generate integers $x_{n}$ over a set that contains $\frac{p_{k} - 1}{2^{k+2}}$ elements. This drastically decreases the average numbers of iterations that will need to be performed before the sequence ${x_{i}$ 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 speed-ups 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 $x_{n+1} = x_{n}^{2^{10}} + 1$ 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 $x_{n+1} = x_{n}^{2^{11}} + 1$ instead, he would've only added one extra squaring operation cost, however because $2^{10} \mid 2^{11}$ , the above function would've still been iterating over a set of at most $\frac{p_{k} -1}{2^{10}}$ integers and there is a 50% chance that it would've been iterating over $\frac{p_{k}-1}{2^{11}}$ integers if so happened that $p_{k} \equiv 1 mod 2^{11}$ . In the case of $F_{8}$ this happens to be true. In general, if we let $s = lcm(1,2,3...k)$ for some relatively small integer $k$ , if we are already aware that $p_{k} \equiv 1 mod m$ for some relatively large integer m, it actually makes sense to use the iterating function $x_{n+1} = x_{n}^{sm}+ 1$ . This can be applied to Mersenne integers as well, since any prime factor $q \mid 2^{p} - 1$ must satisfy $q \equiv 1 mod (2p)$ . You could call it a combined $P - 1 / Pollard Rho$ factorization algorithm. Anyway, this doesn't have anything to do with the idea of using $n_{n+1} = x_{n}^{2} - 2, x_0 = 4$ 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.

2019-03-18, 17:34	#4
chris2be8 Sep 2009 9A0₁₆ 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 P-1? This assumes the overhead for the extra calculations would be paid for by the chance of finding a factor. Chris

2019-03-18, 18:41	#5
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 3·23·89 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?

2019-03-18, 18:58	#6
wpolly Sep 2002 Vienna, Austria 3·73 Posts	I believe that using x-->x^2-2 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^2-1 finds a cycle in 658 iterations, while x-->x^2-2 requires 7035 iterations.