Unconditional deterministic polynomial-time factorization of integers given Euler's totient function (Problem 1.1 of Hittmeir-Pomykała, 2020)

The classical reduction of integer factorization to computing Euler's totient function φ is deterministic and polynomial-time under the Extended Riemann Hypothesis (Miller 1976), and unconditional but randomized (Rabin 1980); its unconditional derandomization has been open for roughly five decades. Hittmeir and Pomykała (2020) isolate this as their Problem 1.1: does there exist a deterministic polynomial-time algorithm that factors an arbitrary integer $N\ge 2$ given only the value $\phi(N)$, or given the prime-power decomposition of $\phi(N)$? They prove that the decomposition oracle DecΦ suffices in deterministic polynomial time for all $N$ with $\omega(N)\le(\log N/\log 4)^{1/3}$ and for almost all $N$ with at most S distinct prime factors, and improve the subexponential reduction exponent to $2^{-1/3}$, yet their conclusion states Problem 1.1 wide open. The forward literature — Du-Volkovich's factor-3 approximation of ω(N) from a totient oracle, the lattice-based conditional algorithms of Morain-Renault-Smith, the elliptic-curve oracle analogue of Dąbrowski-Pomykała-Shparlinski, and the oracle-free deterministic factoring record of $N^{1/5+o(1)}$ — leaves the core question unresolved: no unconditional deterministic polynomial-time reduction of factoring to φ-computation is known, neither for all N nor for a positive-density set of N without an oracle.

Background

Integer factorization — computing the prime factorization of a given integer $N$ — is a central problem of algorithmic number theory and the security foundation of the RSA cryptosystem. Euler's totient function $\phi(N)$ counts the integers in $\{1,\dots,N\}$ coprime to $N$; if $N=p_1^{e_1}\cdots p_k^{e_k}$ is the prime factorization, then $\phi(N)=\prod_i p_i^{e_i-1}(p_i-1)$, and $\omega(N)$ denotes the number $k$ of distinct prime divisors. This formula shows that factoring yields $\phi(N)$ in deterministic polynomial time; the reverse direction is the subject of this problem. Two oracle models are used to phrase it. A $\Phi$-oracle returns the numerical value $\phi(m)$ for any queried integer $m$; the stronger oracle $\mathrm{Dec}\Phi$ returns the prime-power decomposition of $\phi(N)$ (equivalently, its complete prime factorization), and $\mathrm{Dec}\mathrm{Ord}$ analogously returns prime-power decompositions of multiplicative orders of elements of the unit group $\mathbb{Z}_N^*$ of the residue ring modulo $N$. For a semiprime $N=pq$ the value $\phi(N)$ already factors $N$ deterministically: $p+q=N-\phi(N)+1$, so $p$ and $q$ are the roots of the quadratic $x^2-(N-\phi(N)+1)x+N$, obtained by an exact integer square root of the perfect-square discriminant $(p-q)^2$. The difficulty begins at $\omega(N)\ge 3$, where the prime powers composing $\phi(N)$ must be matched against the unknown primes of $N$. The standard splitting mechanism is the Fermat-Euclid witness: an integer $b$ coprime to $N$ such that, for some divisor $s$ of the multiplicative order of $b$ modulo $N$, the greatest common divisor $\gcd(b^s-1,N)$ is a proper divisor of $N$. Writing a known multiple $M$ of the order — for instance $M=\phi(N)$ — as $M=2^t u$, one tests $\gcd(b^{2^i u}-1,N)$; this splits $N$ unless the 2-adic valuations $v_2(\cdot)$ (the exponent of the largest power of 2 dividing a number) of the orders of $b$ modulo the different prime divisors of $N$ all coincide. Miller (1976) proved that under the Extended Riemann Hypothesis (ERH — the Riemann hypothesis for Dirichlet $L$-functions, which yields polylogarithmic bounds for the least quadratic nonresidue modulo a prime, i.e. the least integer that is not a square modulo that prime) a small such witness always exists, so that factoring is deterministic polynomial-time reducible to computing $\phi$; Rabin (1980) obtained an unconditional reduction by randomizing the choice of $b$. Removing this randomness unconditionally has remained open since. Woll (1987) systematically studied reductions among such number-theoretic oracles; Landau (1988) proved that a $\Phi$-oracle suffices to compute the squarefree part of $N$ deterministically via factor refinement (iterative splitting of $N$ into pairwise coprime factors); Bach, Miller and Shallit (1986) treated the analogous oracle for the divisor-sum function $\sigma$.

