![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
4.8.1 The p - 1 MethodAs 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 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 4.8.2 Dixons Algorithm and the Quadratic SieveDixons algorithm is based on a very simple idea that we already saw in connection with the Rabin Cryptosystem. Namely, if we can find The method uses a factor base, which is a set 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 If we take the product of these three congruences, then we have
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |