mersenneforum.org Can Pollard Rho cycles be used to find a factor?
 Register FAQ Search Today's Posts Mark Forums Read

 2013-08-10, 05:28 #1 wwf   May 2013 2·3 Posts Can Pollard Rho cycles be used to find a factor? Pollard's rho algorithm uses a generator function to generate a sequence of numbers xi. We check for factors by calculating GCD(abs(xi-x2i),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 xk be the first number in the cycle of length r. Thus xk==xk+r. If k!=1 (is this usually the case?), then we also have: xk-1 != xk+r-1. Now our typical generator is xi+1=x2i+c MOD N. This means we have: x2k-1+c==xk==xk+r==x2k+r-1+c MOD N. or x2k-1+c==x2k+r-1+c MOD N x2k-1 == x2k+r-1 MOD N This is a congruence of squares, and we already have xk-1!=xk+r-1 So (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. I have not seen this mentioned in my limited search on the Pollard Rho algorithm. Is this a new finding? Walter
2013-08-10, 20:20   #2
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by wwf Pollard's rho algorithm uses a generator function to generate a sequence of numbers xi. We check for factors by calculating GCD(abs(xi-x2i),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 xk be the first number in the cycle of length r. Thus xk==xk+r. If k!=1 (is this usually the case?), then we also have: xk-1 != xk+r-1. Now our typical generator is xi+1=x2i+c MOD N. This means we have: x2k-1+c==xk==xk+r==x2k+r-1+c MOD N. or x2k-1+c==x2k+r-1+c MOD N x2k-1 == x2k+r-1 MOD N This is a congruence of squares, and we already have xk-1!=xk+r-1 So (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. I have not seen this mentioned in my limited search on the Pollard Rho algorithm. Is this a new finding? Walter
Repeat after me....

2013-08-11, 13:15   #4
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 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.

 2013-08-11, 14:29 #5 jasonp Tribal Bullet     Oct 2004 3·1,163 Posts Can you comment on his specific question? Is the above a worthwhile tweak to Pollard Rho?
2013-08-11, 14:44   #6
R.D. Silverman

Nov 2003

1C4016 Posts

Quote:
 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.

 2013-08-11, 17:40 #7 wwf   May 2013 2·3 Posts Ah, I see the problem with this method. As Silverman mentioned, xk-1+xk+r-1 == N is a possibility. Since xk-1 = N - xk+r-1 = a, you essentially have found a pair of numbers a and -a MOD N. It is then easy to see that a2+c == (-a)2+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
2013-08-11, 18:04   #8
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

22·32·281 Posts

Quote:
 Originally Posted by wwf Ah, I see the problem with this method. As Silverman mentioned, xk-1+xk+r-1 == N is a possibility. Since xk-1 = N - xk+r-1 = a, you essentially have found a pair of numbers a and -a MOD N. It is then easy to see that a2+c == (-a)2+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.

Last fiddled with by xilman on 2013-08-11 at 18:04 Reason: s/word/world/

2013-08-11, 18:42   #9
R.D. Silverman

Nov 2003

26·113 Posts

Quote:
 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)

2013-08-11, 18:50   #10
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

4,391 Posts

Quote:
 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.

2013-08-11, 19:19   #11
R.D. Silverman

Nov 2003

161008 Posts

Quote:
 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.
I suggest thay you consider the level of effort to achieve such a
claim. Reading Peter Montgomery's papers alone would take months.

Quote:
 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.

Quote:
 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

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

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

Last fiddled with by R.D. Silverman on 2013-08-11 at 19:20 Reason: typo

 Similar Threads Thread Thread Starter Forum Replies Last Post henryzz Math 2 2017-08-15 12:13 Arkadiusz Software 7 2013-02-18 12:43 geoff Factoring 5 2004-09-29 20:14 chrow Factoring 5 2004-02-19 10:15 dsouza123 Software 3 2003-12-11 00:48

All times are UTC. The time now is 09:20.

Fri Oct 23 09:20:29 UTC 2020 up 43 days, 6:31, 0 users, load averages: 1.55, 1.53, 1.65