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].











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)