Can Pollard Rho cycles be used to find a factor?

[wwf]

Pollard's rho algorithm uses a generator function to generate a sequence of numbers x_i.
We check for factors by calculating GCD(abs(x_i-x_2i),N).
If the GCD = 1, we continue to the next i.
If the GCD > 1, we have found a factor.
If the GCD = N, we have found a cycle and
then the algorithm terminates with failure, since this means x = y and therefore, by Floyd's cycle-finding algorithm, the sequence has cycled and continuing any further would only be repeating previous work.

I think the typical Pollard Rho implementations can find a factor when GCD=N or when we have found a cycle.
This is because of our choice of a generator function.
Let x_k be the first number in the cycle of length r.
Thus x_k==x_k+r.
If k!=1 (is this usually the case?), then we also have:
x_k-1 != x_k+r-1.

Now our typical generator is x_i+1=x²_i+c MOD N.
This means we have:
x²_k-1+c==x_k==x_k+r==x²_k+r-1+c MOD N.
or
x²_k-1+c==x²_k+r-1+c MOD N
x²_k-1 == x²_k+r-1 MOD N
This is a congruence of squares, and we already have x_k-1!=x_k+r-1
So
(x_k-x_k+r-1)(x_k+x_k+r-1) = 0 mod N
Both GCD(x_k-x_k+r-1,N) and GCD(x_k+x_k+r-1,N) are non-trivial factors of N.
We have factored N.

I have not seen this mentioned in my limited search on the Pollard Rho algorithm.
Is this a new finding?

Walter

[R.D. Silverman]

Originally Posted by wwf

Pollard's rho algorithm uses a generator function to generate a sequence of numbers x_i.
We check for factors by calculating GCD(abs(x_i-x_2i),N).
If the GCD = 1, we continue to the next i.
If the GCD > 1, we have found a factor.
If the GCD = N, we have found a cycle and
then the algorithm terminates with failure, since this means x = y and therefore, by Floyd's cycle-finding algorithm, the sequence has cycled and continuing any further would only be repeating previous work.

I think the typical Pollard Rho implementations can find a factor when GCD=N or when we have found a cycle.
This is because of our choice of a generator function.
Let x_k be the first number in the cycle of length r.
Thus x_k==x_k+r.
If k!=1 (is this usually the case?), then we also have:
x_k-1 != x_k+r-1.

Now our typical generator is x_i+1=x²_i+c MOD N.
This means we have:
x²_k-1+c==x_k==x_k+r==x²_k+r-1+c MOD N.
or
x²_k-1+c==x²_k+r-1+c MOD N
x²_k-1 == x²_k+r-1 MOD N
This is a congruence of squares, and we already have x_k-1!=x_k+r-1
So
(x_k-x_k+r-1)(x_k+x_k+r-1) = 0 mod N
Both GCD(x_k-x_k+r-1,N) and GCD(x_k+x_k+r-1,N) are non-trivial factors of N.
We have factored N.

I have not seen this mentioned in my limited search on the Pollard Rho algorithm.
Is this a new finding?

Walter

Repeat after me....

Google is my friend.

[wwf]

I have looked at the first 50 hits for "pollard rho" and "cycle".
None of the algorithms implement my method above.
When the GCD==N, the algorithms either return failure or the number N.

Both Maxima and YAFU implement the Pollard rho method using f(x)=x²+c.
Neither of these implementations find the factors when GCD==N.

In addition I have read about 20 papers that I have access to and still no mention of this finding.

The reason that I have asked others is that this is not my area of expertise and I cannot say that I have found something new.
I don't have access to all the papers, nor have I studied factoring algorithms in an academic environment.
I do not have enough knowledge to answer my question.

I assume that there are knowledgeable users on this forum who can point me to a previously published version of this finding if one exists.

I do know that the condition GCD=N leads to backtracking in the more sophisticated algorithms, but this backtracking does not handle the case I mentioned above.

I have also ran experiments and formed heuristic arguments that my finding will not improve the success rate of Pollard rho by any significant amount.
So maybe others do know about this, and it is not worth mentioning.

Walter

[R.D. Silverman]

Originally Posted by wwf

I have looked at the first 50 hits for "pollard rho" and "cycle".
None of the algorithms implement my method above.

(1) It's not your method. It is arrogant to claim it as such.
(2) You write:

"(xk-xk+r-1)(xk+xk+r-1) = 0 mod N
Both GCD(xk-xk+r-1,N) and GCD(xk+xk+r-1,N) are non-trivial factors of N.
We have factored N."

There is no guarantee that these are non-trivial factors. One can easily
have GCD(xk-xk+r-1,N) = 1 or N.

[jasonp]

Can you comment on his specific question? Is the above a worthwhile tweak to Pollard Rho?

[R.D. Silverman]

Originally Posted by jasonp

Can you comment on his specific question? Is the above a worthwhile tweak to Pollard Rho?

Huh? See my last post. I did comment on the specific question.

Pollard Rho is such a weak algorithm that it isn't worth bothering with
anyway.

[wwf]

Ah, I see the problem with this method.
As Silverman mentioned, x_k-1+x_k+r-1 == N is a possibility.

Since x_k-1 = N - x_k+r-1 = a, you essentially have found a pair of numbers a and -a MOD N.
It is then easy to see that a²+c == (-a)²+c.

I know Pollard Rho is a weak algorithm.
However, I think even this weak algorithms is worthy of study if I am going to understand how to factor numbers.

Walter

[xilman]

Originally Posted by wwf

Ah, I see the problem with this method.
As Silverman mentioned, x_k-1+x_k+r-1 == N is a possibility.

Since x_k-1 = N - x_k+r-1 = a, you essentially have found a pair of numbers a and -a MOD N.
It is then easy to see that a²+c == (-a)²+c.

I know Pollard Rho is a weak algorithm.
However, I think even this weak algorithms is worthy of study if I am going to understand how to factor numbers.

Walter

Excellent!

Many weak algorithms are worthy of study, partly because realizing why they are weak teaches you how to question and evaluate the strength of algorithms, partly because understanding the history of a subject enables you to learn how progress is made in the real world, and partly because it gives you guidance as to how and why other approaches are important.

[R.D. Silverman]

Originally Posted by xilman

Excellent!

Many weak algorithms are worthy of study, partly because realizing why they are weak teaches you how to question and evaluate the strength of algorithms, partly because understanding the history of a subject enables you to learn how progress is made in the real world, and partly because it gives you guidance as to how and why other approaches are important.

Read (gasp!) Peter Montgomery's (now classic) paper: Speeding the
Pollard and Elliptic Curve Methods of Factorization.

Oh. I forgot. People in this forum have a disdain for reading. (as they have
repeatedly stated)

[VBCurtis]

Originally Posted by R.D. Silverman

Read (gasp!) Peter Montgomery's (now classic) paper: Speeding the
Pollard and Elliptic Curve Methods of Factorization.

Oh. I forgot. People in this forum have a disdain for reading. (as they have
repeatedly stated)

The poster you are berating for not reading already explained he tried READING the entire top 50 google links for what he felt were relevant search terms. Perhaps if you didn't have such disdain for humans not named Silverman, you'd figure out that insulting everyone attempting to learn mathematics fails to produce any useful outcome.

All the same, thanks for showing him the hint he needed to connect the dots and see why his idea didn't help. It's too bad that useful wisdom has to be presented with all the "you idiot, why didn't you think of this already?" wrappers.

[R.D. Silverman]

Originally Posted by VBCurtis

The poster you are berating for not reading already explained he tried READING the entire top 50 google links for what he felt were relevant search terms.

(sarcasm on). Yeah. Right. He read all 50 links.
I suggest thay you consider the level of effort to achieve such a
claim. Reading Peter Montgomery's papers alone would take months.

Perhaps if you didn't have such disdain for humans not named Silverman, you'd figure out that insulting everyone attempting to learn mathematics fails to produce any useful outcome.

I am not the one who has (repeatedly!) stated that they can't be bothered
reading papers. Many in this forum have stated that they can't be bothered to read either books or papers. Yet they continue to (as evidenced by the
recent math subfoum thread) state their "opinions".

As I said before: The questions people ask here are like asking a baker
if he/she has ever put his/her hands into a bag of flour.

Let me try to make this clear. If you do not have a degree in math
(or very strong mathematic maturity; i.e. are at the level of participation
in the IMO) there is NOTHING YOU HAVE TO CONTRIBUTE.

Trying to "improve algorithms" is a clear case of trying to run before you can
walk. One needs to acquire the background number theory and group theory
FIRST.

All the same, thanks for showing him the hint he needed to connect the dots and see why his idea didn't help. It's too bad that useful wisdom has to be presented with all the "you idiot, why didn't you think of this already?" wrappers.

It's also too bad that one of my chronic deriders had to jump with "why
didn't you answer the specific question" AFTER I HAD ALREADY DONE SO.

The answer would be crystal clear to anyone taking a first course in
elementary number theory. Taking such a course is a PRE-REQUISITE
for even attempting to suggest an "improvement" to an existing algorithm.
Why do I say this? Because without the proper background, questions
such as that asked by the OP are indeed like asking if a baker has ever used
flour. It is sheer arrogance to presume that you might have something new
and useful that has not already been considered.

The message does not seem to get through. I'll say it again to the
general audience:

Any idea you might have about improving existing
algorithms has already been thought about.

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)"