gpt 6 astra pro attempt on Math-122

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.