Factoring integers in time, exponential in $\sqrt{n\log n}$

J. Dixon was the first to show that $n$-digit integers can be factored in $e^{c\sqrt{n\log n}}$ steps. Let $X$ be an $n$-digit integer ( $X\approx 2^n$) which we want to factor.

Definition 0.6   We say that $z$ is a $v$-smooth integer if all primes dividing $z$ are $\le v$.

Suppose we can find $a,b$ such that $a^2 \equiv b^2 \pmod X$ and $a\not\equiv \pm b \pmod X$. Then $X$ divides $(a+b)(a-b)$ and $a+b$ splits $X$.

How do we find such $a$ and $b$? Let $v$ be a threshold number $v =2^{\sqrt{n \log n}}$ and let $P = \{p~{\rm is~a~prime}~\colon~ p\le v\}$. Let $r_i\in\{1,\dots,X\}$ be a random number. Let $s_i = (r_i^2 \bmod X)$. If $s_i$ is not $v$-smooth, discard it and try again. Let $N=\vert P\vert$. Keep generating the $r_i$ until $N+1$ smooth numbers $s_i$ are found.

Suppose $s_i = p_1^{\alpha_{i_1}}\dots p_N^{\alpha_{i_N}} \pmod X$ where $P = \{p_1,\dots,p_N\}$.

Consider the matrix

$$\begin{pmatrix} \alpha_{1,1} & \alpha... ...ots \\ \alpha_{N+1,1} & \alpha_{N+1,2} & \dots & \alpha_{N+1,N} \end{pmatrix}$$

Since this matrix is $(N+1)\times N$, its rows are linearly dependent $\pmod 2$. Therefore there exists a nonempty set $S\subseteq\{1,\dots,N\}$ such that $(\forall j) (\sum_{i\in S}\alpha_{ij} = 2\beta_j)$. Thus

$$\prod_{i\in S}r_i^2 \equiv \prod_{j=1}^N p_j^{2\beta_j} \pmod X$$

Let $a:=\prod_{i\in S}r_i \bmod X$ and $b:=\prod_{j=1}^N p_j^{\beta_j} \bmod X$. Now $a^2 \equiv b^2 \pmod X$.

There are two catches in this sketch. First, the smooth numbers have to happen sufficiently frequently. Second, the probability of $a\not\equiv \pm b \pmod X$ must be significant.

The second claim seems more plausible and can be proven by using a clever counting argument. Here we present intuition behind the first claim.

Let $\psi(X,v)$ be the number of $v$-smooth numbers less than $X$. Let $k=\sqrt{n/\log n}$, i.e. $v^k\approx X$. Clearly, $\psi(v^k,v)\geq \binom{\pi(v)}{k}>(\pi(v)/k)^k$ (the product of any $k$ primes $\le v$ is smooth). What is the probability that a random number is smooth?

$$\frac{\psi(v^k,v)}{v^k} \geq \left(\frac{\pi(v)}{k}\right)^k\frac... ...right)^{\sqrt{n/\log n}} = (c/n)^{\sqrt{n/\log n}} \geq c_1^{\sqrt{n \log n}}.$$

Thus, the expected number of trials to find a random smooth number is less than $(1/c_1)^{\sqrt{n\log n}}$. Note, however, that the $s_i$ are not generated uniformly at random, so the actual proof is necessarily more delicate. But it uses the same simple lower bound on $\psi(v^k,v)$.