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.808811366558075
0 references
0.781299352645874
0 references
0.745904266834259
0 references
0.7361684441566467
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