mersenneforum.org On Pollard Rho Cycle
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2020-09-15, 16:23 #1 Deuterium     Sep 2020 22 Posts On Pollard Rho Cycle Dear all, I am new to this forum, I have decided to subscribe because there are lot of intelligent and good people (CRGreathouse is one of them), lot of dreamers (my connational Alberico Lepore) and lot of ideas. Last premise : I am ready to be "dissed" by Silverman, but if he is real Mr Silverman, then he really knows math. So I will accept that. Back to the question then. I have read a lot about Rho Pollard Cycle and I have not understood all, even if it is considered an "easy" factorization method. What I cannot understand is this : after a certain amount of iterations, the alghorhytm spontaneously evolves in a cycle, providing that there will be a certain amount of terms that will repeat in an infinite sequence. First question : if a cycle is detected, is it correct to say that the alghorithm is "failing" and needs to be reinitialized or it's a good thing and it leads to one of the factors ? I think first statement is correct, but please tell me if I am wrong. Second question : In case the answer to first question is that "cycles must be avoided", is there a trick to reinitialize the new sequence in order to obtain good values to get the first factor ? Or it's like "just reinitialize the sequence and cross your fingers ?" Is there a way to "learn" from the first detected cycle and A) Avoid a new cycle B) Get better numbers that leads straightforward to factorization ? Or maybe if you reinitialize it, sooner or later, the iterations will spontaneously fallback in another cycle ? Excuse me for the naive questions, I hope to find here a place for discussion and not finding big headed id10ts like in stackexchange Thanks, Deuterium
 2020-09-15, 16:47 #2 LaurV Romulan Interpreter     Jun 2011 Thailand 22×2,239 Posts You compute a result "modulo something". So, there are only a limited number of possible outcomes. The result is the input of the new "iteration". After long enough time, values will start to repeat, as there are not an "infinite amount" of them. They are only m-1 values, where m is your module. Give it enough time, they will repeat. As the calculus is deterministic, once you get the same value, you will have the same result in the next iteration like you had last time. There, you have a "loop". Loops are good, your goal is to find one (not to avoid it!). Once you find the loop, its "size" gives you the factorization. Say, for a very simple example, you want to factor the number 259. You start with a random value, say 5, and every iteration you square the former result, mod 259. Then you get: 5, 25, 107, 53, 219, 46, 44, 123, 107, bingo. There are only 258 possible outcomes (generally, less then half, why?) so eventually, you will get a value which you already have got in the past. The trick Rho does is just to find when you got this loop and how large it is. Here the example is trivial, you can see that the loop has length 6, at a glance, and you just find out that 7 is a factor. You can either say that 5^4=5^256 and work that as a difference of squares, or you can also say that 25^2=123^2, and work that as a difference of squares (and find the factors as gcd(259, 123-25)=7, and gcd(259, 123+25)=37). But for very large factors, loops can be very large, and what Rho does, it goes to extents to help you detect when you have a loop, and how big it is. So, circle is good, is what you want to find, and you need its "size" to get to the factor. Last fiddled with by LaurV on 2020-09-15 at 17:17
2020-09-15, 16:57   #3
Deuterium

Sep 2020

22 Posts

Quote:
 Originally Posted by LaurV You compute a result "modulo something". So, there are only a limited number of possible outcomes. The result is the input of the new "iteration". After long enough time, values will start to repeat, as there are not an "infinite amount" of them. They are only m-1 values, where m is your module. Give it enough time, they will repeat. As the calculus is deterministic, once you get the same value, you will have the same result in the next iteration like you had last time. There, you have a "loop". Loops a good, your goal is to find one (not to avoid it!). Once you find the loop, its "size" gives you the factorization.

Thanks LaurV !
So, (OMG) , a loop is a positive thing in pollard rho !
What I cannot nderstand now is this: since a loop is somewhat of random (it can pop up after 5 cycles or after 301032103 cycles), can we say that pollard rho is a complete random alghorithm ? I can factor a number of 30 digits in 10 ms or in 10 seconds...

What if we can "force" a loop by some (if exist) mathematical tricks ?

 2020-09-15, 17:10 #4 LaurV Romulan Interpreter     Jun 2011 Thailand 22FC16 Posts The algorithm is not "random". You can use some math tricks, and you can get lucky when you select the starting parameters, but the calculus is deterministic. For example, if you want to factor 2047 and randomly start with 3, you will need 88 iterations to get the loop, but if you randomly start with 622 (which is square root of 1 mod 2047, but you don't know that when you try to factor a big number), you will find after the first iteration 622^2=1 mod 2047, so the gcd(2047, 622-1)=23 and gcd(2047, 622+1)=89 will give you the two factors. (Welcome to the forum, here you have to make a habit not to reply immediately to posts, give yourself, and us, 10 or 20 minutes, we use to edit our posts because we say a lot of stupid things, and realize after, or make typos, or add examples, like in the post above , moreover, if you spent 15 minutes thinking about the subject, you will find many interesting things, and eventually spot mistakes in our posts too, hehe; then, quoting the immediately preceding post also makes not much sense, people know what is about, unless you quote a particular idea that you reply to, or combat; this has the advantage (for me, hehe) that you don't quote my aberrations before I have time to edit them ) Last fiddled with by LaurV on 2020-09-15 at 17:21
