Trial division
Once it is established that an integer n is composite, before expending vast amounts of time with more powerful techniques, the first thing that should be attempted is trial division by all “small” primes. Here, “small” is determined as a function of the size of n. As an extreme case, trial division can be attempted by all prunes up to sjn. If this is done, trial division will completely factor n but the procedure will take roughly y/n divisions in the worst case when n is a product of two prunes of the same size. In general, if the factors found at each stage are tested for primality, then trial division to factor n completely takes 0(p + lg n) divisions, where p is the second-largest prime factor of n.
Fact 3.7 indicates that if trial division is used to factor a randomly chosen large integer n, then the algorithm can be expected to find some small factors of n relatively quickly, and expend a large amount of time to find the second largest prime factor of n.
- 3.7 Fact Let n be chosen uniformly at random from the interval [1, ж].
- (i) If I < a < 1, then the probability that the largest prime factor of n is < x^{a} is approximately 1 + In q. Thus, for example, the probability that n has a prime factor
> ^/(r is In 2 « 0.69.
- (ii) The probability that the second-largest prime factor of n is < ж^{0,2117} is about i.
- (iii) The expected total number of prime factors of n is In In x + 0(1). (If n = П pf. the total number of prime factors of n is e,.)
Pollard’s rho factoring algorithm
Pollard’s rho algorithm is a special-purpose factoring algorithm for finding small factors of a composite integer.
Let / : 5 —» 5 be a random function, where S is a finite set of cardinality n. Let xo be a random element of S, and consider the sequence xo.xi, x_{2},... defined by x_{i+} = f{xi) for i > 0. Since S is finite, the sequence must eventually cycle, and consists of a tail of expected length yjтгп/8 followed by an endlessly repeating cycle of expected length a/7to/8 (see Fact 2.37). A problem that arises in some cryptanalytic tasks, including integer factorization (Algorithm 3.9) and the discrete logarithm problem (Algorithm 3.60), is of finding distinct indices i and j such that x, = Xj (a collision is then said to have occurred).
An obvious method for finding a collision is to compute and store Xi for i = 0,1,2,... and look for duplicates. The expected number of inputs that must be tried before a duplicate is detected is yJirn/2 (Fact 2.27). This method requires 0(y/n) memory and 0{/n) time, assuming the x_{t} are stored in a hash table so that new entries can be added in constant time.
3.8 Note (Floyd’s cycle-finding algorithm) The large storage requirements in the above technique for finding a collision can be eliminated by using Floyd’s cycle-finding algorithm. In this method, one starts with the pair (xi,x_{2}), and iteratively computes (х*,х_{2}*) from the previous pair (x*. i, x_{2i}__{2}), until x_{m} = X2,_{n} for some m. If the tail of the sequence has length Л and the cycle has length p, then the first time that x_{m} = x_{2m} is when m = p( 1 + [X/p). Note that A < m < A + p, and consequently the expected running time of this method is 0(_{v}/n).
Now, let p be a prime factor of a composite integer n. Pollard’s rho algorithm for factoring n attempts to find duplicates in the sequence of integers xo,xi, x_{2},... defined by xo = 2, x_{i+}i = f{xi) = x? + 1 mod p for i > 0. Floyd’s cycle-finding algorithm is utilized to find x_{m} and x_{2m} such that x_{m} = x_{2m} (mod p). Since p divides n but is unknown, this is done by computing the terms x, modulo n and testing if gcd(x_{TO} - x_{2m}, n) > 1. If also gcd(x_{TO} - x_{2m}, n) < n, then a non-trivial factor of n is obtained. (The situation gcd(x_{m} - x_{2m}, n) = n occurs with negligible probability.)
3.9 Algorithm Pollard’s rho algorithm for factoring integers
INPUT: a composite integer n that is not a prime power.
OUTPUT: a non-trivial factor d of a.
- 1. Set ai—2, hi—2.
- 2. For г = 1,2,... do the following:
- 2.1 Compute at—a^{2} + 1 mod n, b<—b^{2} + 1 mod n, 6t— b^{2} + 1 mod n.
- 2.2 Compute d = gcd(a — b, n).
- 2.3 If 1 < d < n then retum(d) and terminate with success.
- 2.4 If d = n then terminate the algorithm with failure (see Note 3.12).
- 3.10 Example (Pollard’s rho algorithm for finding a non-trivial factor of n = 455459) The following table lists the values of variables a, b, and d at the end of each iteration of step 2 of Algorithm 3.9.
a |
b |
d |
5 |
26 |
1 |
26 |
2871 |
1 |
677 |
179685 |
1 |
2871 |
155260 |
1 |
44380 |
416250 |
1 |
179685 |
43670 |
1 |
121634 |
164403 |
1 |
155260 |
247944 |
1 |
44567 |
68343 |
743 |
Hence two non-trivial factors of 455459 are 743 and 455459/743 = 613. □
- 3.11 Fact Assuming that the function f(x) = x^{2} + 1 mod p behaves like a random function, the expected time for Pollard’s rho algorithm to find a factor p of n is 0( у/p) modular multiplications. This implies that the expected time to find a non-trivial factor of n is ()(n^{1}^^{1}) modular multiplications.
- 3.12 Note (options upon termination with failure) If Pollard’s rho algorithm terminates with failure, one option is to try again with a different polynomial / having integer coefficients instead of f(x) = x^{2} + 1. For example, the polynomial f(x) = x^{2} + c may be used as long as с Ф 0, -2.