A log-log speedup for exponent one-fifth deterministic integer factorisation

This is exactly [Har20, Lem. 2.3]; the proof depends on a standard application of a product tree. By “compute a polynomial” we mean compute a list of its coefficients. ∎

This is exactly [Har20, Lem. 2.4]. The proof relies on Bluestein’s algorithm [Blu70], which saves a logarithmic factor over a general multipoint evaluation. ∎

This is a trivial modification of [Har20, Lem. 3.1]. The proof depends on observing that $aq$ and $bp$ must be roots of the polynomial $y^{2}-uy+abN$. ∎

This is exactly [Hit18, Thm. 6.3]. Briefly, the idea is to attempt to compute orders of various $\alpha\in\mathbb{Z}_{N}^{*}$ via the standard babystep-giantstep procedure. If we fail to compute $\operatorname{ord}_{N}(\alpha)$, then the order must be large and we are done. If we succeed in computing $k\coloneqq\operatorname{ord}_{N}(\alpha)$, then we try to find a factor of $N$ via $\gcd(N,\alpha^{k/r}-1)$ for each prime divisor $r$ of $k$. If this fails, then we know that $k\mid{p-1}$ for every prime divisor $p$ of $N$. Repeating this process for various $\alpha$, we either find an element of large order, or obtain enough information about the factorisation of $p-1$ for $p\mid N$ to make it feasible to factor $N$ directly. For details, see [Hit18]. ∎

See Theorem 6.9 and Theorem 2.7(e) in [MV07]. The first statement is a form of the Prime Number Theorem, and the second statement is one of Mertens’ theorems. ∎

We may find a nonzero vector $w\in L$ of minimal norm by applying the classical Lagrange–Gauss reduction algorithm to the input basis (see [Gal12, Chap. 17]). According to [Gal12, Thm. 17.1.10], this runs in time $O(\log^{3}B)$. (The reduction algorithm is essentially a special case of LLL: the basic idea is to repeatedly subtract a suitable integer multiple of the shorter vector from the longer vector, until no further progress can be made in reducing the norms.) This vector satisfies $\lVert w\rVert^{2}\leqslant\gamma_{2}\det L$ where $\gamma_{2}=2/\sqrt{3}$ is the Hermite constant for rank-$2$ lattices (see [Gal12, Defn. 16.2.7]). Since $\gamma_{2}^{1/2}=1.074\ldots<2$ we are done. ∎

Assume that the input parameters $N$, $m_{0}$, $\sigma_{0}$, $m$ and $\sigma$ are as described above. Assume also that $N=pq$ is a semiprime satisfying (3.1) and (3.2).

Let $t_{0}\coloneqq p/\sigma_{0}-1$ so that $p=\sigma_{0}(1+t_{0})$. Then $0\leqslant t_{0}<1/m_{0}\leqslant 1$, so

for some $\delta\in[0,1)$. For any pair of integers $(a,b)$, it then follows that

Similarly, let $t\coloneqq p/\sigma-1$, so that $p=\sigma(1+t)$. Then $t$ is a rational number that is $m$-integral (i.e., its denominator is coprime to $m$), and $t\equiv 0\pmod{m}$. Thus

and for any pair of integers $(a,b)$ we obtain

This last congruence implies that (3.4) holds for any $(a,b)$ that satisfies

If $(a,b)$ additionally satisfies the inequalities

then (3.5) implies that (3.3) holds. We are left with showing how to compute a pair $(a,b)\neq(0,0)$ satisfying both (3.6) and (3.7). (The point is that both of these conditions are independent of $p$.)

The congruence (3.6) is equivalent to $b\equiv\gamma a\pmod{m}$, where $\gamma$ is the unique integer in $[0,m)$ congruent to $N/\sigma^{2}$ modulo $m$. Thus the solutions $(a,b)\in\mathbb{Z}^{2}$ to (3.6) form a lattice $L=\langle u,v\rangle$, where $u\coloneqq(1,\gamma)$ and $v\coloneqq(0,m)$. Our goal is to find a nonzero vector $(a,b)\in L$ that lies in the parallelogram defined by (3.7).

To achieve this, it is convenient to introduce the linear change of variables

In the $(c,d)$-coordinates the inequalities (3.7) become simply

i.e., the parallelogram becomes a square. Moreover, in the $(c,d)$-coordinates the lattice $L$ gets mapped to the lattice $L^{\prime}\coloneqq\langle u^{\prime},v^{\prime}\rangle$ where

The determinant of $L^{\prime}$ is $Nmm_{0}\sigma_{0}^{2}$. We may therefore apply Lemma 3.1 to the basis $u^{\prime},v^{\prime}$ to find a nonzero pair $(c,d)\in L^{\prime}$ satisfying (3.8).

The hypothesis $m_{0},\sigma_{0},m=O(N)$ implies that $\lVert u^{\prime}\rVert,\lVert v^{\prime}\rVert=O(N^{4})$, so the cost of applying Lemma 3.1 is $O(\lg^{3}N)$. The cost of the remaining arithmetic (computing $\gamma$, $u^{\prime}$ and $v^{\prime}$, and recovering $(a,b)$ from $(c,d)$) is bounded by $(\lg N)^{1+o(1)}$. Finally, (3.7) implies that $|a|\leqslant 2N^{-1/2}m^{1/2}m_{0}^{1/2}=O(N^{1/2})$ and $|b|\leqslant 2N^{1/2}m^{1/2}+|a|N=O(N^{3/2})$. ∎

This is exactly Proposition 4.1 in [Har20]. ∎

We first prove correctness. Suppose that $N=pq$ is semiprime, with $p<q$. We must show that in Steps 1–13 the algorithm succeeds in finding $p$ and $q$.

Consider the loop in Steps 1–3. Since we have assumed that $\operatorname{ord}_{N}(\beta^{m^{2}})\geqslant 2\lambda+1$, in this loop we either find a factor of $N$, or prove that both $\operatorname{ord}_{p}(\beta^{m^{2}})\geqslant 2\lambda+1$ and $\operatorname{ord}_{q}(\beta^{m^{2}})\geqslant 2\lambda+1$. For the remainder of the proof, we will assume the latter.

We next consider the giantsteps. The block in Steps 8–10 is executed for various pairs $(\sigma,\sigma_{0})$. We claim that (3.2) holds for exactly one such $\sigma$, and that (3.1) holds for exactly one such $\sigma_{0}$. For (3.2) this is clear, as $p$ is coprime to $m$ by hypothesis, so there is exactly one $\sigma$ visited by the outer loop such that $\gcd(\sigma,m)=1$ and $p\equiv\sigma\pmod{m}$. For the inner loop, observe that $\sigma_{0}$ strictly increases on each iteration (in Step 11), so the loop certainly terminates. For any $\sigma_{0}$ visited in the loop, write $\sigma^{\prime}_{0}\coloneqq\lceil(1+1/m_{0})\sigma_{0}\rceil$ for the value of $\sigma_{0}$ at the next iteration. Since $p<N^{1/2}$, on some iteration we must have $\sigma_{0}\leqslant p<\sigma^{\prime}_{0}$; in fact, this occurs for precisely one value of $\sigma_{0}$ because the successive intervals $[\sigma_{0},\sigma^{\prime}_{0})$ are disjoint. Moreover, since $p$ is an integer, the condition $\sigma_{0}\leqslant p<\sigma^{\prime}_{0}$ is equivalent to $\sigma_{0}\leqslant p<(1+1/m_{0})\sigma_{0}$, i.e., to (3.1). Therefore (3.1) holds for exactly one $\sigma_{0}$ as claimed.

Let $(\bar{\sigma},\bar{\sigma}_{0})$ be the pair for which (3.1) and (3.2) hold, and consider the corresponding coefficients $\bar{a}\coloneqq a_{\bar{\sigma},\bar{\sigma}_{0}}$ and $\bar{b}\coloneqq b_{\bar{\sigma},\bar{\sigma}_{0}}$ computed in Step 8. According to Proposition 3.3, the linear combination $\bar{a}q+\bar{b}p$ satisfies (3.3) and (3.4) for $(\bar{\sigma},\bar{\sigma}_{0})$. Let $\tau$ and $\tau_{0}$ be as defined in Step 9. From (3.4) we find that

