![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
Reducing the expressions inside the parentheses modulo n, we have Then we compute finding the factor 115759 of n. Suppose for 1 ≤ j ≤ C. For each j, consider the vector If we can find a subset of the ajs that sum modulo 2 to the vector (0, . . . , 0), then the product of the corresponding xjs will use each factor in 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 a1, a2, a3 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 a1, . . . , aC that sums modulo 2 to the all-zero vector is nothing more than finding a linear dependence (over It remains to discuss how we obtain integers xj such that the values xj2 mod n factor completely over the factor base There is, of course, a trade-off here: if and this leads to an expected running time of The number field sieve is a more recent factoring algorithm from the late 1980s. It also factors n by constructing a congruence x2 ≡ y2 (mod n), but it does so by means of computations in rings of algebraic integers. 4.8.3 Factoring Algorithms in PracticeThe 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, 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 2251 - 1 (this computation was done by Davis, Holdridge, and Simmons). Progress continued throughout the 1980s, 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
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |