2.4.4 Quadratic Sieve Factoring

The idea behind quadratic factoring is the following:
Let be x, y ∈ Z, such that x² ≡ y² (mod n), but x ≠ y (mod n). Then n divides x² - y² = (x - y) ⋅(x + y) but n does not divide neither (x - y) nor (x + y). Hence gcd(x - y, n) must be a non-trivial factor of n. A common strategy for finding such x and y is the following:
Let be S = {p₁, p₂, ..., p_t } the set of the first t primes (= factor base). Find pairs (a_i , b_i ) such that:
(i) a_i² ≡ b_i (mod n) and
(ii) b_i = ∏^t_j=1 p_j^{e _ij} , e_ij ≥ 0, so b_i is p_t - smooth.

Now find a subset of b_i's such that its product is a perfect square. That means all the e_ij's have to be even. For simplifying, identify the binary vector v_i = (v_i1 , v_i2 , ..., v_it ) with the exponent vector (e_i1 , e_i2 , ..., e_it ), such that v _ij = e_ij mod 2. If t + 1 pairs (a_i ,b_i ) occur, the t - dimensional vectors v₁ ,v ₂ , ..., v_t+1 are linear dependant over Z₂. Hence there is a subset T ⊆ {1, 2, ..., t + 1} such that ∑ _{i ∈ T} v_i = 0 over Z₂ and so ∏ _{i ∈ T} b_i is a perfect square. It is obvious that ∏_{i ∈ T} a_i² is a perfect square, too. Thus setting x = ∏ _{i ∈ T} a_i and y as a square root of ∏ _{i ∈ T} b_i yields a pair (x, y) such that x² ≡ y² (mod n). If this pair satisfies x ≠ y (mod n), then gcd(x - y, n) yields a non-trivial factor of n. Otherwise you can replace some of the pairs (a_i , b_i ) by new pairs.

Definition: (Legendre- symbol)
The Legendre- symbol (a/b) for a, b ∈ Z is defined as follows:
(a/b) = 0, if p | a,
(a/b) = 1, if a is a quadratic residuo modulo p
(a/b) = -1, if a is a non-quadratic residuo modulo p.

Quadratic Sieve Factoring uses now an efficient method for finding such pairs (a_i , b_i ):
Let be m = ⌊ √n ⌋ , and consider q(x) = x2 + 2mx + m² - n ≈ x² + 2mx which is small (with respect to n), if x is small. The sieve algorithm chooses a_i = (x + m) and checks whether b_i = (x + m)² - n is p_t - smooth. Note that: a_i² = (x + m)² ≡ b_i (mod n). Note also that if a prime p divides b_i it follows that (x + m)² ≡ n (mod p) and so n is a quadratic residuo modulo p. Consequently the factor base only needs to contain such primes p for which the Legendre-symbol (n/p) = 1. Further on the factor base should include "-1" because of the negative b_i's.

Example:
1. Choose a factor base with t = 6 to find non-trivial factors of n = 24961.
Consequently S = {-1, 2, 3, 5, 13, 23} (For 7, 11, 17, 19 is (n/p) = -1)
2. Now compute m = ⌊ √24961 ⌋ = 157.
3. After that you compute 7 a_i's and b_i's with different x's in q(x) = (x + m)² - n, so that q(x) is 23-smooth.
That leads to the following:
x₁ = 0, q(x₁ )= -312 = -2³⋅3⋅13, a₁ = 157, v₁ = (1, 1, 1, 0, 1, 0)
x₂ = 1, q(x₂ )= 3, a₂ = 158, v₂ = (0, 0, 1, 0, 0, 0)
x₃ = -1, q(x₃ )= -625 = -5⁴, a₃ = 156, v₃ = (1, 0, 0, 0, 0, 0)
x₄ = 2, q(x₄ )= 320 = 2⁶⋅5, a₄ = 159, v₄ = (0, 0, 0, 1, 0, 0)
x₅ = -2, q(x₅ )= -936 = -2³⋅3² ⋅13, a₅ = 155, v₁ = (1, 1, 0, 0, 1, 0)
x₆ = 4, q(x₆ )= 960 = 2⁶⋅3⋅5, a₆ = 161, v₆ = (0, 0, 1, 1, 0, 0)
x₇ = -6, q(x₇ )= -2160 = -2⁴⋅3³ ⋅5, a₇ = 151, v₇ = (1, 0, 1, 1, 0, 0)
4. E.g. for T = {1, 2, 5} is v₁ + v₂ + v₅ = 0
5. x = (a₁ ⋅a₂ ⋅a₅ mod n) = 936
6. l₁ = 1, l₂ = 3, l₃ = 2, l₄ = 0, l₅ = 1, l₆ = 0
7. y = -2³ ⋅ 3² ⋅ 13 mod n = 24025

8. Because of 936 ≡ -24025 (mod n), there must be found another T

9 Now for T = {3, 6, 7} is v₃ + v₆ + v₇ = 0
10. x = (a₃ ⋅a₆ ⋅a₇ mod n) = 23045
11. l₁ = 1, l₂ = 5, l₃ = 2, l₄ = 3 , l₅ = 0, l₆ = 0
12. y = -2⁵ ⋅ 3² ⋅ 5³ mod n = 13922 13. Now 23405 ≠ 13922 (mod n), so that ggT(x - y, n) = ggT(9483, 24961) = 109.
That means we found two non-trivial factors of 24961 109 and 229.

Applet quadratic Sieve Factoring

Source code:
QuadAlgSF.java - Applet Surface
QuadAlg.java - Algorithm Class
Matrix.java - Matrix Class

2.5.1 Shank's algorithm