Implementing the Continued Fraction Algorithm on the Illiac IV.

Abstract

The factoring of large composite integers has an important inverse relationship with the security of certain types of encrytion systems. If a particular code is based on a 100 digit composite number, the code can be considered secure for the length of time it would take to factor a 100 digit number on the fastest computer available using the best known factoring algorithm. The continued fraction algorithm has generally been regarded as the best proven method known for factoring large integers. The research performed by the principle investigator and described in this report was to produce a detailed running time analysis of the algorithm and obtain a model from which CPU time estimates could be obtained for the factoring of very large numbers. Since the fastest machines in use today are array processors, such as the ILLIAC IV and the English ICL-DAP, a feasibility study was conducted showing that the continued fraction method can be efficiently implemented on such a machine. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1980
Accession Number
ADA100145

Entities

People

  • Marvin Wunderlich

Organizations

  • Northern Illinois University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Arithmetic Units
  • Central Processing Units
  • Classification
  • Composite Materials
  • Computations
  • Computer Science
  • Computers
  • Identities
  • Mathematics
  • Number Theory
  • Numbers
  • Parallel Processors
  • Plastic Explosives
  • Prime Numbers
  • Security

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Programming and Software Development.
  • Theoretical Analysis.