mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2013-08-10, 05:28   #1
wwf
 
May 2013

2·3 Posts
Default 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
wwf is offline   Reply With Quote
Old 2013-08-10, 20:20   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by wwf View Post
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....

Google is my friend.
R.D. Silverman is offline   Reply With Quote
Old 2013-08-11, 03:22   #3
wwf
 
May 2013

68 Posts
Default

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)=x2+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
wwf is offline   Reply With Quote
Old 2013-08-11, 13:15   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by wwf View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-08-11, 14:29   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

Can you comment on his specific question? Is the above a worthwhile tweak to Pollard Rho?
jasonp is offline   Reply With Quote
Old 2013-08-11, 14:44   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-08-11, 17:40   #7
wwf
 
May 2013

2·3 Posts
Default

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
wwf is offline   Reply With Quote
Old 2013-08-11, 18:04   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22·32·281 Posts
Default

Quote:
Originally Posted by wwf View Post
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/
xilman is online now   Reply With Quote
Old 2013-08-11, 18:42   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by xilman View Post
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)
R.D. Silverman is offline   Reply With Quote
Old 2013-08-11, 18:50   #10
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,391 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
VBCurtis is offline   Reply With Quote
Old 2013-08-11, 19:19   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

161008 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.

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

Last fiddled with by R.D. Silverman on 2013-08-11 at 19:20 Reason: typo
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Pollard rho with known factor of P-1 henryzz Math 2 2017-08-15 12:13
PFGW can't find a small factor. Arkadiusz Software 7 2013-02-18 12:43
How much ECM does it take to find a given factor? geoff Factoring 5 2004-09-29 20:14
Where I find the best program to it factor keys? I use AMD. chrow Factoring 5 2004-02-19 10:15
How large a factor can P-1 testing find ? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.