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 < xa 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, x2,... defined by xi+ = 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 xt 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,x2), and iteratively computes (х*,х2*) from the previous pair (x*. i, x2i_2), until xm = X2,n for some m. If the tail of the sequence has length Л and the cycle has length p, then the first time that xm = x2m 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, x2,... defined by xo = 2, xi+i = f{xi) = x? + 1 mod p for i > 0. Floyd’s cycle-finding algorithm is utilized to find xm and x2m such that xm = x2m (mod p). Since p divides n but is unknown, this is done by computing the terms x, modulo n and testing if gcd(xTO - x2m, n) > 1. If also gcd(xTO - x2m, n) < n, then a non-trivial factor of n is obtained. (The situation gcd(xm - x2m, 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—a2 + 1 mod n, b<—b2 + 1 mod n, 6t— b2 + 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) = x2 + 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 ()(n1^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) = x2 + 1. For example, the polynomial f(x) = x2 + c may be used as long as с Ф 0, -2.
 
Source
< Prev   CONTENTS   Source   Next >