License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.17
URN: urn:nbn:de:0030-drops-155286
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15528/
Go to the corresponding LIPIcs Volume Portal

Du, Yang ; Volkovich, Ilya

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

pdf-format:
LIPIcs-FSTTCS-2021-17.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{du_et_al:LIPIcs.FSTTCS.2021.17,
  author =	{Du, Yang and Volkovich, Ilya},
  title =	{{Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{17:1--17:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15528},
  URN =		{urn:nbn:de:0030-drops-155286},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.17},
  annote =	{Keywords: Euler’s Totient Function, Integer Factorization, Number of Prime Factors, Derandomization}
}

Keywords: Euler’s Totient Function, Integer Factorization, Number of Prime Factors, Derandomization
Collection: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Issue Date: 2021
Date of publication: 29.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI