O5a — Deterministic polynomial-time integer factorization

O5a — Deterministic polynomial-time integer factorization

Definitions and mathematical statement

The binary length of $N\ge2$ is $\ell(N)=\lfloor\log_2N\rfloor+1$. A nontrivial factor is an integer $d$ with $1<d<N$ and $d\mid N$. Ask whether there exist a deterministic classical algorithm $A$ and constants $C,k$ such that \[ \forall N\text{ composite},\qquad A(N)=d\text{ a nontrivial factor},\qquad T_A(N)\le C\ell(N)^k. \] The promise is compositeness; the running-time bound is in the bit length, not in the value of $N$.

Formulation and concept references: [S1].

Short English statement

Is there a deterministic classical method that factors every composite integer in time polynomial in its number of binary digits?

Research attempt

Scope and checked algorithmic context.

The input is promised composite, and the requested output is one proper divisor. Running time means bit operations in $\ell=\ell(N)$; a loop of length $N^{1/5}$ remains exponential in this parameter. An established deterministic result of Harvey--Hittmeir [E1] factors $N$ in $O(N^{1/5}\log^{16/5}N/(\log\log N)^{3/5})$ bit operations. It is substantially faster than trial division, but does not meet this target. Their 2026 manuscript [E2] improves the auxiliary problem of finding large-order elements; its stated alternatives include returning an element, so it is not a polynomial-time factorization theorem. No completeness claim about all current algorithms is needed here.

The chosen route examines modular square roots. Jeřábek [E3], the author manuscript of [S1], studies reductions involving factoring and square-root search, carefully distinguishing randomized reductions from deterministic ones. We give the elementary fiber calculation behind this connection, then test the tempting derandomization by a short fixed list of inputs. The calculation is classical; its purpose here is to expose the exact unsupplied algorithmic step rather than rebrand a reduction as a factorization algorithm. The conditional claims in catalogue source [S2] are not assumed.

Elementary preprocessing is genuinely polynomial.

If $N$ is even, return $2$. Detect perfect powers by trying each integer $2\le k\le\ell$ and computing the integer $k$th root by binary search, with exact exponentiation and comparison to $N$. Intermediate products may be capped as soon as they exceed $N$, so the bit lengths remain $O(\ell)$. There are $O(\ell)$ exponents, $O(\ell)$ search steps per exponent, and polynomially many bit operations per step. If $N=a^k$, $a>1$, return $a$. This includes odd prime powers without needing to recognize their prime base. The unhandled promised inputs are odd and have at least two distinct prime factors.

Write their unknown factorization, for analysis only, as $N=\prod_{i=1}^r p_i^{e_i}$, with $r\ge2$. This notation does not give the algorithm access to the factors. Let $U_N=(\mathbb Z/N\mathbb Z)^\times$ and let $Q_N$ be the image of its squaring map. A hypothetical oracle $F_N$ takes $u\in Q_N$ and returns any $v$ satisfying $v^2\equiv u\pmod N$. Because $u$ is a unit, its returned root is automatically a unit. The oracle is not presumed to return a random root or a preferred CRT sign.

Exact root fibers and extraction probability.

Lemma 17.1. Every $u\in Q_N$ has exactly $2^r$ square roots modulo $N$. For a fixed root $v$, exactly two roots $a$ fail to give a proper factor through $\gcd(a-v,N)$.

Proof. For an odd prime power $p^e$, a root $w$ of $w^2=1$ satisfies $p^e\mid(w-1)(w+1)$. Since $\gcd(w-1,w+1)$ divides two, the full prime power divides precisely one factor. Thus $w\equiv1$ or $-1$ modulo $p^e$. Multiplication by any fixed root of $u$ bijects its roots with roots of one. The Chinese remainder theorem therefore gives $2^r$ roots, one for each independent local sign.

If $a$ uses the same sign as $v$ at every prime power, then $a=v$ modulo $N$ and the gcd is $N$. If every sign is opposite, then $a=-v$ and the gcd is one, since $2v$ is a unit. Any mixed sign pattern makes the gcd the product of a nonempty proper subset of the prime-power factors. This is a proper divisor, and there are exactly $2^r-2$ such patterns.$\square$

