mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-03-14, 20:23   #1
jshort
 
"James Short"
Mar 2019
Canada

11 Posts
Default 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.)
jshort is offline   Reply With Quote
Old 2019-03-16, 13:23   #2
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

32·11 Posts
Default

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
ThiloHarich is offline   Reply With Quote
Old 2019-03-17, 23:45   #3
jshort
 
"James Short"
Mar 2019
Canada

11 Posts
Default

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.
jshort is offline   Reply With Quote
Old 2019-03-18, 17:34   #4
chris2be8
 
chris2be8's Avatar
 
Sep 2009

7·271 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2019-03-18, 18:41   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

165A16 Posts
Default

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?
henryzz is offline   Reply With Quote
Old 2019-03-18, 18:58   #6
wpolly
 
wpolly's Avatar
 
Sep 2002
Vienna, Austria

3×73 Posts
Default

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.
wpolly is offline   Reply With Quote
Old 2019-03-19, 16:37   #7
chris2be8
 
chris2be8's Avatar
 
Sep 2009

189710 Posts
Default

Quote:
Originally Posted by wpolly View Post
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
chris2be8 is offline   Reply With Quote
Old 2019-03-20, 06:53   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

210618 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2019-03-20, 22:52   #9
jshort
 
"James Short"
Mar 2019
Canada

11 Posts
Default

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.
jshort is offline   Reply With Quote
Old 2019-04-09, 16:34   #10
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default

Quote:
Originally Posted by jshort View Post
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
lukerichards is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 00:02.

Wed Sep 30 00:02:33 UTC 2020 up 19 days, 21:13, 0 users, load averages: 1.09, 1.34, 1.44

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.