and (3.3) yields

so

This implies that $\tau_{0}-\lambda\leqslant\lfloor(\bar{a}q+\bar{b}p)/m^{2}\rfloor\leqslant\tau_{0}+\lambda$, i.e., that $\lfloor(\bar{a}q+\bar{b}p)/m^{2}\rfloor=\tau_{0}-\lambda+\bar{i}$ for some $0\leqslant\bar{i}\leqslant 2\lambda$. Inserting this into (4.4), we find that

where $\bar{j}\coloneqq j_{\bar{\sigma},\bar{\sigma}_{0}}$ is as defined in Step 9. Now, the congruence $p\equiv 1\pmod{p-1}$ implies that $\bar{a}q+\bar{b}p\equiv\bar{a}N+\bar{b}\pmod{p-1}$, so Fermat’s little theorem yields

We conclude that there must be a collision modulo $p$ between the babysteps computed in Step 2 and the giantsteps computed in Step 10, namely

In Step 12, we attempt to find the solution $(\bar{i},\bar{\sigma},\bar{\sigma}_{0})$ to (4.5), by finding all solutions to the stronger congruence (4.1), which is a congruence modulo $N$ rather than modulo $p$. Let $(i,\sigma,\sigma_{0})$ be one of the solutions found in Step 12. If it is equal to $(\bar{i},\bar{\sigma},\bar{\sigma}_{0})$, then the corresponding $u$ defined in (4.2) will be equal to $m^{2}\bar{i}+\bar{j}=\bar{a}q+\bar{b}p$, and the factors $p$ and $q$ will be found via Lemma 2.4. Now suppose instead that $(i,\sigma,\sigma_{0})\neq(\bar{i},\bar{\sigma},\bar{\sigma}_{0})$. We claim then that $(\sigma,\sigma_{0})\neq(\bar{\sigma},\bar{\sigma}_{0})$. Indeed, if $(\sigma,\sigma_{0})=(\bar{\sigma},\bar{\sigma}_{0})$, then we would have

which implies that $\bar{i}=i$ due to the fact that $0\leqslant i,\bar{i}\leqslant 2\lambda$ and $\operatorname{ord}_{p}(\beta^{m^{2}})\geqslant 2\lambda+1$. This establishes the claim, and consequently the giantstep $v_{\bar{\sigma},\bar{\sigma}_{0}}$ remains among the candidates in the list $v_{1},\ldots,v_{n}$ constructed in Step 13.

Finally we consider Step 13. The procedure in Step 12 ensures that all preconditions for Algorithm 4.1 are met. In addition, we have seen in the last paragraph that one of $v_{1},\ldots,v_{n}$ is equal to $v_{\bar{\sigma},\bar{\sigma}_{0}}$. Hence, Algorithm 4.1 will succeed in finding a nontrivial factor of $N$.

If $N$ is prime, then Steps 1–13 will fail to find a nontrivial factor, and the algorithm will correctly return “$N$ is prime” in Step 14.

We now analyse the runtime complexity. To prepare for the loop in Steps 1–3 we first compute $\beta^{m^{2}}\pmod{N}$; the cost of this step is

The loop itself computes at most $\kappa\coloneqq 2\lambda+1$ products modulo $N$ and $\kappa$ GCDs of integers bounded by $N$, whose total cost is

In Step 5 we compute $m$ GCDs of integers bounded by $m=O(N)$, which costs

Now consider the inner loop over $\sigma_{0}$. The ratio between values of $\sigma_{0}$ on successive iterations is at least $1+1/m_{0}$, so for each $\sigma$ the number of iterations of the inner loop over $\sigma_{0}$ is at most

The number of $\sigma$ considered is $\phi(m)$, so the block in Steps 8–11 executes altogether