Quantitative partial results accumulated before the source paper. Burthe (1997) proved that the least compositeness witness for $n$ — the smallest base $a$ for which $n$ fails the Miller–Rabin strong-pseudoprime test — is 2 on average, from which Źrałek (2010) deduced that for almost all $n$ the value $\phi(n)$ alone yields complete deterministic polynomial-time factorization — but with no explicit description of the exceptional set. Źrałek (2010) also identified explicit families of integers that are completely factorable in deterministic polynomial time from $\phi(n)$ (roughly, products of primes $p$ such that $p-1$ has only small prime factors, with at most two exceptions), and proved that iterating the $\Phi$ oracle $O(\ln n)$ times factors every $n$ in deterministic subexponential time $\exp((1+o(1))(\ln n)^{1/3}(\ln\ln n)^{2/3})$, i.e. $L_n(1/3)^{1+o(1)}$ in the $L$-notation $L_n(1/3)=\exp((\ln n)^{1/3}(\ln\ln n)^{2/3})$; a 2019 refinement of the underlying divisor-in-residue-class technique preserved this reduction shape. Durnoga and Pomykała (2017) proved, via large-sieve estimates (an analytic-number-theoretic technique bounding how many integers can simultaneously occupy prescribed residue classes) for compositeness witnesses, quantitative exceptional-set bounds (for odd squarefree integers) for deterministic factoring from a $\phi$-oracle. Morain, Renault and Smith (2018/2023) used LLL lattice basis reduction (the Lenstra–Lenstra–Lovász algorithm, which finds short vectors in a lattice and thence small roots of polynomial equations) to factor deterministically in polynomial time given $\phi(N)$ — or given order information of the kind used in quantum factoring — whenever the prime factors of $N$ satisfy relative-size conditions, for example squarefree $N$ having a prime factor exceeding $\sqrt{N}$. Hittmeir and Pomykała (2020), the source paper, proved that the $\mathrm{Dec}\Phi$ oracle yields a nontrivial factor of $N$ (a divisor $d$ with $1<d<N$) in deterministic time $O(\log^{S+6} N)$ whenever $\omega(N)\le S\le(\log N/\log 4)^{1/3}$; established almost-all counting theorems: for every fixed $s\ge 2$, all but $O(x/A(x))$ of the integers $N\le x$ with exactly $s$ (respectively at most $S$) distinct prime factors are nontrivially factorable in deterministic polynomial time with $\mathrm{Dec}\Phi$, where $A(x)$ is an explicit power of $x$; and improved the subexponential reduction exponent from $1$ to $2^{-1/3}$ with $O(\log N)$ oracle calls. Afterwards, Du and Volkovich (2021) gave the first efficient deterministic algorithm that, from a $\Phi$-oracle alone, approximates $\omega(N)$ within a factor of 3, and Ravi and Volkovich (2023) made the squarefree-part computation from a $\Phi$-oracle non-adaptive via a new characterization of factor refinement. In the oracle-free setting the best rigorous deterministic factoring algorithm remains of complexity $N^{1/5+o(1)}$ (Harvey and Hittmeir 2022, with 2026 preprints continuing the program), and the Adleman-McCurley open-problem lists (1987, 1994) already asked whether any set of integers of positive density can be factored in deterministic polynomial time — still unresolved, as is the elliptic-curve oracle analogue of Dąbrowski, Pomykała and Shparlinski (2023), who obtained almost-all (not all) results from point-count oracles.

Problem Statement

The problem is the unconditional derandomization of the classical reduction of factoring to totient computation, stated as Problem 1.1 in the source paper of Hittmeir and Pomykała (2020) and in the standard formulation of Morain-Renault-Smith: Primary question. Does there exist a deterministic algorithm which, given an arbitrary composite integer $N\ge 2$ together with (a) only the numerical value $\phi(N)$, or (b) the stronger information consisting of the prime-power decomposition of $\phi(N)$ (the $\mathrm{Dec}\Phi$ oracle), outputs a nontrivial factor of $N$ — a divisor $d$ with $1<d<N$ — in time polynomial in $\log N$, with no unproved hypothesis and no exceptional set? (If the algorithm has oracle access to $\Phi$ and can therefore query $\phi(m)$ for the cofactors arising along the way, recursively applying such a splitting algorithm yields the complete prime factorization; under input (a) as a single given value, the requested output is a nontrivial factor.) Variant (a) is the operative target: the prime-power decomposition of $\phi(N)$ determines the value $\phi(N)$, so an algorithm meeting the primary-question standard for input (a) also meets it for input (b), and a positive resolution is an algorithm for input (a) while a negative resolution is a proof that no deterministic algorithm succeeds for the value-only input (a). Three concrete open directions toward the same derandomization objective are discussed in the literature: (1) eliminating the exceptional set of the known $\mathrm{Dec}\Phi$-based almost-all algorithms; (2) matching the known $\mathrm{Dec}\Phi$-level performance using only the numerical value $\phi(N)$, including deciding whether $\omega(N)=k$ for fixed $k\ge 3$, which remains open (Du and Volkovich 2021); and (3) improving the exponent $2^{-1/3}$ of the subexponential reduction from factoring to $\Phi$-computation in $L_N(1/3)$-time, while bounding the number of oracle calls. The common objective uniting these targets is the removal of randomness and of the Extended Riemann Hypothesis from the totient-to-factoring reduction; a complete answer to the primary question — an algorithm with a correctness and runtime proof for every composite $N$, or a proof that no such algorithm exists — is the goal.

References

1. Markus Hittmeir and Jacek Pomykała, Deterministic Integer Factorization with Oracles for Euler's Totient Function, Fundamenta Informaticae 172(1) (2020) 39-51. DOI 10.3233/FI-2020-1891, https://doi.org/10.3233/FI-2020-1891
2. Yang Du and Ilya Volkovich, Approximating the Number of Prime Factors Given an Oracle to Euler's Totient Function, in: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021), LIPIcs 213, Schloss Dagstuhl (2021) 17:1-17:10. DOI 10.4230/LIPIcs.FSTTCS.2021.17, https://doi.org/10.4230/LIPIcs.FSTTCS.2021.17
3. François Morain, Guénaël Renault and Benjamin Smith, Deterministic factoring with oracles, Applicable Algebra in Engineering, Communication and Computing 34(4) (2023) 663-690. DOI 10.1007/s00200-021-00521-8, https://doi.org/10.1007/s00200-021-00521-8 (preprint arXiv:1802.08444, https://arxiv.org/abs/1802.08444)
4. Gary L. Miller, Riemann's Hypothesis and tests for primality, Journal of Computer and System Sciences 13(3) (1976) 300-317. DOI 10.1016/S0022-0000(76)80043-8, https://doi.org/10.1016/S0022-0000(76)80043-8
5. Michael O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12(1) (1980) 128-138. DOI 10.1016/0022-314X(80)90084-0, https://doi.org/10.1016/0022-314X(80)90084-0
6. Susan Landau, Some remarks on computing the square parts of integers, Information and Computation 78(3) (1988) 246-253. DOI 10.1016/0890-5401(88)90028-4, https://doi.org/10.1016/0890-5401(88)90028-4
7. Heather Woll, Reductions among number theoretic problems, Information and Computation 72(3) (1987) 167-179. DOI 10.1016/0890-5401(87)90030-7, https://doi.org/10.1016/0890-5401(87)90030-7
8. Eric Bach, Gary Miller and Jeffrey Shallit, Sums of Divisors, Perfect Numbers and Factoring, SIAM Journal on Computing 15(4) (1986) 1143-1154. DOI 10.1137/0215083, https://doi.org/10.1137/0215083
9. Ronald Joseph Burthe Jr., The average least witness is 2, Acta Arithmetica 80(4) (1997) 327-341. DOI 10.4064/aa-80-4-327-341, https://doi.org/10.4064/aa-80-4-327-341 (zbMATH 0874.11011)
10. Bartosz Źrałek, A deterministic version of Pollard's p-1 algorithm, Mathematics of Computation 79(269) (2010) 513-533. DOI 10.1090/S0025-5718-09-02262-5, https://doi.org/10.1090/S0025-5718-09-02262-5 (preprint arXiv:0707.4102, https://arxiv.org/abs/0707.4102)
11. Bartosz Źrałek, An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler's totient, Mathematics of Computation 88(317) (2019) 1261-1272. DOI 10.1090/mcom/3368, https://doi.org/10.1090/mcom/3368
12. Konrad Durnoga and Jacek Pomykała, Large Sieve, Miller-Rabin Compositeness Witnesses and Integer Factoring Problem, Fundamenta Informaticae 156(2) (2017) 179-185. DOI 10.3233/FI-2017-1603, https://doi.org/10.3233/FI-2017-1603
13. Leonard M. Adleman and Kevin S. McCurley, Open problems in number theoretic complexity, in: Discrete algorithms and complexity (Proceedings of the Japan-US Joint Seminar, Kyoto, 1986), Perspectives in Computing 15, Academic Press (1987) 237-262. zbMATH 0659.10002, https://zbmath.org/?q=an%3A0659.10002
14. Leonard M. Adleman and Kevin S. McCurley, Open problems in number theoretic complexity, II, in: Algorithmic Number Theory (ANTS-I), Lecture Notes in Computer Science 877, Springer (1994) 291-322. DOI 10.1007/3-540-58691-1_70, https://doi.org/10.1007/3-540-58691-1_70
15. Andrzej Dąbrowski, Jacek Pomykała and Igor E. Shparlinski, On oracle factoring of integers, Journal of Complexity 76 (2023) 101741. DOI 10.1016/j.jco.2023.101741, https://doi.org/10.1016/j.jco.2023.101741 (preprint arXiv:1912.00345, https://arxiv.org/abs/1912.00345)
16. Aditya Ravi and Ilya Volkovich, New Characterization of the Factor Refinement Algorithm with Applications, in: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (ISSAC 2023), ACM (2023) 490-497. DOI 10.1145/3597066.3597108, https://doi.org/10.1145/3597066.3597108
17. David Harvey and Markus Hittmeir, A log-log speedup for exponent one-fifth deterministic integer factorisation, Mathematics of Computation 91(335) (2022) 1367-1379. DOI 10.1090/mcom/3708, https://doi.org/10.1090/mcom/3708 (preprint arXiv:2105.11105, https://arxiv.org/abs/2105.11105)
18. Jacek Pomykała and Olgierd Żołnierczyk, Elliptic-Curve Factorization and Witnesses, in: Computational Science - ICCS 2024, Lecture Notes in Computer Science, Springer (2024) 287-301. DOI 10.1007/978-3-031-63749-0_20, https://doi.org/10.1007/978-3-031-63749-0_20
19. Jacek Pomykała and Maciej Radziejewski, Integer factoring and compositeness witnesses, Journal of Mathematical Cryptology 14 (2020) 346-358. DOI 10.1515/jmc-2019-0023, https://doi.org/10.1515/jmc-2019-0023
20. David Harvey and Markus Hittmeir, Deterministic methods for finding elements of large multiplicative order, arXiv:2601.11131 (2026). arXiv:2601.11131, https://arxiv.org/abs/2601.11131
21. Pantelimon Stănică, Erik Mulder and Markus Hittmeir, Multi-target hyperbolic sieves and elliptic trace obstructions, arXiv:2606.13018 (2026). arXiv:2606.13018, https://arxiv.org/abs/2606.13018
22. Valerii Hlukhov, Quantum-Inspired Computing: Shor's Algorithm and Euler's Totient Function, in: 2023 IEEE 12th International Conference on Intelligent Data Acquisition and Advanced Computing Systems (IDAACS), IEEE (2023). DOI 10.1109/IDAACS58523.2023.10348718, https://doi.org/10.1109/IDAACS58523.2023.10348718