Can Pollard Rho cycles be used to find a factor?

[danaj]

Not going to wade too deep in this, but I recommend:

Montgomery, "Speeding the Pollard and elliptic curve methods of factorization", 1987

Silverman already pointed this one out, and I agree it's a gem that is full of information. I find more in it every time I look at it.

Brent, "Primality Testing and Integer Factorisation", 1990 (published 1991)

Two books I like are "Prime Numbers and Computer Methods for Factorization" by Hans Riesel (1994), available at reasonable prices used; and "Prime Numbers: A Computational Perspective" by Crandall and Pomerance (2nd edition, mine is copyright 2010). The latter is available in electronic form here. I like having a paper copy, but given the free electronic price there isn't any reason not to peruse it.

How useful Pollard's rho is depends on your application. It's always useful to know, and for CS geeks it's a fun thing to program, especially as it is quite short. I've found it to be quite useful in some cases when trying to factor tiny numbers quickly (SQUFOF and p-1 are better in the long run -- your mileage may vary). Hence I think it's a useful tool to have around if that's something you'll be doing.

[xilman]

Originally Posted by R.D. Silverman

BTW, I am not the only one who who has these kinds of ideas.
Bruce Schneier has repeatedly stated similar ideas (on cryptography).

His summary: "So you want to be a cryptographer? Get a PhD".

I say "So you think you can improve existing algorithms? Get a PhD. (or
equivalent study)"

FWIW, I do not have a PhD.

I have a DPhil in an entirely unrelated subject (physical chemistry, specifically molecular spectroscopy). That hasn't stopped me from doing useful (but admittedly not earth-shattering) work in other fields including cryptography and, more generally, information security.

I've a lot of respect for Bruce and have learned much from him over the years. On one occasion, just before he was about to start, he asked why I was in his audience --- apparently under the impression that I already knew everything he was about to say. Needless to say, he was mistaken.

[henryzz]

It just occurred to me that if the polynomial in pollard rho is x^2-2 then for 1.5x + gcds cost we could run pollard rho plus a lucas lehmer test at the same time. How much time would the gcds take in this circumstance for large exponents?

[LaurV]

Those orders are much higher, you won't find a factor in the first p-1 iterations. As someone said before, Pollard rho is a very inefficient algorithm. Try it for M67, M101, and see.

[only_human]

Originally Posted by henryzz

It just occurred to me that if the polynomial in pollard rho is x^2-2 then for 1.5x + gcds cost we could run pollard rho plus a lucas lehmer test at the same time. How much time would the gcds take in this circumstance for large exponents?

Mathworld says:

Iterating the formula
x_n+1 = (x_n)² + a (mod n),
or almost any polynomial formula (an exception being x_n^2-2) for any initial value x_0 will produce a sequence of number that eventually fall into a cycle.

This comes up in discussions occasionally. I have seen it said that -2 is an unusually poor choice for a. I don't know the reason and LL tests do exist that subtract other constant values per iteration.

[R.D. Silverman]

Originally Posted by only_human

Mathworld says:
This comes up in discussions occasionally. I have seen it said that -2 is an unusually poor choice for a. I don't know the reason and LL tests do exist that subtract other constant values per iteration.

The reason requires knowing something about properties of finite fields.
I will offer a hint: Consider the orbit of a generator of the twisted sub-group
of GF(P^2).

Second hint: Look at the roots of x^2-2 in GF(P^2) (where P is the prime
being sought)

Third hint: consider looking for a closed form solution to the recursion:

x_{n+1} = x_n^2 - 2

[henryzz]

Originally Posted by LaurV

Those orders are much higher, you won't find a factor in the first p-1 iterations. As someone said before, Pollard rho is a very inefficient algorithm. Try it for M67, M101, and see.

(p-1)/2 iterations as rho iterates twice per iteration.
It wouldn't surprise me if the number of iterations would only be enough in very few situations.

Originally Posted by only_human

