Factorization: Quadratic Sieve

17 Dec 2021

Notes Cryptography Factorization: Quadratic Sieve

§ Motivation

We want to continue exploring different methods of factorization, as methods like Pollard's ρ\rho and p−1p-1 have very restrictive constraints that if not met will cause the problem to become degenerate and be as bad as naïve factorization. In context of RSA, we want to find asymptotically fast methods of factorization to determine the viability of RSA.

§ Fermat's Difference of Squares

If nn is a composite with two prime factors, then we can use Fermat's difference of squares method to find the two prime factors.

Fermat's Difference of Two Squares

Given an odd composite integer of the form n=abn = ab, then

ab=(12(a+b))2−(12(a−b))2.ab = \left(\frac{1}{2}(a+b)\right)^2 - \left(\frac{1}{2}(a-b)\right)^2.

Factorization by Difference of Squares

Sps. n=26217n = 26217, we have that n≈159\sqrt{n} \approx 159. We then notice that n+64=1592n + 64 = 159^2.

n=1592−82=(159+8)(159−8)=(167)(151)\begin{align*} n &= 159^2 - 8^2\\ &= (159 + 8)(159 - 8)\\ &= (167)(151) \end{align*}

It is trivial to check that 167167 and 151151 satisfies the equality given in the definition of Fermat's difference of two squares.

If aa and bb are close to n\sqrt{n}, then Fermat's method is faster than trial division. However, this is not the case for most odd composites.

Kraitchik realized that we can find more readily find values that satisfy the difference of squares by working in Zn\mathbb{Z}_n.

Fermat-Kraitchik Method

Find integers u,vu, v satisfying u2≡nv2.u^2 \equiv_n v^2. Then, for values satisfying u̸≡n±vu \not\equiv_n \pm v we have that (u−v,n)(u - v, n) is a non-trivial divisor of nn.

If nn odd and divisible by at least two unique primes, then the about half of the solutions satisfying u2≡nv2u^2 \equiv_n v^2 and (uv,n)=1(uv, n) = 1 will be of the non-trivial form u̸≡n±vu \not\equiv_n \pm v.

§ BB-smooth Numbers

Also referred to as nn-smooth numbers.

BB-smooth

An integer is BB-smooth if all of its prime factors are less than or equal to BB.

de Bruijn Function

Let ψ(x,B)\psi(x, B) denote the number of BB-smooth integers less than or equal to xx.

The function can be well approximated as

Ψ(x,B)∼1π(B)!∏p∈P≤Blog⁡xlog⁡p,\Psi(x, B) \sim \frac{1}{\pi(B)!}\prod_{p\in\mathbb{P}_{\leq B}}\frac{\log x}{\log p},

where π(B)\pi(B) is the number of primes less than or equal to BB.

The exact definition of the prime counting function π(x)\pi(x) relies on understanding some functions relating to the Riemann hypothesis, which is much outside the current scope. Another formulation of the de Bruijn function is shown in the following theorem.

de Bruijn Function

Fix an ε∈(0,12)\varepsilon \in \left(0, \frac{1}{2}\right), and let x,B→∞x, B \to \infty while satisfying

(log⁡x)ε<log⁡B<(log⁡x)1−ε(\log x)^\varepsilon \lt \log B \lt (\log x)^{1-\varepsilon}

Let u=log⁡x/log⁡Bu = \log x / \log B, then the number of BB-smooth numbers less than xx satisfies

ψ(x,B)=x⋅u−u(1+o(1)).\psi(x, B) = x \cdot u^{-u(1+o(1))}.

§ The 3-step Method for Difference of Squares

In Pomerance's Tale of Two Sieves he uses the 3-step method in an example demonstrating Kraitchik's observation[1].

In class, we referred to this method as the 3-step method, but I've found resources referring to the steps done in the 3-step method as the Fermat-Kraitchik method.

Let L(x)=elog⁡xlog⁡log⁡xL(x) = e^{\sqrt{\log x \log\log x}} and let nn be a large integer; setting B=L(n)12B = L(n)^\frac{1}{\sqrt{2}}.

  1. We expect to check approximately L(n)2L(n)^{\sqrt{2}} random numbers modulo nn in order to find
    π(B)∼B/log⁡B\pi(B) \sim B / \log B numbers that are BB-smooth.
  2. We expect to check approximately L(n)2L(n)^{\sqrt{2}} random numbers of the form a2(modn)a^2 \pmod{n} in order to find enough BB-smooth numbers to factor nn.

Then, we can infer that the 3-step method should have a sub-exponential time complexity and have a high probability of factoring nn.

3-step Method

