No label defined (Q3744217)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3979140
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3979140

      Statements

      1986
      0 references
      computational number theory
      0 references
      perfect numbers
      0 references
      random reduction
      0 references
      multiply perfect numbers
      0 references
      amicable pairs
      0 references
      computational complexity
      0 references
      Euler phi-function
      0 references
      sum of divisors
      0 references
      factoring
      0 references
      random polynomial time algorithm
      0 references
      0 references
      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].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references