20200915, 16:23  #1 
Sep 2020
4_{10} 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 
20200915, 16:47  #2 
Romulan Interpreter
Jun 2011
Thailand
9,161 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 m1 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, 12325)=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 20200915 at 17:17 
20200915, 16:57  #3  
Sep 2020
2^{2} Posts 
Quote:
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 ? 

20200915, 17:10  #4 
Romulan Interpreter
Jun 2011
Thailand
10001111001001_{2} 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, 6221)=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 20200915 at 17:21 
20200916, 03:19  #5 
Aug 2006
3·1,987 Posts 
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.

20200916, 06:28  #6 
Sep 2020
2^{2} 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 
20200916, 07:50  #7  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10518_{10} Posts 
Quote:
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. 

20200916, 15:51  #8 
Sep 2009
1986_{10} Posts 
The Pollard Rho method is described in detail in The Art of Computer Programming volume 2 by Knuth. Pages 384386 in the third edition. That should tell you nearly everything you would want to know about it.
Chris 
20201014, 15:40  #9 
Sep 2020
2^{2} Posts 
Dear all,
I continue on this thread my exploration of this strange and interesting method. Question is : Ok, we have a cycle x_{k} for k=1,2,3,....... I do not understand if there is a way to obtain the result of x_{2k} knowing x_{k} 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 20201014 at 15:42 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Hibernate cycle when working with Prime95?  iamue  Information & Answers  4  20170809 05:15 
Immediate antecedents for sequences terminating in a cycle  mshelikoff  Aliquot Sequences  1  20141219 09:15 
PostProcessing Fails at Cycle Optimization  wombatman  Msieve  3  20131012 04:51 
Cycle lane v Earthquake  davieddy  Soap Box  15  20080815 17:15 
Question about cycle counting in MSieve  schickel  Msieve  3  20061125 07:14 