The Extraordinary Power of Division in Straight Line Programs

• Published in 2012
• Added on 2026-02-06

A lovely circle of ideas due primarily to Shub, Smale and Shamir says that if it is possible to divide quickly, then it is possible to factor quickly. Here, dividing quickly means modular division over a straight line program. In this context, quickly means actual computations done quickly. The point of this note is to advertise this lovely circle of ideas. The language of complexity theory sometimes clouds the underlying simplicity of the ideas. It is our hope to provide a straight forward explanation of these intrinsically simple ideas.

Links

• https://www.jstor.org/stable/10.4169/amer.math.monthly.119.07.584?seq=3

Other information

BibTeX entry

@article{TheExtraordinaryPowerofDivisioninStraightLinePrograms,
	key = {TheExtraordinaryPowerofDivisioninStraightLinePrograms},
	type = {article},
	title = {The Extraordinary Power of Division in Straight Line Programs},
	author = {Peter Borwein and Joe Hobart},
	abstract = {A lovely circle of ideas due primarily to Shub, Smale and Shamir says that if it is possible to divide quickly, then it is possible to factor quickly. Here, dividing quickly means modular division over a straight line program. In this context, quickly means actual computations done quickly. The point of this note is to advertise this lovely circle of ideas. The language of complexity theory sometimes clouds the underlying simplicity of the ideas. It is our hope to provide a straight forward explanation of these intrinsically simple ideas.},
	comment = {},
	date_added = {2026-02-06},
	date_published = {2012-02-09},
	urls = {https://www.jstor.org/stable/10.4169/amer.math.monthly.119.07.584?seq=3},
	collections = {fun-maths-facts,integerology},
	url = {https://www.jstor.org/stable/10.4169/amer.math.monthly.119.07.584?seq=3},
	year = 2012,
	urldate = {2026-02-06}
}