LCS Publication Details
Publication Title: FACTORING NUMBERS IN 0 (Log N) ARITHMETIC STEPS
Publication Author: Shamir, Adi
Additional Authors:
LCS Document Number: MIT-LCS-TM-091
Publication Date: 11-1-1977
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
In this paper we show that a non-trivial factor of a composite number n can be found by performing arithmetic steps in a number proportional to the number of bits in n, and thus there are extremely short straight-line factoring programs. However, this theoretical result does not imply that natural numbers can be factored in polynomial time in the Turing-Machine model of complexity, since the numbers operated on can be as 2 cn2, thus requiring exponentially many bit operations.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.