mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-09-15, 16:23   #1
Deuterium
 
Deuterium's Avatar
 
Sep 2020

22 Posts
Default 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
Deuterium is offline   Reply With Quote
Old 2020-09-15, 16:47   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

3×2,953 Posts
Default

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
LaurV is online now   Reply With Quote
Old 2020-09-15, 16:57   #3
Deuterium
 
Deuterium's Avatar
 
Sep 2020

1002 Posts
Default

Quote:
Originally Posted by LaurV View Post
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 ?
Deuterium is offline   Reply With Quote
Old 2020-09-15, 17:10   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

885910 Posts
Default

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
LaurV is online now   Reply With Quote
Old 2020-09-16, 03:19   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

593010 Posts
Default

Quote:
Originally Posted by Deuterium View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2020-09-16, 06:28   #6
Deuterium
 
Deuterium's Avatar
 
Sep 2020

416 Posts
Default

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
Deuterium is offline   Reply With Quote
Old 2020-09-16, 07:50   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×32×281 Posts
Default

Quote:
Originally Posted by Deuterium View Post
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.
xilman is offline   Reply With Quote
Old 2020-09-16, 15:51   #8
chris2be8
 
chris2be8's Avatar
 
Sep 2009

111011110012 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2020-10-14, 15:40   #9
Deuterium
 
Deuterium's Avatar
 
Sep 2020

22 Posts
Default

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
Deuterium is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Hibernate cycle when working with Prime95? iamue Information & Answers 4 2017-08-09 05:15
Immediate antecedents for sequences terminating in a cycle mshelikoff Aliquot Sequences 1 2014-12-19 09:15
Post-Processing Fails at Cycle Optimization wombatman Msieve 3 2013-10-12 04:51
Cycle lane v Earthquake davieddy Soap Box 15 2008-08-15 17:15
Question about cycle counting in MSieve schickel Msieve 3 2006-11-25 07:14

All times are UTC. The time now is 04:18.

Sat Oct 24 04:18:30 UTC 2020 up 44 days, 1:29, 1 user, load averages: 1.41, 1.43, 1.43

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.