Experience in Factoring Large Integers Using Quadratic Sieve

GQS is a set of computer programs for factoring “large ” inte-gers. It is based on multiple polynomial quadratic sieve. The current version, 3.0, can factor a 82-decimal-digit integer in a PC with AMD 1.8G Hz processor and 512 MB main memory in one day. The largest number I have factored using GQS is RSA-130, a 130-digit integer. This was done in three PC clus-ters, two of which has 16 nodes and the other has 64 nodes. In this talk I will describe how the GQS is implemented and my experience in using GQS. Theory of Quadratic Sieve Quadratic sieve is an “efficient ” algorithm for factoring integers up to about 120 decimal digits. Let n be the integer to be factored. The algorithm first finds a pair of congruent squares x2 ≡ y2 (mod n). Suppose that x 6 ≡ ±y (mod n) Then gcd(n, x − y) and gcd(n, x+ y) are the non-trivial factor of n. 1 For example, 1892 ≡ 502 (mod 33221), gcd(33221,189−50) = 139 and gcd(33221,189+ 50) = 239 are two factors of 332221. Theory of Quadratic Sieve Assume that n is a product of two different primes. x2 ≡ y2 (mod n) ⇒ x2 − y2 ≡ 0 (mod n) ⇒ n | (x − y)(x+ y) x 6 ≡ ±y (mod n) ⇒ n 6 | (x − y) and n 6 | (x+ y) Thus, x − y and x + y each contains only one factor of n, but not both. Therefore, gcd(n, x − y) and gcd(n, x+ y) are non-trivial factors of n. 2 Find Congruent Squares First, find a set of integers whose square modulo n are b-smooth: S = {x | every prime factor of x2 mod n is bounded by b}. Let P = {p | p is prime and p ≤ b}. We then compute a set of S such that the residue x2i mod n of each xi ∈ S can be factored by using the primes in P. x2i mod n = s∏ j=1 p ei,j j. 3 The next step is to find a subset T of S such that xi∈T x2i mod n = xi∈T s∏ j=1 p ei,