Parallel Integer Factorization Using Quadratic Forms

Abstract

Factorization is important for both practical and theoretical reasons. In secure digital communication, security of the commonly used RSA public key cryptosystem depends on the difficulty of factoring large integers. In number theory, factoring is of fundamental importance. This research has analyzed algorithms for integer factorization based on continued fractions and binary quadratic forms, focusing on runtime analysis and comparison of parallel implementations of the algorithm. In the process it proved several valuable results about continued fractions. In 1975, Daniel Shanks used class group infrastructure to modify the Morrison-Brillhart algorithm and develop Square Forms Factorization, but he never published his work on this algorithm or provided a proof that it works. This research began by analyzing Square Forms Factorization, formalizing and proving the premises on which the algorithm is based. First, this research analyzed the connections between continued fractions and quadratic forms, proving, among other things, that the square of any ambiguous cycle is the principal cycle. Then, the connection with ideals was developed, requiring a generalization to the standard description and formulas for multiplication of ideals. Lastly, the connection was made with lattices and minima, allowing for a generalization of the formulas relating composition with distance. These results are fundamental to explaining why Square Forms Factorization works. This research also analyzed several variations, including two different parallel implementations, one of which was considered by Shanks and one of which is original. The results suggest that the new implementation, which utilizes composition of quadratic forms, is slower for small numbers of processors, but is more efficient asymptotically as the number of processors grows.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 09, 2005
Accession Number
ADA436652

Entities

People

  • Stephen S. Mcmath

Organizations

  • United States Naval Academy

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Asymetric Encryption
  • Coding
  • Computations
  • Computer Programs
  • Computers
  • Cryptography
  • Digital Communications
  • Infrastructure
  • Mathematics
  • Number Theory
  • Numbers
  • Polynomials
  • Real Numbers
  • Square Roots
  • Two Dimensional
  • United States Naval Academy

Fields of Study

  • Computer science

Readers

  • Cybersecurity.
  • Graph Algorithms and Convex Optimization.
  • Theoretical Analysis.