20130810, 05:28  #1 
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 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 cyclefinding 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_{k1} != x_{k+r1}. Now our typical generator is x_{i+1}=x^{2}_{i}+c MOD N. This means we have: x^{2}_{k1}+c==x_{k}==x_{k+r}==x^{2}_{k+r1}+c MOD N. or x^{2}_{k1}+c==x^{2}_{k+r1}+c MOD N x^{2}_{k1} == x^{2}_{k+r1} MOD N This is a congruence of squares, and we already have x_{k1}!=x_{k+r1} So (x_{k}x_{k+r1})(x_{k}+x_{k+r1}) = 0 mod N Both GCD(x_{k}x_{k+r1},N) and GCD(x_{k}+x_{k+r1},N) are nontrivial 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 
20130810, 20:20  #2  
Nov 2003
2^{2}·5·373 Posts 
Quote:
Google is my friend. 

20130811, 03:22  #3 
May 2013
110_{2} Posts 
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^{2}+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 
20130811, 13:15  #4  
Nov 2003
2^{2}×5×373 Posts 
Quote:
(2) You write: "(xkxk+r1)(xk+xk+r1) = 0 mod N Both GCD(xkxk+r1,N) and GCD(xk+xk+r1,N) are nontrivial factors of N. We have factored N." There is no guarantee that these are nontrivial factors. One can easily have GCD(xkxk+r1,N) = 1 or N. 

20130811, 14:29  #5 
Tribal Bullet
Oct 2004
3·1,181 Posts 
Can you comment on his specific question? Is the above a worthwhile tweak to Pollard Rho?

20130811, 14:44  #6 
Nov 2003
2^{2}×5×373 Posts 

20130811, 17:40  #7 
May 2013
2×3 Posts 
Ah, I see the problem with this method.
As Silverman mentioned, x_{k1}+x_{k+r1} == N is a possibility. Since x_{k1} = N  x_{k+r1} = a, you essentially have found a pair of numbers a and a MOD N. It is then easy to see that a^{2}+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 
20130811, 18:04  #8  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{4}·13·53 Posts 
Quote:
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 20130811 at 18:04 Reason: s/word/world/ 

20130811, 18:42  #9  
Nov 2003
2^{2}·5·373 Posts 
Quote:
Pollard and Elliptic Curve Methods of Factorization. Oh. I forgot. People in this forum have a disdain for reading. (as they have repeatedly stated) 

20130811, 18:50  #10  
"Curtis"
Feb 2005
Riverside, CA
3^{2}·563 Posts 
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. 

20130811, 19:19  #11  
Nov 2003
2^{2}·5·373 Posts 
Quote:
I suggest thay you consider the level of effort to achieve such a claim. Reading Peter Montgomery's papers alone would take months. Quote:
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:
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 PREREQUISITE 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)" Last fiddled with by R.D. Silverman on 20130811 at 19:20 Reason: typo 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pollard rho with known factor of P1  henryzz  Math  2  20170815 12:13 
PFGW can't find a small factor.  Arkadiusz  Software  7  20130218 12:43 
How much ECM does it take to find a given factor?  geoff  Factoring  5  20040929 20:14 
Where I find the best program to it factor keys? I use AMD.  chrow  Factoring  5  20040219 10:15 
How large a factor can P1 testing find ?  dsouza123  Software  3  20031211 00:48 