Choose $a$ uniformly in $U_N$ and query $F_N(a^2)$. Conditional on the square $u=a^2$, the element $a$ is uniform in its $2^r$-element fiber. The oracle's chosen root depends on $u$, not on which preimage was sampled. Hence the success probability is exactly \begin{equation}\label{wsref-0-72-61-3a-31-37-3a-70-72-6f-62-61-62-69-6c-69-74-79} 1-2^{1-r}\ge\tfrac12. \end{equation} This remains true for any fixed deterministic selection of one root per square. If the oracle itself is randomized independently of the sampled preimage, condition on its output and obtain the same result.

An implementable sampler need not already know $U_N$. Sample uniformly from $1,\ldots,N-1$ and compute $g=\gcd(a,N)$. If $g>1$, it is already proper and succeeds. Otherwise the conditional distribution is uniform on $U_N$ and the lemma applies. Uniform bounded-integer sampling by rejection uses expected $O(\ell)$ random bits. Thus a polynomial-time square-root oracle would yield a randomized expected-polynomial-time factorization algorithm, with failure probability at most $2^{-t}$ after $t$ independent trials. Every reported factor is checked by exact division. This is not the deterministic worst-case bound requested.

Attempted derandomization and an exact obstruction.

A natural proposal is to replace the random $a$ by the first $\operatorname{poly}(\ell)$ integers, or another short deterministic list $H\subseteq U_N$. A success proportion of one half on the whole unit group does not imply that this particular list meets the successful half. Here the possible obstruction can be characterized exactly.

Lemma 17.2. There exists a valid root selector $F_N$ for which every test $a\in H$ fails if and only if, in each squaring fiber, the elements of $H$ lie in a single pair $\{b,-b\}$.

Proof. If that condition holds, for each fiber meeting $H$ select one member $b$ of its represented sign pair as the oracle output. Then all tested preimages equal $b$ or $-b$, and Lemma 17.1 says they fail. Choose any root on unqueried fibers to complete a valid selector. Conversely, if a fiber contains tested elements $a,b$ with $a\not\equiv\pm b$, no selected root can have both of them in its single exceptional sign pair. At least one query succeeds.$\square$

In fact, in the latter case the oracle is unnecessary: $a^2\equiv b^2\pmod N$ and $a\not\equiv\pm b$ already imply that $\gcd(a-b,N)$ is a proper divisor by the same local-sign argument. Consequently a short list guaranteed to defeat every root selector must already contain a useful congruence of squares. Producing such lists deterministically in polynomial time would itself solve the remaining factoring instances. The random reduction has not made that construction automatic.

The obstruction also applies to a finite adaptive transcript: when a previously unseen square is queried, an adversary can return the supplied preimage; when a previously queried square recurs in the same sign pair, the old response still causes failure. A new sign pair exposes precisely the factor-producing collision. This adversary can be extended to a valid selector after the transcript. Its implementation need not be efficient, so this is not a complexity lower bound against efficient root algorithms, nor does it exclude exploiting the structure of a specific algorithm. It isolates the defect in an oracle-independent derandomization based only on the success fraction.

A concrete failed list and a successful collision.

For $N=77$, the squares of $1,2,3,4,5,6$ are distinct modulo $77$, and all six inputs are units. A valid selector may return the respective input on those six squares; all six gcd tests then fail. Nevertheless there are four roots of one, $1,34,43,76$, and the mixed roots immediately yield $\gcd(34-1,77)=11$ and $\gcd(34+1,77)=7$. The roots exist in abundance relative to the two trivial choices, but their existence does not tell the deterministic procedure where to find one. This small example illustrates the logical failure of the proposed list argument, not an asymptotic hard instance: trial division already factors $77$ quickly.

One can also defeat a proposed use of generic collision finding. The squaring map has $\varphi(N)/2^r$ images, and evaluating it is cheap. Enumerating enough preimages to force a collision by the pigeonhole principle can still require exponentially many in $\ell$. Moreover the automatic collision $a,-a$ gives no factor. A collision theorem must control both its search cost and its local sign pattern. Calling a collision algorithm polynomial in $N$, or counting arithmetic operations while allowing exponentially long integers, would not meet the stated bit-complexity target.

