Flowers Discusses the Quadratic Sieve Factoring Algorithm

Posted on 3/28/2011 12:34:10 PM

Dr. Tim Flowers, of the Mathematics Department, will give a colloquium talk on Wednesday, March 30, 2011, at 3:30 p.m. in Stright 302 entitled “An Overview of the Quadratic Sieve Factoring Algorithm.”

In 1977, Martin Gardner's “Mathematical Games” feature in Scientific American posed the challenge of factoring a 129-digit number (known as RSA-129). Using the resources available at the time, it was estimated that it would take 40 quadrillion years to factor this number. However, in 1994, Lenstra, et al., announced a factorization of RSA-129. Using many computers, it took them eight months to complete this groundbreaking calculation. They used a modified implementation of the Quadratic Sieve, which had been originally introduced by Carl Pomerance in 1982.

The goal of this talk will be to give a general overview of the Quadratic Sieve algorithm. Special attention will be given to the elementary number theory and linear algebra techniques used in the algorithm.

Undergraduate students are encouraged to attend! The talk is intended to be accessible to those who are familiar with the basics of modular arithmetic and linear algebra.