Can Pollard Rho cycles be used to find a factor?

[R.D. Silverman]

Originally Posted by R.D. Silverman

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)

Let me expand upon this.

There is a solution to x^2-2 = 0 (in the field) of the form
a + 1/a for some element a. When you apply the recurrence
x <- x^2 - 2 in the Pollard Rho algorithm, one gets

(a+1/a)(a + 1/a) - 2 = a^2 + 2*a * 1/a + 1/a^2 - 2.

The middle term "drops out". (a+1/a)^2 = a^2 + 1/a^2

This is what makes it bad as a pseudo RNG. As one repeats the
recurrence, all of the middle terms drop out. This limits the range
of the recurrence.

[only_human]

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.

I just looked in a few of the usual places and could not find anything supporting my statement in bold. Sorry for the thread bump but I do not want anyone wasting time on this unsubstantiated assertion of mine.

[only_human]

Here are the other Lucas Lehmer Tests for Mersenne numbers that subtract other constant values per iteration.: http://www.mersennewiki.org/index.ph...Initial_Values

[henryzz]

Originally Posted by only_human

Here are the other Lucas Lehmer Tests for Mersenne numbers that subtract other constant values per iteration.: http://www.mersennewiki.org/index.ph...Initial_Values

Interesting. The objection still stands that not enough cycles will be done to find a factor.

[LaurV]

Assuming some TF was done, there will never be more optimal to use rho for mersenne numbers. That is because rho is finding the order of some base b, and this order is always a multiple of q-1, where q is a factor of m=Mp=2^p-1, with few "lucky" exceptions (one exception is when we stepped on a square root of 1, for example, its order is 2).

Try this in pari/gp:

gp > v=vector(2046);
gp > for(i=1,2046,if(gcd(2047,i)==1,v[i]=znorder(Mod(i,2047))))
gp > v=vecsort(v);
gp > cnt=1; for(i=2,#v,if(v[i]==v[i-1],cnt++,print("elements with order "v[i-1]": \t"cnt); cnt=1)); print("elememts with order "v[#v]": \t"cnt)
elements with order  0:  110
elements with order  1:    1
elements with order  2:    3
elements with order  4:    4
elements with order  8:    8
elements with order 11:  120
elements with order 22:  360
elements with order 44:  480
elememts with order 88:  960

The "zeros" are the factors, with their multiples, we don't know them. If we luckily step on a factor, then job is done.
The "twos" are square roots of 1, some of them are quadratic residues too, therefore we have "fours" and "eights". If we step on them, we are lucky, job is done.
The "elevens" (this is our p) are powers of 2, and their negatives, because 2^p=1 (mod m) always. Those are not useful for our rho.
The rest (22, 44, 88) are the orders of some random bases which are not factors or multiple of factors.

Now you take 2^67-1, and tell me how lucky you have to be to "step on a factor" when you randomly pick the base.

Because, if you are not, you will always need to do at least a DOUBLE number of rho iterations to get the order of that base (and therefore the factor).

Well, this example is not very good, because you can start with c=b^(2*p) as a base, for a random b, and you reduce the order by 2p, but still, that is why I said in the beginning "if some TF was done", i.e. for a k in q=2*k*p+1 and k>p, (which is trivial to TF!!!) and a factor was not found, then you will still have to do MORE than p iterations of rho, to find any factor. And this is valid for ALL exponents. Either you find a factor by doing a little bit of TF, or if not, then you must do MORE than p iterations of rho to find the factor.

(edit: by doing a little bit of TF you eliminate the possibility that the order you are looking for is very small; afterthat what is left is either "a lot of rho", or "a lot of luck" to step on a convenient base).

This discussion is futile, as a known person here would say...