The Extraordinary Power of Division in Straight Line Programs

DOI10.4169/AMER.MATH.MONTHLY.119.07.584MaRDI QIDQ4908555zbMATH OpenOpenAlexWikidataFDO

Authors Joe Hobart, Peter Borwein

Publication date 6 March 2013

Published in The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4169/amer.math.monthly.119.07.584

zbMATH Keywords

computational complexitydivisioninteger factorizationstraight line program

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Greatest common divisors of polynomials given by straight-line programs
• On Faster Integer Calculations Using Non-arithmetic Primitives
• Arithmetic complexity
• On primitive recursive algorithms and the greatest common divisor function
• Breaking RSA may be as difficult as factoring
• Log Depth Circuits for Division and Related Problems
• On the Shortest Linear Straight-Line Program for Computing Linear Forms
• On the Simplification and Equivalence Problems for Straight-Line Programs
• scientific article; zbMATH DE number 3958730
• Division in logspace-uniform NC

Cited in

(2)

• scientific article; zbMATH DE number 4072374 (Why is no real title available?)
• Integer complexity and well-ordering

This page was built for publication: The Extraordinary Power of Division in Straight Line Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4908555)