Mathworld says:
This comes up in discussions occasionally. I have seen it said that -2 is an unusually poor choice for a. I don't know the reason and LL tests do exist that subtract other constant values per iteration.

x^2-2 is unusual
It wouldn't surprise me if other choices of a that work for LL tests are also quite bad.


We also have to remember that factors of 2^p-1 are of the form 2kp+1 which would be relatively large factors for rho to find.

[only_human]

As for considering the GCD cost in Pollard Rho, there is this optimization (Wikipedia):

A further improvement was made by Pollard and Brent. They observed that if gcd (a,n) >1, then also gcd (ab,n)>1 for any positive integer b. In particular, instead of computing gcd (|x-y|,n) at every step, it suffices to define z as the product of 100 consecutive |x-y| terms modulo n, and then compute a single gcd (z,n). A major speed up results as 100 gcd steps are replaced with 99 multiplications modulo n and a single gcd. Occasionally it may cause the algorithm to fail by introducing a repeated factor, for instance when n is a square. But it then suffices to go back to the previous gcd term, where gcd(z,n)=1, and use the regular Rho algorithm from there.

[R.D. Silverman]

Originally Posted by henryzz

(p-1)/2 iterations as rho iterates twice per iteration.
It wouldn't surprise me if the number of iterations would only be enough in very few situations.

x^2-2 is unusual
It wouldn't surprise me if other choices of a that work for LL tests are also quite bad.
.

Why not take the time to study the mathematics of finite fields? You
might learn how to respond to your 'surprise'. Try studying WHY the
LL test works.

[CRGreathouse]

Originally Posted by R.D. Silverman

The reason requires knowing something about properties of finite fields.
I will offer a hint: Consider the orbit of a generator of the twisted sub-group
of GF(P^2).

I'm interested in learning more about this, although I have never studied group theory. (I did take a general algebra class, plus a graduate class in field theory, so I'm not entirely clueless.)

You mention a generator, so you must mean a twisted subgroup of the multiplicative group GF(p^2)* since the additive group has no generator (as all elements have order 1 or p). {1} and GF(p^2)* are trivial twisted subgroups of GF(p^2)*, you must not mean those.

I looked at GF(9) as an example, and unless I am mistaken there are two nontrivial twisted subgroups: {1, 2} and {1, 2, a, b} where a and b are the square roots of 2. (I'm not sure of the usual terminology here.) Only the former has a generator, since a does not generate b and b does not generate a.

But in any case, the orbit of a generator is surely the whole twisted subgroup, no? Else it would not be a generator. So I'm confused as to what you mean.

Edit: Of course by 1 I mean the multiplicative identity and by 2 I mean 1+1 = -1.

[R.D. Silverman]

Originally Posted by CRGreathouse

I'm interested in learning more about this, although I have never studied group theory. (I did take a general algebra class, plus a graduate class in field theory, so I'm not entirely clueless.)

You mention a generator, so you must mean a twisted subgroup of the multiplicative group GF(p^2)* since the additive group has no generator (as all elements have order 1 or p). {1} and GF(p^2)* are trivial twisted subgroups of GF(p^2)*, you must not mean those.

I looked at GF(9) as an example, and unless I am mistaken there are two nontrivial twisted subgroups: {1, 2} and {1, 2, a, b} where a and b are the square roots of 2. (I'm not sure of the usual terminology here.) Only the former has a generator, since a does not generate b and b does not generate a.

But in any case, the orbit of a generator is surely the whole twisted subgroup, no? Else it would not be a generator. So I'm confused as to what you mean.

Edit: Of course by 1 I mean the multiplicative identity and by 2 I mean 1+1 = -1.

A generator x, of the twisted sub-group is a solution to x^2-2 = 0 in
GF(p^2)

The fact that there is a generator which is a solution to x^2 - 2 = 0
(and there is a closed form solution )
combined with the fact that the recurrence x_{n+1} = x_n^2 -2 is
just squaring an element in the twisted sub-group shows that there
is a closed form solution to the recurrence. Which makes it bad
as a pseudo RNG (and hence bad for Pollard Rho)