Peter Lawrence Montgomery (September 25, 1947 – February 18, 2020) was an American

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...

who worked at the

System Development Corporation System Development Corporation (SDC) was a computer software company based in Santa Monica, California. Founded in 1955, it is considered the first company of its kind. History SDC began as the systems engineering group for the SAGE air-defens ...

and

Microsoft Research Microsoft Research (MSR) is the research subsidiary of Microsoft. It was created in 1991 by Richard Rashid, Bill Gates and Nathan Myhrvold with the intent to advance state-of-the-art computing and solve difficult world problems through technologi ...

. He is best known for his contributions to

computational number theory In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of computational methods for investigating and solving problems in number theory and arithmetic geometry, including algorith ...

and mathematical aspects of

cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...

, including the

Montgomery multiplication In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. ...

method for arithmetic in

finite fields In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subt ...

, the use of

Montgomery curve In mathematics the Montgomery curve is a form of elliptic curve introduced by Peter L. Montgomery in 1987, different from the usual Weierstrass form. It is used for certain computations, and in particular in different cryptography applications. ...

s in applications of

elliptic curves In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...

to integer factorization and other problems, and the

Montgomery ladder Elliptic curve scalar multiplication is the operation of successively adding a point along an elliptic curve to itself repeatedly. It is used in elliptic curve cryptography (ECC) as a means of producing a one-way function. The literature presents ...

, which is used to protect against

side-channel attack In computer security, a side-channel attack is any attack based on extra information that can be gathered because of the fundamental way a computer protocol or algorithm is implemented, rather than flaws in the design of the protocol or algori ...

s in

elliptic curve cryptography Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide e ...

Education and career

Montgomery began his undergraduate career at the

University of California, Riverside The University of California, Riverside (UCR or UC Riverside) is a public university, public Land-grant university, land-grant research university in Riverside, California. It is one of the ten campuses of the University of California system. Th ...

, in 1965 and transferred to Berkeley in 1967, earning a BA in mathematics in 1969 and an MA in mathematics in 1971, He joined the

(SDC) in 1972, where he worked for many years as a programmer implementing algorithms for the

CDC 7600 The CDC 7600 was the Seymour Cray-designed successor to the CDC 6600, extending Control Data's dominance of the supercomputer field into the 1970s. The 7600 ran at 36.4 MHz (27.5 ns clock cycle) and had a 65 Kword primary memory (with a ...

and PDP series of computers, including the implementation of algorithms for multi-precision arithmetic that led to the invention of what is now known as

. He then returned to academia in 1987, earning his PhD in mathematics from

UCLA The University of California, Los Angeles (UCLA) is a public university, public Land-grant university, land-grant research university in Los Angeles, California. UCLA's academic roots were established in 1881 as a Normal school, teachers colle ...

in 1992 under the supervision of David Cantor. He joined the cryptography group at

in 1998, where he worked until his retirement in 2014. On February 28, 2020, an 829-bit (RSA-250) RSA key was successfully factorised. The team dedicated the computation to Peter Montgomery, who died on the 18th of the same month.

Contributions

Montgomery is particularly known for his contributions to the

elliptic curve method The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub- exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the t ...

of factorization, which include a method for speeding up the second stage of algebraic-group factorization algorithms using

FFT A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in th ...

techniques for fast polynomial evaluation at equally spaced points. This was the subject of his dissertation, for which he received his

Ph.D. A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is a ...

in 1992 from the

University of California, Los Angeles The University of California, Los Angeles (UCLA) is a public university, public Land-grant university, land-grant research university in Los Angeles, California. UCLA's academic roots were established in 1881 as a Normal school, teachers colle ...

. He also invented the

block Lanczos algorithm In computer science, the block Lanczos algorithm is an algorithm for finding the nullspace of a matrix over a finite field, using only multiplication of the matrix by long, thin matrices. Such matrices are considered as vectors of tuples of finite-f ...

for finding

nullspace In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the linear subspace of the domain of the map which is mapped to the zero vector. That is, given a linear map between two vector spaces and , the kernel ...

of a matrix over a

finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subt ...

, which is very widely used for the

quadratic sieve The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerab ...

and

number field sieve In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form :\exp\left( ...

methods of factorization; he has been involved in the computations which set a number of

integer factorization records Integer factorization is the process of determining which prime numbers divide a given positive integer. Doing this quickly has applications in cryptography. The difficulty depends on both the size and form of the number and its prime factors; it ...

. He was a

Putnam Fellow The William Lowell Putnam Mathematical Competition, often abbreviated to Putnam Competition, is an annual mathematics competition for undergraduate college students enrolled at institutions of higher learning in the United States and Canada (regar ...

in 1967. In that year, he was one of only two contestants, along with child prodigy

Don Zagier Don Bernard Zagier (born 29 June 1951) is an American-German mathematician whose main area of work is number theory. He is currently one of the directors of the Max Planck Institute for Mathematics in Bonn, Germany. He was a professor at the ''Col ...

of MIT, to solve all twelve of the exam problems.

Selected works

* * *

References

External links

Incomplete list of Montgomery's papersIn Memoriam: Peter L. Montgomery (1947–2020) (Notices - American Mathematical Society, April 2021, Volume 68, Number 4, Joppe W. Bos and Kristin E. Lauter)
1947 births 2020 deaths 20th-century American mathematicians 21st-century American mathematicians American cryptographers Microsoft employees Number theorists Putnam Fellows Scientists from the San Francisco Bay Area University of California, Berkeley alumni University of California, Los Angeles alumni {{US-mathematician-stub