Verification and edge cases.

The local script enumerates every unit and every squaring fiber for $N=15,45,77,105,315,1001$. For the selector choosing the smallest root, the exact success counts are \[ \begin{array}{r|r|r|r} N&r&\varphi(N)&\text{successful units}\\\hline 15&2&8&4\\45&2&24&12\\77&2&60&30\\ 105&3&48&36\\315&3&144&108\\1001&3&720&540 \end{array} \] The repeated-prime cases $45$ and $315$ check that the lemma uses distinct prime factors, not the total number counted with multiplicity. For every unit it verifies both the gcd criterion and the exact fraction in (ra:17:probability). The table-building oracle is implemented by exhaustive enumeration and has no claimed efficient running time. The script separately verifies the six-query failure setup for $77$. These are exact integer calculations, stored in checks.py and results.json under _Local/top_problems/continuation_15_25_2026_09_27/analytic/.

Even moduli were removed before the odd-prime-power argument. A pure prime power would have $r=1$ and success probability zero, which is why the perfect-power step is essential. On a prime input no proper divisor exists; the catalogue promises compositeness, and no total running-time claim on off-promise inputs is silently used. On the actual promised inputs, gcds, modular squaring, and output verification are polynomial; the missing operations are finding roots and removing randomness.

Remaining gap and outcome.

The fully proved result is the exact fiber reduction and its sharp failure condition for a deterministic test set. A complete solution along this route needs an actual deterministic polynomial-time root procedure together with a polynomial-time way to force a mixed-sign collision, or a different direct divisor construction. Neither is provided. An impossibility claim would need a lower bound against all deterministic algorithms, far beyond the limited oracle observation.

Outcome: UNRESOLVED. The randomized reduction and the oracle stress test are justified; no deterministic polynomial-time factoring algorithm or superpolynomial lower bound has been obtained. The process combined direct proof, primary-source checking, and exact finite tests; the results are not a claim of historical novelty or external certification.

Sources

• S1 Integer factoring and modular square roots. https://www.sciencedirect.com/science/article/pii/S0022000015000768. Formulation source.
• S2 A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization — Chris Umans and Siki Wang $2025$. https://arxiv.org/abs/2511.10851. Further reference; not a proof endorsement.
• S3 Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks — Marshall, Aaronson and Dunjko, CCC 2025. https://drops.dagstuhl.de/storage/00lipics/lipics-vol339-ccc2025/LIPIcs.CCC.2025.5/LIPIcs.CCC.2025.5.pdf. Further reference; not a proof endorsement.

• E1 David Harvey and Markus Hittmeir, A log-log speedup for exponent one-fifth deterministic integer factorisation, Mathematics of Computation 91 $2022$, 1367--1379; arXiv:2105.11105. https://arxiv.org/abs/2105.11105. Primary research reference for a proved deterministic bit-complexity bound, which is exponential in input length. Consulted 27 September 2026.
• E2 David Harvey and Markus Hittmeir, Deterministic methods for finding elements of large multiplicative order, arXiv:2601.11131v2 (5 June 2026). https://arxiv.org/abs/2601.11131v2. Recent manuscript: auxiliary order-search result, not a claimed polynomial-time factoring algorithm; not used in the proofs here. Consulted 27 September 2026.
• E3 Emil Jeřábek, Integer factoring and modular square roots, arXiv:1207.5220v3 (28 July 2015), author manuscript of [S1]. https://arxiv.org/pdf/1207.5220v3. Primary source on factoring and square-root search reductions; the elementary fiber reduction is proved explicitly above. Consulted 27 September 2026.

O5a — Deterministic polynomial-time integer factorization

Definitions and mathematical statement

The binary length of $N\ge2$ is $\ell(N)=\lfloor\log_2N\rfloor+1$. A nontrivial factor is an integer $d$ with $1<d<N$ and $d\mid N$. Ask whether there exist a deterministic classical algorithm $A$ and constants $C,k$ such that \[ \forall N\text{ composite},\qquad A(N)=d\text{ a nontrivial factor},\qquad T_A(N)\le C\ell(N)^k. \] The promise is compositeness; the running-time bound is in the bit length, not in the value of $N$.