Let nn be an integer we aim to find a non-trivial factor of.

  1. Find a1,…,ara_1, \dots, a_r such that ci≡nai2c_i \equiv_n a_i^2

  2. Take a product ∏n=1scin\prod_{n=1}^{s}c_{i_n} of some cic_i's such that evey prime appearing in the product appears an even number of times.

    ∃b, ∏n=1scin≡b2(modn)\exists b,\ \prod_{n=1}^{s}c_{i_n} \equiv b^2 \pmod{n}

  3. Let a=∏n=1saina = \prod_{n=1}^{s}a_{i_n} and compute d=(n,a−b)d = (n, a - b).

    Since a2≡∏n=1sain≡∏n=1scin≡b2(modn)a^2 \equiv \prod_{n=1}^{s}a_{i_n} \equiv \prod_{n=1}^{s}c_{i_n} \equiv b^2 \pmod{n}, the value dd is likely a non-trivial factor of nn.

Generally, the values of aia_i are chosen randomly and above n\sqrt{n} to avoid most of the trivial cases in Kraitchik's observation where u≡n±vu \equiv_n \pm v. As we will see below, the quadratic sieve chooses values of aia_i by using a quadratic in the form F(t)=t2+nF(t) = t^2 + n, where tt is larger than n\sqrt{n}.

§ The Quadratic Sieve

The Quadratic Sieve is the fastest factorization algorithm we know of for integers of around
∼2350\sim 2^{350}. Asymptotically, it is faster than Lenstra's elliptic curve factorization but slower than the General Number Field sieve.

We will demonstrate the Quadratic Sieve by way of example rather than precise definition.

Quadratic Sieve

Say we wanted to use the quadratic sieve on n=493n = 493.

We will sieve the values of the quadratic function F(t)=t2−493F(t) = t^2 - 493 for t∈[23…38]t\in[23\dots 38] for 1111-smooth numbers.

232425262728293031323334353637383683132183236291348407468531596663732803876951↓2↓2↓2↓2↓2↓2↓2↓2188366183118291174407234531298663366803438951↓4↓4↓4↓4↓4↓4↓4↓4983331835929187407117531149663183803219951↓3↓3↓3↓3↓3↓3↓3↓3↓3↓3↓33831161599729407391771492216180373317↓9↓9↓9183116159972940713591492216180373317↓11↓11↓11183161599729371359149221617373317\newcommand{\arraystretch}{1.25} \newcommand{\dw}[1]{\downarrow\!{\scriptsize\text{#1}}} \footnotesize \begin{array}{| c c c c c c c c c c c c c c c c |}\hline 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33 & 34 &35 & 36 & 37 & 38\\\hline 36 & 83 & 132 & 183 & 236 & 291 & 348 & 407 & 468 & 531 & 596 & 663 & 732 & 803 & 876 & 951\\ \dw{2} & & \dw{2} & & \dw{2} & & \dw{2} & & \dw{2} & & \dw{2} & & \dw{2} & & \dw{2} & \\ 18 & 83 & 66 & 183 & 118 & 291 & 174 & 407 & 234 & 531 & 298 & 663 & 366 & 803 & 438 & 951\\ \dw{4} & & \dw{4} & & \dw{4} & & \dw{4} & & \dw{4} & & \dw{4} & & \dw{4} & & \dw{4} & \\ 9 & 83 & 33 & 183 & 59 & 291 & 87 & 407 & 117 & 531 & 149 & 663 & 183 & 803 & 219 & 951\\ \dw{3} & & \dw{3} & \dw{3} & & \dw{3} & \dw{3} & & \dw{3} & \dw{3} & & \dw{3} & \dw{3} & & \dw{3} & \dw{3} \\ 3 & 83 & 11 & 61 & 59 & 97 & 29 & 407 & 39 & 177 & 149 & 221 & 61 & 803 & 73 & 317\\ \dw{9} & & & & & & & & \dw{9} & \dw{9} & & & & & & \\ 1 & 83 & 11 & 61 & 59 & 97 & 29 & 407 & 13 & 59 & 149 & 221 & 61 & 803 & 73 & 317\\ & & \dw{11} & & & & & \dw{11} & & & & & & \dw{11} & & \\ 1 & 83 & 1 & 61 & 59 & 97 & 29 & 37 & 13 & 59 & 149 & 221 & 61 & 73 & 73 & 317 \\\hline \end{array}

By sieving, we see that F(23)F(23) and F(25)F(25) are 1111-smooth, however, we notice that F(23)F(23) is the product of small primes with even powers modulo 443443.

F(23)≡22⋅32(mod493)b≡F(23)≡2⋅3(mod493)\begin{align*} F(23) &\equiv 2^2\cdot3^2 \pmod{493}\\ b &\equiv \sqrt{F(23)} \equiv 2\cdot 3 \pmod{493} \end{align*}

Then, in terms of the 3-step method we have that our a=23a=23 and b=6b=6, which has a high probability of yielding a non-trivial factor of 493493:

gcd⁡(23−6,493)=17gcd⁡(23+6,493)=29\begin{align*} \gcd(23 - 6, 493) &= 17\\ \gcd(23 + 6, 493) &= 29 \end{align*}

Therefore, by way of quadratic sieve, we get that 1717 and 2929 are non-trivial factors of 493493.

  1. Pomerance, Carl. "Tale of Two Sieves." Notices of the American Mathematical Society, vol. 43, no. 12, Dec. 1996, pp. 1473–1485. ↩︎