scientific article; zbMATH DE number 3979140
From MaRDI portal
Publication:3744217
This article discusses the computational complexity of some functions from elementary number theory. It is shown that computing \(\varphi(N)\) (the Euler phi-function) or \(\sigma(N)\) (sum of divisors of \(N)\) is randomly equivalent to factoring \(N\). A corollary is that there exists a random polynomial time algorithm to determine if \(N\) is perfect \((\sigma(N)=2N)\) or multiply perfect \((N\mid \sigma(N)).\) A more detailed version of this paper has appeared in SIAM J. Comput. 15, 1143--1154 (1986; Zbl 0606.10003)]. For the entire collection see [Zbl 08259216].
Recommendations
Cited in
(11)- Number-theoretic functions which are equivalent to number of divisors
- On the complexity of slice functions
- Some remarks on computing the square parts of integers
- Computing the inverses, their power sums, and extrema for Euler's totient and other multiplicative functions
- On the arithmetic complexity of Euler function
- scientific article; zbMATH DE number 2184737 (Why is no real title available?)
- scientific article; zbMATH DE number 3931010 (Why is no real title available?)
- scientific article; zbMATH DE number 1346365 (Why is no real title available?)
- scientific article; zbMATH DE number 1148334 (Why is no real title available?)
- Some characterizations of functions computable in on-line arithmetic
- On the upper bounds for complexities of discrete functions
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3744217)