Formulation and concept references: [S1].

Short English statement

Is there a deterministic classical method that factors every composite integer in time polynomial in its number of binary digits?

Research attempt

Current frontier.

Research check: 27 September 2026. Harvey's deterministic algorithm has an exponent $1/5$ in the integer's value, up to logarithmic factors, rather than polynomial complexity in its bit length. [E1]. Umans--Wang's November 2025 manuscript proposes a number-theoretic hypothesis that could lower this exponent to $1/6$; it does not claim the polynomial-time algorithm asked for here. [S2]. The research below isolates two distinct obstructions in an order-based route: computing an exponent and deterministically finding a base that separates prime-power components.

Attack route.

Near-square search, smooth-order methods, and modular-square-root methods all find factors on structured inputs. A global solution needs a uniform coverage theorem for all composites. We investigate a modular-exponent certificate because its verification and its failure mechanism can both be written exactly. We also compare it with a geometric near-square criterion, rather than assuming that random-base success derandomizes.

Attempt: factoring with a supplied exponent.

Let $N$ be odd, with at least two distinct prime divisors, and suppose a positive integer $M$ divisible by the Carmichael exponent $\lambda(N)$ is supplied, with bit length polynomial in $\log N$. Write $M=2^su$, $u$ odd. For any base $a$, first compute $\gcd(a,N)$. A proper gcd is already a factor. For a unit, compute \[ b_0=a^u\pmod N,\qquad b_{j+1}=b_j^2\pmod N, \qquad 0\leq j<s. \tag{17.1} \] Test all $\gcd(b_j-1,N)$. These computations take polynomial time in $\log N+\log M$ by binary exponentiation and the Euclidean algorithm.

To characterize success, factor $N=\prod_{i=1}^r p_i^{e_i}$ only for the analysis, not as an algorithmic subroutine. Put $t_i=v_2(p_i-1)$ and $v_i=v_2(\operatorname{ord}_{p_i^{e_i}}(a))$. Since $u$ removes the odd part of every component order, $b_j\equiv1\pmod{p_i^{e_i}}$ exactly when $v_i\leq j$. If the $v_i$ are not all equal, choosing $j$ between their minimum and maximum yields a nontrivial gcd in $17.1$. Conversely if all are equal, the chain simultaneously becomes one in every component and none of these gcds is proper. To exclude a partial prime-power gcd, note that each $b_j$ has two-power order: reduction from units modulo $p_i^{e_i}$ to units modulo $p_i$ has an odd-order kernel, so a nonidentity element of this two-primary subgroup cannot reduce to one. Thus this algorithm succeeds on a unit if and only if its component two-adic order valuations differ.

For a uniformly random unit, the CRT makes the components independent. The cyclic group of units modulo an odd prime power has two-primary part of order $2^{t_i}$. Consequently \[ \Pr(v_i=0)=2^{-t_i},\qquad \Pr(v_i=j)=2^{j-1-t_i}\quad(1\leq j\leq t_i). \tag{17.2} \] Each atom is at most $1/2$. For $r\geq2$, \[ \Pr(\hbox{failure}\mid a\text{ a unit}) =\sum_{j\geq0}\prod_{i=1}^r\Pr(v_i=j)\leq\frac12. \tag{17.3} \] Indeed, bound one of the first two factors by $1/2$, sum the other, and bound all remaining factors by one. Sampling from $1,\ldots,N-1$ is also safe: a nonunit has a proper gcd immediately, so overall success is at least $1/2$. The argument establishes a randomized algorithm given $M$. It establishes neither a deterministic base choice nor a way to compute $M$. The order/square-root mechanism is standard; the displayed probability calculation is supplied here in full. [E2].

Attempt: the exact deterministic package still missing.

