CODEWITHSUNDEEP
algorithm
SlashGeek
SlashGeek

Reputation: 575

Pollard Rho factorization method

Pollard Rho factorization method uses a function generator f(x) = x^2-a(mod n) or f(x) = x^2+a(mod n) , is the choice of this function (parabolic) has got any significance or we may use any function (cubic , polynomial or even linear) as we have to identify or find the numbers belonging to same congruence class modulo n to find the non trivial divisor ?

Upvotes: 3

Views: 1893

Answers (1)

mcdowella
mcdowella

Reputation: 19601

In Knuth Vol II (The Art Of Computer Programming - Seminumerical Algorithms) section 4.5.4 Knuth says

Furthermore if f(y) mod p behaves as a random mapping from the set {0, 1, ... p-1} into itself, exercise 3.1-12 shows that the average value of the least such m will be of order sqrt(p)... From the theory in Chapter 3, we know that a linear polynomial f(x) = ax + c will not be sufficiently random for our purpose. The next simplest case is quadratic, say f(x) = x^2 + 1. We don't know that this function is sufficiently random, but our lack of knowledge tends to support the hypothesis of randomness, and empirical tests show that this f does work essentially as predicted

The probability theory that says that f(x) has a cycle of length about sqrt(p) assumes in particular that there can be two values y and z such that f(y) = f(z) - since f is chosen at random. The rho in Pollard Rho contains such a junction, with the cycle containing multiple lines leading on to it. For a linear function f(x) = ax + b then for gcd(a, p) = 1 mod p (which is likely since p is prime) f(y) = f(z) means that y = z mod p, so there are no such junctions.

If you look at http://www.agner.org/random/theory/chaosran.pdf you will see that the expected cycle length of a random function is about the sqrt of the state size, but the expected cycle length of a random bijection is about the state size. If you think of generating the random function only as you evaluate it you can see that if the function is entirely random then every value seen so far is available to be chosen again at random to find a cycle, so the odds of closing the cycle increase with the cycle length, but if the function has to be invertible the only way to close the cycle is to generate the starting point, which is much less likely.

Upvotes: 2

Related Questions