Regarding pseudo-random functions for Pollard's Rho factoring method
in [Cryptography]
|
Prev: Semiautomatic Hybrid Block_Stream Cipher
Next: Regarding pseudo-random functions for Pollard's Rho factoring method
From: Martin Lauridsen on 17 Jun 2010 04:21 On p. 385 of The art of Computer programming vol. 2 by Knuth, he states that the function f(x) = ax + c is not random enough for the purpose of Pollard's Rho method, referring back to Chapter 3. I can't seem to find where he states that in Chapter 3. Can anyone help me out here? Why is f(x) = ax + c not random enough?
From: Bryan on 17 Jun 2010 06:20 Martin Lauridsen wrote: > On p. 385 of The art of Computer programming vol. 2 by Knuth, he > states that the function f(x) = ax + c is not random enough for the > purpose of Pollard's Rho method, referring back to Chapter 3. I find that on page 369 (second edition). > I can't > seem to find where he states that in Chapter 3. > > Can anyone help me out here? Why is f(x) = ax + c not random enough? Ah, good question. The answer is that it takes too long to cycle, and worse, with high probability it cycles back to the starting value and thus fails to form a rho. Remember why the algorithm is called the "rho" method: it is named for lower-case Greek letter rho, which has a tail leading into a loop. The algorithm walks the iterated pseudo-random function, hoping to find that outputs, modulo a non-trivial factor p, form a non-empty tail leading into a cycle. The algorithm detects such a cycle without yet knowing the factor by looking at the GCD. I first read about Pollard's rho method in Knuth, and was baffled. I much prefer the presentation in Cormen, Leiserson, Rivest (and Stein), /Introduction to Algorithms/. There are also some fine explanations you can Google up for free. -- --Bryan Olson
From: Bryan on 17 Jun 2010 06:38 Martin Lauridsen wrote: > On p. 385 of The art of Computer programming vol. 2 by Knuth, I find it on page 369 (second edition). > he > states that the function f(x) = ax + c is not random enough for the > purpose of Pollard's Rho method, referring back to Chapter 3. I can't > seem to find where he states that in Chapter 3. > > Can anyone help me out here? Why is f(x) = ax + c not random enough? Ah, good question. The answer is that it takes too long to cycle, and worse, with high probability it cycles back to the initial value and thus fails to form a rho. Remember why the algorithm is called the "rho" method: it is named for the lower-case Greek letter rho, which has a tail leading into a loop. The algorithm walks the iterated pseudo-random function, hoping to find that the outputs, modulo a non-trivial factor p, form a non-empty tail leading into the inevitable loop. The algorithm can detect the cycle without yet knowing p by taking the GCD. I first read of Pollard's rho method in Knuth, and was baffled. I much prefer the presentation in Cormen, Leiserson, Rivest, (and Stein) / Introduction to Algorithms/. There are also some fine explanations you can Google up for free. -- --Bryan Olson [Sorry if this message gets double-posted. Didn't seem to work the first time.]
From: Martin Lauridsen on 17 Jun 2010 06:53 On 17 Jun., 12:38, Bryan <bryanjugglercryptograp...(a)yahoo.com> wrote: > Martin Lauridsen wrote: > > On p. 385 of The art of Computer programming vol. 2 by Knuth, > > I find it on page 369 (second edition). > > > he > > states that the function f(x) = ax + c is not random enough for the > > purpose of Pollard's Rho method, referring back to Chapter 3. I can't > > seem to find where he states that in Chapter 3. > > > Can anyone help me out here? Why is f(x) = ax + c not random enough? > > Ah, good question. The answer is that it takes too long to cycle, and > worse, with high probability it cycles back to the initial value and > thus fails to form a rho. > > Remember why the algorithm is called the "rho" method: it is named for > the lower-case Greek letter rho, which has a tail leading into a loop. > The algorithm walks the iterated pseudo-random function, hoping to > find that the outputs, modulo a non-trivial factor p, form a non-empty > tail leading into the inevitable loop. The algorithm can detect the > cycle without yet knowing p by taking the GCD. > > I first read of Pollard's rho method in Knuth, and was baffled. I much > prefer the presentation in Cormen, Leiserson, Rivest, (and Stein) / > Introduction to Algorithms/. There are also some fine explanations you > can Google up for free. > > -- > --Bryan Olson > [Sorry if this message gets double-posted. Didn't seem to work the > first time.] Hi Bryan, Thanks for your reply. I only have the 3rd edition available. Perhaps you could state which section it occurs? On page 369 in the 3rd edition, is an analysis of Euclids algorithm. As far as I remember, CLRS does not attend why f(x) = ax+c is not random enough. I will try looking for more sources online. Thanks.
From: Scott Fluhrer on 17 Jun 2010 07:55
"Martin Lauridsen" <martinlauridsen(a)gmail.com> wrote in message news:1f4b9234-efa9-4ffd-81d0-540f1f48ec08(a)k39g2000yqd.googlegroups.com... > On p. 385 of The art of Computer programming vol. 2 by Knuth, he > states that the function f(x) = ax + c is not random enough for the > purpose of Pollard's Rho method, referring back to Chapter 3. I can't > seem to find where he states that in Chapter 3. > > Can anyone help me out here? Why is f(x) = ax + c not random enough? Well, assuming a is relatively prime to the number being factored, ax+c is a permutation, which is pretty far from a random function. For example, the expected size of repeat from cycling is O(p) for a random permutation of size p and O(sqrt(p)) for a random permutation of size p. Here's why that's important for Pollard Rho; that searches for a pair (n != m) where f^n(x) = f^m(x) mod p for some factor p of N. Now, if f is a random function, then we'd expect there to be such a pair n, m < O(sqrt(p)). However, if f is a random permutation, then we don't expect such a pair until we get close to O(p) (at which point we're no better off than trial division). |