Modern Cryptography: Theory and Practice

Reducing the expressions inside the parentheses modulo n, we have

Then we compute

finding the factor 115759 of n.

Suppose is the factor base. Let C be slightly larger than B (say C = B + 10), and suppose we have obtained C congruences:

for 1 ≤ j ≤ C. For each j, consider the vector

If we can find a subset of the a_j’s that sum modulo 2 to the vector (0, . . . , 0), then the product of the corresponding x_j’s will use each factor in an even number of times.

We illustrate by returning to Example 4.15, where there exists a dependence even though C < B in this case.

Example 4.15  (Cont.)

The three vectors a₁, a₂, a₃ are as follows:

It is easy to see that

This gives rise to the congruence we saw earlier that successfully factored n.

Observe that finding a subset of the C vectors a₁, . . . , a_C that sums modulo 2 to the all-zero vector is nothing more than finding a linear dependence (over ) of these vectors. Provided C > B, such a linear dependence must exist, and it can be found easily using the standard method of Gaussian elimination. The reason why we take C > B + 1 is that there is no guarantee that any given congruence will yield the factorization of n. Approximately 50% of the time it will turn out that x ≡ ±y (mod n). But if C > B + 1, then we can obtain several such congruences (arising from different linear dependencies among the a_j’s). Hopefully, at least one of the resulting congruences will yield the factorization.

It remains to discuss how we obtain integers x_j such that the values x_j² mod n factor completely over the factor base . There are several methods of doing this. One common approach is the Quadratic Sieve due to Pomerance, which uses integers of the form The name “quadratic sieve” comes from a sieving procedure (which we will not describe here) that is used to determine those x_j’s that factor over :

There is, of course, a trade-off here: if is large, then it is more likely that an integer x_j factors over . But the larger B is, the more congruences we need to accumulate before we are able to find a dependence relation. The optimal choice for B is approximately

and this leads to an expected running time of

The number field sieve is a more recent factoring algorithm from the late 1980’s. It also factors n by constructing a congruence x² ≡ y² (mod n), but it does so by means of computations in rings of algebraic integers.

4.8.3 Factoring Algorithms in Practice

The asymptotic running times of the quadratic sieve, elliptic curve and number field sieve are as follows:

The notation o(1) denotes a function of n that approaches 0 as n → ∞, and p denotes the smallest prime factor of n.

In the worst case, and the asymptotic running times of the quadratic sieve and elliptic curve algorithms are essentially the same. But in such a situation, quadratic sieve generally outperforms elliptic curve. The elliptic curve method is more useful if the prime factors of n are of differing size. One very large number that was factored using the elliptic curve method was the Fermat number in 1988 by Brent.

For factoring RSA moduli (where n = pq, p, q are prime, and p and q are roughly the same size), the quadratic sieve is currently the most successful algorithm. Some notable milestones have included the following factorizations. In 1983, the quadratic sieve successfully factored a 69-digit number that was a (composite) factor of 2²⁵¹ - 1 (this computation was done by Davis, Holdridge, and Simmons). Progress continued throughout the 1980’s, and by 1989, numbers having up to 106 digits were factored by this method by Lenstra and Manasse, by distributing the computations to hundreds of widely separated workstations (they called this approach “factoring by electronic mail”).

More recently, in April 1994, a 129-digit number known as RSA-129 was factored by Atkins, Graff, Lenstra, and Leyland using the quadratic sieve. (The numbers RSA-100, RSA-110, . . . , RSA-500 are a list of RSA moduli publicized on the Internet as “challenge” numbers for factoring algorithms. Each number RSA-d is a d-digit number that is the product of two primes of approximately the same length.) The factorization of RSA-129 required 5000 MIPS-years of computing time donated by over 600 researchers around the world.

The number field sieve is the most recent of the three algorithms. It seems to have great potential since its asymptotic running time is faster than either quadratic sieve or the elliptic curve. It is still in developmental stages, but people have speculated that number field sieve might prove to be faster for numbers having more than about 125-130 digits. In 1990, the number field sieve was used by Lenstra, Lenstra, Manasse, and Pollard to factor into three primes having 7, 49 and 99 digits.

Copyright © CRC Press LLC