From: Paul Rubin on
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

"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