1 Search Results for "Du, Yang"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.17
Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function

Authors: Yang Du and Ilya Volkovich

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@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}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.17},
  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}
}
  • Refine by Author
  • 1 Du, Yang
  • 1 Volkovich, Ilya

  • Refine by Classification
  • 1 Mathematics of computing → Number-theoretic computations
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Derandomization
  • 1 Euler’s Totient Function
  • 1 Integer Factorization
  • 1 Number of Prime Factors

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact