Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function

Du, Yang; Volkovich, Ilya

doi:10.4230/LIPIcs.FSTTCS.2021.17

File

LIPIcs.FSTTCS.2021.17.pdf

Filesize: 0.72 MB
10 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2021.17
URN: urn:nbn:de:0030-drops-155286

Author Details

Yang Du

Departments of EECS, CSE Division, University of Michigan, Ann Arbor, MI, USA

Ilya Volkovich

Computer Science Department, Boston College, Chestnut Hill, MA, USA

Acknowledgements

The authors would like to thank the anonymous referees for their detailed comments and suggestions on the previous version of the paper.

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 17:1-17:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.17

Abstract

In this work we devise the first efficient deterministic algorithm for approximating ω(N) - the number of prime factors of an integer N ∈ ℕ, given in addition oracle access to Euler’s Totient function Φ(⋅). We also show that the algorithm can be extended to handle a more general class of additive functions that "depend solely on the exponents in the prime factorization of an integer". In particular, our result gives the first algorithm that approximates ω(N) without necessarily factoring N. Indeed, all the previously known algorithms for computing or even approximating ω(N) entail factorization of N, and therefore are either randomized [M. O. Rabin, 1980; D. L. Long, 1981] or require the Generalized Riemann Hypothesis (GRH) [G. L. Miller, 1976]. Our approach combines an application of Coppersmith’s method for finding non-trivial factors of integers whose prime factors satisfy certain "relative size" conditions of [F. Morain et al., 2018], together with a new upper bound on Φ(N) in terms of ω(N) which could be of independent interest.

Subject Classification

ACM Subject Classification

Mathematics of computing → Number-theoretic computations
Theory of computation → Problems, reductions and completeness
Theory of computation → Computational complexity and cryptography

Keywords

Euler’s Totient Function
Integer Factorization
Number of Prime Factors
Derandomization

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

L. M. Adleman and K. S. McCurley. Open problems in number theoretic complexity, II. In Algorithmic Number Theory, First International Symposium, ANTS-I, Ithaca, NY, USA, May 6-9, 1994, Proceedings, pages 291-322, 1994. URL: https://doi.org/10.1007/3-540-58691-1.
M. Agrawal, N. Kayal, and N. Saxena. Primes is in P. Annals of Mathematics, 160(2):781-793, 2004.
E. Bach. Intractable problems in number theory. In Advances in Cryptology - CRYPTO '88, 8th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1988, Proceedings, pages 77-93, 1988. URL: https://doi.org/10.1007/0-387-34799-2.
E. Bach, G. L. Miller, and J. Shallit. Sums of divisors, perfect numbers and factoring. SIAM J. Comput., 15(4):1143-1154, 1986. URL: https://doi.org/10.1137/0215083.
D. Coppersmith. Finding a small root of a univariate modular equation. In Advances in Cryptology - EUROCRYPT, volume 1070 of Lecture Notes in Computer Science, pages 155-165. Springer, 1996. URL: https://doi.org/10.1007/3-540-68339-9.
M. Hittmeir and J. Pomykala. Deterministic integer factorization with oracles for euler’s totient function. Fundam. Inform., 172(1):39-51, 2020. URL: https://doi.org/10.3233/FI-2020-1891.
J. Kim, I. Volkovich, and N. X. Zhang. The power of leibniz-like functions as oracles. In The 15th International Computer Science Symposium in Russia, CSR, volume 12159 of Lecture Notes in Computer Science, pages 263-275. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-50026-9.
S. Landau. Some remarks on computing the square parts of integers. Inf. Comput., 78(3):246-253, 1988. URL: https://doi.org/10.1016/0890-5401(88)90028-4.
D. L. Long. Random equivalence of factorization and computation of orders. Technical Report 284, Princeton University, 1981.
G. L. Miller. Riemann’s hypothesis and tests for primality. J. Comput. Syst. Sci., 13(3):300-317, 1976. URL: https://doi.org/10.1016/S0022-0000(76)80043-8.
F. Morain, G. Renault, and B. Smith. Deterministic factoring with oracles. CoRR, abs/1802.08444, 2018. URL: http://arxiv.org/abs/1802.08444.
M. O. Rabin. Probabilistic algorithm for testing primality. Journal of number theory, 12(1):128-138, 1980.
J. Shallit and A. Shamir. Number-theoretic functions which are equivalent to number of divisors. Inf. Process. Lett., 20(3):151-153, 1985. URL: https://doi.org/10.1016/0020-0190(85)90084-5.
H. Woll. Reductions among number theoretic problems. Inf. Comput., 72(3):167-179, 1987. URL: https://doi.org/10.1016/0890-5401(87)90030-7.
B. Zralek. A deterministic version of pollard’s p-1 algorithm. Math. Comput., 79(269):513-533, 2010. URL: https://doi.org/10.1090/S0025-5718-09-02262-5.