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 616 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

"Bob Silverman"
Nov 2003
North of Boston

7,507 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

"Bob Silverman"
Nov 2003
North of Boston

750710 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 32×5×79 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

"Bob Silverman"
Nov 2003
North of Boston

11101010100112 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 616 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

19·613 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

"Bob Silverman"
Nov 2003
North of Boston

1D5316 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

127748 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

"Bob Silverman"
Nov 2003
North of Boston

165238 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 06:23.

Sun Jan 29 06:23:40 UTC 2023 up 164 days, 3:52, 0 users, load averages: 0.91, 1.06, 1.13