Sums of Divisors, Perfect Numbers and Factoring

DOI10.1137/0215083zbMath0606.10003OpenAlexW1980291956MaRDI QIDQ3744218

Eric Bach, Jeffrey O. Shallit, Gary Lee Miller

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/27cbe1f696ce981df94eac189fb0d55cfd35a762

zbMATH Keywords

perfect numbersamicable pairsfactoringprime factorizationrandom reductionmultiply perfect numbersrandom polynomial time algorithmGill's complexity class BPP

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Arithmetic functions; related numbers; inversion formulas (11A25) Randomized algorithms (68W20) Factorization (11Y05) Values of arithmetic functions; tables (11Y70)

Related Items (11)

Sieve algorithms for perfect power testing ⋮ The Power of Leibniz-Like Functions as Oracles ⋮ Counting lattice vectors ⋮ Some remarks on computing the square parts of integers ⋮ New Characterization of the Factor Refinement Algorithm with Applications ⋮ Deterministic factoring with oracles ⋮ Factorization, malleability and equivalent problems ⋮ An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler’s totient ⋮ A deterministic version of Pollard’s $p-1$ algorithm ⋮ Factoring with Cyclotomic Polynomials ⋮ COMPLEXITY OF SHORT GENERATING FUNCTIONS

This page was built for publication: Sums of Divisors, Perfect Numbers and Factoring