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: Bryan on 19 Jun 2010 03:40 Paul Rubin wrote: > 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). Thanks. The Koblitz book has been on my really-should-get-and-read list for a while. -- --Bryan
From: Bryan on 19 Jun 2010 04:50 Martin Lauridsen wrote: > Bryan wrote: > > Martin Lauridsen wrote: > > > 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. I muddied that up. The issue is the long cycle. > Thanks for your reply. I only have the 3rd edition available. Perhaps > you could state which section it occurs? Ah, yes. Knuth is best cited by section designation rather than page, kind of like Shakespeare or the Bible. The section on Pollard's rho method of factoring is 4.5.4 in the second edition, and I think Knuth retained the sectioning as he updated the editions. The theory explaining why the linear congruential method has to longer period than a random function is in 3.2.1. > 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. What's left to look for? Even if I confused the issue a bit, Scott Fluhrer nailed it: f(x) = ax+c mod n is a poor choice because the size of a repeating cycle is too long. For Pollard's rho method, we do not want an f() that maximizes the period. The algorithm finds a non-trivial factor 'p' of the given 'n' when if find a repeated value of f* mod p that is not also a repeat mod n. The linear congruential method will find a repeat mod p in p iterations, which is as fast and as slow as trial division. A random function that is consistent mod p will find a repeat in p**(1/2) expected time. You can, and should, ignore the response from Mok-Kong Shen. Difficulty in choosing the parameters for a linear congruential generator is not the issue. Shen begins his post "I suppose," and all he does is suppose; he does not put forth a serious effort to understand the material. -- --Bryan Olson
From: Mok-Kong Shen on 22 Jun 2010 02:46
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. Thanks. M. K. Shen |