Factoring Numbers in 0 (log n) Arithmetic Steps,

Abstract

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 big as 2 to the power c n-squared, thus requiring exponentially many bit operations.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1977
Accession Number
ADA047709

Entities

People

  • Adi Shamir

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Automata
  • Composite Materials
  • Computations
  • Computer Programs
  • Computer Science
  • Computers
  • Electronics Laboratories
  • Identities
  • Information Systems
  • Intervals
  • Mathematics
  • Military Research
  • Naval Operations
  • New York
  • Polynomials

Fields of Study

  • Mathematics

Readers

  • Approximation Theory.
  • Theoretical Analysis.