Cryptography: Theory and Practice:The RSA System and Factoring

cryptography: theory and practice Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210   Pub Date: 03/17/95
  

Previous Table of Contents Next


4.8.1 The p - 1 Method

As an example of a simple algorithm that can sometimes be applied to larger integers, we describe Pollard’s 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 qB 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 Fermat’s 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-1980’s, 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.

4.8.2 Dixon’s Algorithm and the Quadratic Sieve

Dixon’s 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 x2y2 (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 x’s 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 x2y2 (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



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net