A sufficient deterministic package would provide, for every such $N$, in time polynomial in $\log N$, an exponent $M$ as above and a list $\mathcal A_N$ of polynomially many bases containing either a nonunit with proper gcd or a unit whose valuations $v_i$ differ. Equations $17.1$--$17.3$ prove sufficiency, but a density lower bound does not construct this list: the successful set depends on the unknown factors. Trying the first $\operatorname{poly}(\log N)$ integers is an additional number-theoretic claim, not a consequence of $17.3$.

The input exceptions do not create a loophole. Even $N$ is immediate. Perfect powers can be recognized deterministically by testing all integer exponents $2\leq e\leq\lfloor\log_2N\rfloor$ and computing integer $e$-th roots by binary search; successful roots provide a factor. An odd composite that is not a perfect power has at least two distinct prime divisors, so the proposed package would cover all remaining inputs. Computing the exponents and a hitting list uniformly is precisely the unproved part of this attack.

Attempt: comparison with near-square search.

For an odd semiprime $N=pq$, $p\leq q$, Fermat's method tests integers $a\geq\lceil\sqrt N\rceil$ until $a^2-N=b^2$. The pair \[ a_*=(p+q)/2,\qquad b_*=(q-p)/2 \] works. The number of candidates through this pair is at most \[ 1+a_*-\sqrt N =1+\frac{(\sqrt q-\sqrt p)^2}{2} =1+\frac{(q-p)^2}{2(\sqrt q+\sqrt p)^2}. \tag{17.4} \] All square and square-root tests have polynomial bit cost. Thus $q-p\leq N^{1/4}(\log N)^C$ gives polynomial time for fixed $C$, since $(\sqrt q+\sqrt p)^2\geq4\sqrt N$. This is a proven special-case criterion, not a generic factoring estimate. With very unequal primes, $17.4$ can be exponential in $\log N$. Restricting attention to balanced semiprimes would silently weaken the target, and balancedness alone still does not give the $N^{1/4}$ difference bound.

Stress test.

An exponent can be short without being efficiently obtainable: $\lambda(N)$ itself has $O(\log N)$ bits. Using its existence as though it were computed is invalid. The easily computable integer $N!$ is a multiple of the needed orders but has exponentially many bits in the input length; it cannot be inserted as a free certificate. All bounds above distinguish bit cost from arithmetic-operation count. The random unit calculation is checked on small composites in the supplied code, but those tests cannot certify a polynomial-size deterministic hitting set for every input. A polynomial-time solution would not by itself imply $\mathsf P=\mathsf{NP}$, and a negative deterministic result would not by itself give the randomized lower bound needed in UnsolvedMath problem 30006683.

Outcome.

Outcome: Exploratory approach with unresolved gap. The attempt proves a complete success criterion and probability bound for an exponent-assisted algorithm, as well as a uniform near-square special case. It identifies exactly what a deterministic extension requires. Neither efficient exponent production nor the necessary deterministic coverage lemma is established. These auxiliary facts are not claimed to be historically novel, and no general factoring complexity conclusion is asserted.

Sources

• S1 Integer factoring and modular square roots. https://www.sciencedirect.com/science/article/pii/S0022000015000768. Catalogue formulation source.
• S2 A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization — Chris Umans and Siki Wang $2025$. https://arxiv.org/abs/2511.10851. Catalogue research/status reference; not a proof endorsement.
• S3 Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks — Marshall, Aaronson and Dunjko, CCC 2025. https://drops.dagstuhl.de/storage/00lipics/lipics-vol339-ccc2025/LIPIcs.CCC.2025.5/LIPIcs.CCC.2025.5.pdf. Catalogue research/status reference; not a proof endorsement.
• E1 David Harvey, An exponent one-fifth algorithm for deterministic integer factorisation, arXiv:2010.05450 $2020$, main theorem. https://arxiv.org/abs/2010.05450. Added research source. Deterministic value-exponent bound, not a polynomial bit-time algorithm. Consulted 27 September 2026.
• E2 Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing 26$5$ $1997$, 1484--1509; arXiv:quant-ph/9508027. https://arxiv.org/abs/quant-ph/9508027. Added research source. Factoring through order and nontrivial square-root information; the exponent-assisted classical calculation is proved separately. Consulted 27 September 2026.