\documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage{lmodern,microtype} \usepackage[a4paper,margin=1in]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{xcolor,xurl} \usepackage[colorlinks=true,allcolors=blue!45!black]{hyperref} \hypersetup{ pdftitle={An Improved Subexponential Bound for Deterministic Integer Factorization}, pdfauthor={Joseph M. Shunia}, pdfsubject={MSC 2020: 11Y05, 11Y16, 68Q25; integer factorization, exact counting, Boolean tensor networks} } \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \DeclareMathOperator{\Count}{Count} \setlength{\emergencystretch}{2em} \allowdisplaybreaks[2] \title{An Improved Subexponential Bound for\\ Deterministic Integer Factorization} \author{Joseph M. Shunia\thanks{Independent researcher, Ann Arbor, Michigan, United States. Email: \texttt{jshunia@gmail.com}.}} \date{October 30, 2026} \begin{document} \maketitle \begin{abstract} We prove that the complete prime factorization of an $n$-bit integer can be computed deterministically in time $2^{O(n/\sqrt{\log n})}$ and polynomial space. This establishes the bound conjectured by Rudich and Rousseau, sharpening their qualitative $N^{o(1)}$ result. The proof combines OpenAI's quantitative Boolean tensor-contraction theorem with the linear-size multiplication encoding of Akshima et al. The encoding permits exact counting of divisors with prescribed binary prefixes without loss in the exponent. The least prime factor is then recovered by successive prefix queries, and iteration yields the complete factorization within the same asymptotic bound. \end{abstract} \smallskip {\small \noindent\textit{2020 Mathematics Subject Classification.} Primary 11Y05; Secondary 11Y16, 68Q25.\par \noindent\textit{Key words and phrases.} Integer factorization, deterministic algorithms, subexponential time, exact counting, Boolean tensor networks.\par } \section{Introduction} Rudich and Rousseau~\cite{rudich-rousseau} obtained a deterministic algorithm for integer factorization with running time $N^{o(1)}$. They further conjectured that the running time can be bounded by \begin{equation}\label{eq:target} \exp\!\left(O\!\left( \frac{\log N}{\sqrt{\log\log N}}\right)\right). \end{equation} We prove this refinement by combining the quantitative contraction theorem of OpenAI~\cite{openai-eth} with the multiplication encoding of Akshima et al.~\cite{ecdl}. For $N\ge2$, write $n=\lfloor\log_2N\rfloor+1$ for its binary length. Running times are measured in bit operations, and space in bits. All logarithms are to base two; their base does not affect the asymptotic bounds. \begin{theorem}\label{thm:main} There is a uniform deterministic algorithm which computes the least prime factor and the complete prime factorization of every $n$-bit integer $N\ge2$ in time \[ 2^{O(n/\sqrt{\log n})} \] and space $n^{O(1)}$. \end{theorem} Since $n=\Theta(\log N)$, this is the bound in~\eqref{eq:target}, and hence proves Conjecture~1 of~\cite{rudich-rousseau}. The contribution is the quantitative estimate. The search reduction is the divisor-prefix procedure of Rudich and Rousseau: count divisors with a prescribed initial binary word, then recover the least prime factor one bit at a time. To retain the desired running time, however, the counting instances must have size linear in $n$. The multiplication network of Akshima et al. has $O(n)$ edges and maximum degree $O(n^{3/4})$. Fixing its product word to $N$ and restricting the leading bits of one factor preserves both bounds. OpenAI's contraction theorem, which allows degree $O(s^{9/10})$ on a network with $s$ edges, therefore evaluates each count in $2^{O(n/\sqrt{\log n})}$ time. Polynomially many such counts suffice for complete factorization. The inequalities between these size and degree bounds are what allow the conjectured rate to pass through the reduction unchanged. We recall the two results in the form needed here, then give the counting reduction and the factorization algorithm. We also record the integer-rounded version of the bound used in the formulation of the conjecture. \section{Boolean tensor networks}\label{sec:networks} A \emph{Boolean tensor network} consists of a finite undirected multigraph $G=(V,E)$ without self-loops and, at each vertex $v$, a predicate $P_v:\{0,1\}^{\deg(v)}\to\{0,1\}$. The edges incident to each vertex are ordered. Its contraction is \[ \Count(G)= \sum_{x\in\{0,1\}^{E}} \prod_{v\in V}P_v\bigl(x|_{E(v)}\bigr), \] where $x|_{E(v)}$ denotes the ordered tuple of incident edge bits. Thus the contraction counts the assignments satisfying all vertex predicates. The predicates are specified by algorithms for evaluating them, rather than by their full truth tables. The following form of OpenAI's contraction theorem is recorded in~\cite[Theorem 2]{ecdl}. \begin{theorem}[OpenAI {\cite[Theorem D.1]{openai-eth}}] \label{thm:contraction} Let $G$ be a Boolean tensor network with $s\ge2$ edges and maximum degree $O(s^{9/10})$. Suppose that the number of vertices and the total description length are polynomial in $s$, and that the vertex predicates are uniformly evaluable in polynomial time. Then $\Count(G)$ can be computed deterministically in time \[ 2^{O(s/\sqrt{\log s})} \] and polynomial space. The constants are uniform for fixed bounds on the degree, description length, and predicate evaluation time. \end{theorem} For completeness, we explain the specialization from the original statement; see also~\cite[Remark 1]{ecdl}. That statement requires a bipartite graph. Subdividing every edge by a vertex carrying the binary equality predicate produces such a graph, doubles the edge count, and preserves the contraction. The maximum degree becomes at most the larger of $2$ and the original degree. The original statement also computes over a finite coefficient ring. Taking $\mathbb Z/2^{s+1}\mathbb Z$ recovers the exact integer count, since \[ 0\le\Count(G)\le2^s<2^{s+1}. \] The required precision is linear in the network size, including after subdivision. These changes therefore preserve the asserted running time and space. To encode an arithmetic relation, one designates distinct \emph{interface edges} for its argument bits. An encoding is \emph{parsimonious} if each valid assignment to the interface extends to exactly one satisfying assignment on the remaining edges, and an invalid assignment has no such extension. \begin{theorem}[Akshima et al. {\cite[Theorem 3]{ecdl}}] \label{thm:multiplication} For every $d\ge1$, the relation $ab=z$, with $0\le a,b<2^d$ and $0\le z<2^{2d}$, has a parsimonious Boolean tensor-network encoding with fewer than $1100(d+1)$ edges and maximum degree less than $136(d+1)^{3/4}$. The network is uniformly constructible in polynomial time, and its vertex predicates are uniformly evaluable in polynomial time. \end{theorem} The construction in~\cite{ecdl} uses a two-stage Fourier-transform decomposition to obtain the linear edge bound. Canonical representations of the intermediate words ensure parsimony. We shall use both properties: the size bound controls the running time, while uniqueness of the auxiliary assignments identifies the contraction with the desired divisor count. \section{Divisor counts and factorization}\label{sec:factoring} Represent every integer in $[0,2^n)$ by a word of length $n$, allowing leading zeros. For a binary word $u$ of length at most $n$, let \begin{equation}\label{eq:prefixcount} C_N(u)=\#\{d: d\mid N,\ d\ge2, \text{the $n$-bit word for $d$ begins with $u$}\}. \end{equation} In particular, the empty word is a prefix of every divisor. \begin{lemma}\label{lem:counts} The count $C_N(u)$ can be computed deterministically in time $2^{O(n/\sqrt{\log n})}$ and polynomial space, uniformly in $N$ and $u$. \end{lemma} \begin{proof} Apply Theorem~\ref{thm:multiplication} with $d=n$. Fix the product word $z$ to the $2n$-bit representation of $N$, and fix the first $|u|$ bits of $a$ to $u$. Each fixed-bit condition can be conjoined to the predicate at one endpoint of its interface edge. This leaves the graph unchanged and preserves uniqueness of the auxiliary assignments. The modified predicates remain uniformly evaluable in polynomial time. The satisfying assignments now correspond bijectively to the positive divisors $a$ of $N$ whose $n$-bit representations begin with $u$. Indeed, each such divisor determines its unique cofactor $b=N/a$, and both are at most $N<2^n$. Parsimony gives exactly one extension to the remaining edges. Conversely, a satisfying assignment has $ab=N>0$ and therefore supplies such a divisor. To obtain $C_N(u)$, subtract $1$ from the contraction if $u$ is a prefix of the $n$-bit representation of $1$, and subtract $0$ otherwise. The network has $s=\Theta(n)$ edges: its $4n$ interface edges give the lower bound, and Theorem~\ref{thm:multiplication} gives the upper bound. Its maximum degree is $O(n^{3/4})=O(s^{3/4})$, which satisfies the hypothesis of Theorem~\ref{thm:contraction}. Its construction and description have polynomial size and cost. The contraction, and hence the required count, is therefore computed in time \[ 2^{O(s/\sqrt{\log s})}=2^{O(n/\sqrt{\log n})} \] and polynomial space. The count is at most $N$, so its binary representation requires only $O(n)$ bits. All bounds are uniform over the prefixes of length at most $n$. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:main}] Start with the empty word $u$. The invariant $C_N(u)>0$ holds initially because $N$ itself is counted. At each step, compute $C_N(u0)$, where juxtaposition denotes concatenation. Replace $u$ by $u0$ if the count is positive, and by $u1$ otherwise. Continue until $u$ has length $n$. For $|u|