Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
As an example of a simple algorithm that can sometimes be applied to larger integers, we describe Pollards p - 1 algorithm, which dates from 1974. This algorithm, presented in Figure 4.15, has two inputs: the (odd) integer n to be factored, and a bound B. Here is what is taking place in the p - 1 algorithm: Suppose p is a prime divisor of n, and q ≤ B for every prime power q | (p - 1). Then it must be the case that
At the end of the for loop (step 2),
so
since p | n. Now,
by Fermats theorem. Since (p - 1) | [B!, we have that
(in step 3). Thus, in step 4,
and
so
The integer d will be a non-trivial divisor of n (unless a = 1 in step 3). Having found a non-trivial factor d, we would then proceed to attempt to factor d and n/d if they are composite.
Here is an example to illustrate.
Example 4.14
Suppose n = 15770708441. If we apply the p - 1 algorithm with B = 180, then we find that a = 11620221425 in step 3, and d is computed to be 135979. In fact, the complete factorization of n into primes is
in this case, the factorization succeeds because 135978 has only small prime factors:
Hence, by taking B ≥ 173, it will be the case that 135978 | B!, as desired.
In the algorithm, there are B - 1 modular exponentiations, each requring at most 2log2 B modular multiplications using square-and-multiply. The gcd computation can be done in time O((log n)3) using the Euclidean algorithm. Hence, the complexity of the algorithm is O(B log B(log n)2 + (log n)3). If the integer B is O((log n)i) for some fixed integer i, then the algorithm is indeed a polynomial-time algorithm; however, for such a choice of B the probability of success will be very small. On the other hand, if we increase the size of B drastically, say to , then the algorithm will be successful, but it will be no faster than trial division.
Thus, the drawback of this method is that it requires n to have a prime factor p such that p - 1 has only small prime factors. It would be very easy to construct an RSA modulus n = pq which would resist factorization by this method. One would start by finding a large prime p1 such that p = 2p1 + 1 is also prime, and a large prime q1 such that q = 2q1 + 1 is also prime (using one of the Monte Carlo primality testing algorithms discussed in Section 4.5). Then the RSA modulus n = pq will be resistant to factorization using the p - 1 method.
The more powerful elliptic curve algorithm, developed by Lenstra in the mid-1980s, is in fact a generalization of the p - 1 method. We will not discuss the theory at all here, but we do mention that the success of the elliptic curve method depends on the more likely situation that an integer close to p has only small prime factors. Whereas the p - 1 method depends on a relation that holds in the group , the elliptic curve method involves groups defined on elliptic curves modulo p.
Dixons algorithm is based on a very simple idea that we already saw in connection with the Rabin Cryptosystem. Namely, if we can find (mod n) such that x2 ≡ y2 (mod n), then gcd(x - y, n) is a non-trivial factor of n.
The method uses a factor base, which is a set small primes. We first obtain several integers x such that all the prime factors of x2 mod n occur in the factor base . (How this is done will be discussed a bit later.) The idea is to then take the product of several of these xs in such a way that every prime in the factor base is used an even number of times. This then gives us a congruence of the desired type x2 ≡ y2 (mod n), which (we hope) will lead to a factorization of n.
We illustrate with a carefully contrived example.
Example 4.15
Suppose n = 15770708441 (this was the same n that we used in Example 4.14). Let . Consider the three congruences:
If we take the product of these three congruences, then we have
Previous | Table of Contents | Next |
Copyright © CRC Press LLC