2020-09-16, 03:19   #5
CRGreathouse

Aug 2006

5,939 Posts

Quote:
 Originally Posted by Deuterium What I cannot nderstand now is this: since a loop is somewhat of random (it can pop up after 5 cycles or after 301032103 cycles), can we say that pollard rho is a complete random alghorithm ? I can factor a number of 30 digits in 10 ms or in 10 seconds...
It does act, in many ways, like a random algorithm. (In fact, the paper introducing it described it as a Monte Carlo method.) But as LaurV said, it is in fact completely deterministic.

 2020-09-16, 06:28 #6 Deuterium     Sep 2020 22 Posts Hello CR ! What an honour to have a reply from you !! So, since it's a "random algorithm" but works in a deterministic way (Birthday Paradox is helpful), what would be then the difference between using the classical Rho polynomial X^2+C instead of pure random numbers ? Just only because with pure random numbers between 1 and N will never fall in a cycle and since cycle detection leads to factorization this would be pointless ? So basically we need a "thing" (polynomial) that will inevitably fall in a cycle, sooner or later ? I make these confused and basic questions because in internet I have see many implementation of that C alghorithm that try to avoid the cycle, like getting a cycle is a bad thing... Another question : since C is a number that you can choose "freely", if for a choosen C you fall into a cycle and you do not obtain the factors, all you have is to change the C ? Or EVERY cycle you will fall in is always useful for getting the factor ? Thanks CR
2020-09-16, 07:50   #7
xilman
Bamboozled!

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

19·547 Posts

Quote:
 Originally Posted by Deuterium Hello CR ! What an honour to have a reply from you !! So, since it's a "random algorithm" but works in a deterministic way (Birthday Paradox is helpful), what would be then the difference between using the classical Rho polynomial X^2+C instead of pure random numbers ? Just only because with pure random numbers between 1 and N will never fall in a cycle and since cycle detection leads to factorization this would be pointless ? So basically we need a "thing" (polynomial) that will inevitably fall in a cycle, sooner or later ? I make these confused and basic questions because in internet I have see many implementation of that C alghorithm that try to avoid the cycle, like getting a cycle is a bad thing... Another question : since C is a number that you can choose "freely", if for a choosen C you fall into a cycle and you do not obtain the factors, all you have is to change the C ? Or EVERY cycle you will fall in is always useful for getting the factor ? Thanks CR
Not all cycles are useful. If it has length N, for instance, it will report that a factor of N is N. For this reason some values of C are effectively useless.

Further, the trajectory of the values before they cycle can be short or long. For some, a priori unknown values the tail of the rho will be short and for others it will be long. This is just as pecial case of making a choice of the function to be iterated. One way of making Pollard rho a truly random algorithm is to run it in parallel on many processors, each of which are given a randomly chosen iterator. If you know of the ECM this approach should be familiar.

 2020-09-16, 15:51 #8 chris2be8     Sep 2009 2·7·139 Posts The Pollard Rho method is described in detail in The Art of Computer Programming volume 2 by Knuth. Pages 384-386 in the third edition. That should tell you nearly everything you would want to know about it. Chris
 2020-10-14, 15:40 #9 Deuterium     Sep 2020 22 Posts Dear all, I continue on this thread my exploration of this strange and interesting method. Question is : Ok, we have a cycle xk for k=1,2,3,....... I do not understand if there is a way to obtain the result of x2k knowing xk In other words, if I am at iteration number 150, can I directly know the value of iteration of 300 or I do have to make other 150 calculations before getting that result ? Thanks Last fiddled with by Deuterium on 2020-10-14 at 15:42

 Similar Threads Thread Thread Starter Forum Replies Last Post iamue Information & Answers 4 2017-08-09 05:15 mshelikoff Aliquot Sequences 1 2014-12-19 09:15 wombatman Msieve 3 2013-10-12 04:51 davieddy Soap Box 15 2008-08-15 17:15 schickel Msieve 3 2006-11-25 07:14

All times are UTC. The time now is 07:08.

Wed Dec 2 07:08:47 UTC 2020 up 83 days, 4:19, 1 user, load averages: 1.72, 1.70, 1.55