Regarding pseudo-random functions for Pollard's Rho factoring method
in [Cryptography]
|
Prev: Regarding pseudo-random functions for Pollard's Rho factoring method
Next: Problem related to a generalized birthday paradox
From: Paul Rubin on 17 Jun 2010 10:24 Bryan <bryanjugglercryptographer(a)yahoo.com> writes: > 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. The explanation in Koblitz's "A Course in Number Theory and Cryptography" (1st ed). is pretty straightforward if that helps (I think it is where I first learned the algorithm). That book is a good one-stop intro to factoring methods other than the NFS. The second edition is considerably expanded and might cover the NFS (I haven't checked). As expected there is a wikipedia article: http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
From: Scott Fluhrer on 22 Jun 2010 09:37
"Mok-Kong Shen" <mok-kong.shen(a)t-online.de> wrote in message news:hvpm78$svg$00$1(a)news.t-online.com... > Mok-Kong Shen wrote: >> 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 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? >> >> I suppose he simply meant that the discussions on the linear >> congruential method there don't result in clear indications of how >> best to choose the values of a and c to obtain a good PRNG. He gave >> also the notorious example RANDU. >> >> I have on the other hand a related question: Knuth wrote there further >> (quotes mean in different font): >> >> The next-simplest case is quadratic, say f(x) = x^2 + 1. We don't >> "know" that this function is sufficiently random, ....... >> In fact, f is probably slightly "better" than random. >> >> On could in practice in all branches of sciences and engineering >> barely get something that is perfect in the theoretical sense. So >> a PRNG could at best be designed such that its output is fairly well >> random, but how could one ever obtain one that is "better" than random? >> There must be some linguistic issue here that is unfamiliar to me. > > A book that contains some discussions on linear congruential generators > is J. Dagpunar, Principles of Random Variate Generation. Here is > a quote from it: > > Despite all the efforts made to search for good multipliers, > high-order distributivity is difficult to achieve on medium > or small word length machines. Combining the output from > several linear congruential generators provides some hope ..... > > BTW, I yet miss any possible explanation of 'slightly "better" than > random' of Knuth's writing above. "better" == "more well suited for the intended application". This definition obviously depends on what the intended application is. In this case, we want a function that: - Is likely to run into a cycle soon (that is, have f^n(x)==f^m(x) mod p for as small values n, m as possible) - For such n, m, have f^n(x)!=f^m(x) mod N (otherwise the pair wouldn't help us factor) - Is consistent mod p (so we don't have to compare every computed f^n, f^m) - Is fairly cheap to compute (we'll be doing it a lot) Now, for criteria #1, f(x) = x^2 + 1 has a smaller range than a truly random function (the output can attain only half of the values mod p, which is less than a random function), and hence it is plausible that it may be more likely to run into a short cycle than a truly random function. -- poncho |