Algorithmic Problems in Number Theory

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

The investigator has discovered that, for extremely large input sizes, modern factorization algorithms such as the number-field sieve can be carried out with far less memory per processor than was previously believed. Consequently, for extremely large values of d, the number-field sieve can factor 3d-digit numbers at the same cost that was previously believed to be required for d-digit numbers. The investigator is studying the practical effectiveness of this discovery for small input sizes, such as 1024 bits and 1536 bits. The investigator is also continuing his research into the fundamental computational tools in commutative rings of Krull dimension 1. The number-field sieve is the best known attack on many public-key cryptosystems used to protect the secrecy and authenticity of Internet communications. Understanding the power of this algorithm is essential in choosing safe key sizes for the cryptosystems. If, for example, criminals can factor integers as large as 1024 bits, then users must choose key sizes larger than 1024 bits. This award is being cofunded by the Algebra, Number Theory, and Combinatorics Program and the Numeric, Symbolic, and Geometric Computation Program.