Number Field Sieve

The fastest known integer factoring algorithm — O(exp(c·n^{1/3}·(log n)^{2/3})) sub-exponential complexity

Sieve Parameters

Number to factor N:

Factor base B (smooth bound): 20 Sieve interval: 30

B-smooth numbers found

Key idea:
Find a,b s.t. a²≡b² (mod N)
Then N | (a-b)(a+b)

NFS steps:
1. Choose polynomial f, deg~n^{1/3}
2. Sieve for (a,b) where f(a,b) is B-smooth in ℤ AND ℚ(α)
3. Linear algebra over 𝔽₂ to find square product
4. Compute gcd(a-b, N)

Complexity: L_N[1/3, (64/9)^{1/3}]
= exp((64/9)^{1/3} (ln N)^{1/3} (ln ln N)^{2/3})