Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Factoring

John Brillhart

University of Arizona

The Lehmer dynasty and the search for a better factoring method, 1900-1975

Abstract:

This is a history talk about the three Lehmers... D. N. Lehmer, D. H. Lehmer, and Emma Lehmer and the computing world they created that was centered at Berkeley. \vskip .1in \noindent One of their main mathematical interests throughout the period 1900 - 1975 was factoring integers or proving that a prime is a prime. (No, Gertrude Stein did Not say ``A prime is a prime is a prime".) \vskip .1in \noindent A dramatic moment came in 1970 when factoring a large, composite integer N by exclusion. The method considered best for factoring large integers for at least 150 years and which was the favored method used by the Lehmers on their sieves, was shown to be much less powerful than finding non-trivial $x$ and $y$ in the congruence $x2 \equiv y2$ (mod $N$) on a computer. The latter is the basic method that has been used and improved on ever since to carry out large-scale factoring.

Host: Math Club

May 26, 2005

2:00 PM

AP&M 6438

****************************