Motivation§

We want to continue exploring different methods of factorization, as methods like Pollard’s $\rho$ and $p-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 $n$ 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 = ab$, then

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

Factorization by Difference of Squares

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

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

It is trivial to check that $167$ and $151$ satisfies the equality given in the definition of Fermat’s difference of two squares.

If $a$ and $b$ are close to $\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 $\mathbb{Z}_n$.

Fermat-Kraitchik Method

Find integers $u, v$ satisfying $u^2 \equiv_n v^2.$ Then, for values satisfying $u \not\equiv_n \pm v$ we have that $(u - v, n)$ is a non-trivial divisor of $n$.

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

$B$-smooth Numbers§

Also referred to as $n$-smooth numbers.

$B$-smooth

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

de Bruijn Function

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

The function can be well approximated as

$$ \Psi(x, B) \sim \frac{1}{\pi(B)!}\prod_{p\in\mathbb{P}_{\leq B}}\frac{\log x}{\log p}, $$

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

The exact definition of the prime counting function $\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.

Theorem 20.1

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

$$ (\log x)^\varepsilon \lt \log B \lt (\log x)^{1-\varepsilon} $$

Let $u = \log x / \log B$, then the number of $B$-smooth numbers less than $x$ satisfies

$$ \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 observation1.

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) = e^{\sqrt{\log x \log\log x}}$ and let $n$ be a large integer; setting $B = L(n)^\frac{1}{\sqrt{2}}$.

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

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

3-step Method

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

  1. Find $a_1, \dots, a_r$ such that $c_i \equiv_n a_i^2$

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

    $$\exists b,\ \prod_{n=1}^{s}c_{i_n} \equiv b^2 \pmod{n}$$

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

    Since $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 $d$ is likely a non-trivial factor of $n$.

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

The Quadratic Sieve§

The Quadratic Sieve is the fastest factorization algorithm we know of for integers of around
$\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.

The Quadratic Sieve

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

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

$$ \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)$ and $F(25)$ are $11$-smooth, however, we notice that $F(23)$ is the product of small primes with even powers modulo $443$.

$$ \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=23$ and $b=6$, which has a high probability of yielding a non-trivial factor of $493$:

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

Therefore, by way of quadratic sieve, we get that $17$ and $29$ are non-trivial factors of $493$.

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