2026-07-24T08:27:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15528 2024-03-06T10:55:31Z ddc:004 open_access

Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function Du, Yang Volkovich, Ilya Euler’s Totient Function Integer Factorization Number of Prime Factors Derandomization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yang Du and Ilya Volkovich 2021 Is Part Of LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2021.17 urn:nbn:de:0030-drops-155286 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.17 eng https://creativecommons.org/licenses/by/4.0/legalcode