Carl Pomerance

Last updated

Carl Bernard Pomerance (born 1944 in Joplin, Missouri) is an American number theorist. He attended college at Brown University and later received his Ph.D. from Harvard University in 1972 with a dissertation proving that any odd perfect number has at least seven distinct prime factors. [1] He joined the faculty at the University of Georgia, becoming full professor in 1982. He subsequently worked at Lucent Technologies for a number of years, and then became a distinguished Professor at Dartmouth College.

Contents

Contributions

He has over 120 publications, including co-authorship with Richard Crandall of Prime numbers: a computational perspective (Springer-Verlag, first edition 2001, second edition 2005 [2] ), and with Paul Erdős. [3] He is the inventor of one of the integer factorization methods, the quadratic sieve algorithm, which was used in 1994 for the factorization of RSA-129. He is also one of the discoverers of the Adleman–Pomerance–Rumely primality test.

Awards and honors

He has won many teaching and research awards, including the Chauvenet Prize in 1985, [4] MAA's Deborah and Franklin Haimo Distinguished Teaching Award in 1997, and the Levi L. Conant Prize in 2001 for "A Tale of Two Sieves". [5]

In 2012 he became a fellow of the American Mathematical Society. [6] He also became the John G. Kemeny Parents Professor of Mathematics in the same year. [7] [8]

See also

Related Research Articles

<span class="mw-page-title-main">Carmichael number</span> Composite number in number theory

In number theory, a Carmichael number is a composite number , which in modular arithmetic satisfies the congruence relation:

In number theory, integer factorization is the decomposition, when possible, of a positive integer into a product of smaller integers. If the factors are further restricted to be prime numbers, the process is called prime factorization, and includes the test whether the given integer is prime.

<span class="mw-page-title-main">Prime number</span> Evenly divided only by 1 or itself

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically, its complexity for factoring an integer n (consisting of ⌊log2n⌋ + 1 bits) is of the form

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 third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra.

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.

In computational number theory, the Lucas test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known. It is the basis of the Pratt certificate that gives a concise verification that n is prime.

In mathematics, a Smarandache–Wellin number is an integer that in a given base is the concatenation of the first n prime numbers written in that base. Smarandache–Wellin numbers are named after Florentin Smarandache and Paul R. Wellin.

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 algorithms for primality testing and integer factorization, finding solutions to diophantine equations, and explicit methods in arithmetic geometry. Computational number theory has applications to cryptography, including RSA, elliptic curve cryptography and post-quantum cryptography, and is used to investigate conjectures and open problems in number theory, including the Riemann hypothesis, the Birch and Swinnerton-Dyer conjecture, the ABC conjecture, the modularity conjecture, the Sato-Tate conjecture, and explicit aspects of the Langlands program.

Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer n, the integer to be factored, can be divided by each number in turn that is less than n. For example, for the integer n = 12, the only numbers that divide it are 1, 2, 3, 4, 6, 12. Selecting only the largest powers of primes in this list gives that 12 = 3 × 4 = 3 × 22.

In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it.

John Lewis Selfridge, was an American mathematician who contributed to the fields of analytic number theory, computational number theory, and combinatorics.

In number theory, the continued fraction factorization method (CFRAC) is an integer factorization algorithm. It is a general-purpose algorithm, meaning that it is suitable for factoring any integer n, not depending on special form or properties. It was described by D. H. Lehmer and R. E. Powers in 1931, and developed as a computer algorithm by Michael A. Morrison and John Brillhart in 1975.

<span class="mw-page-title-main">Richard Schroeppel</span> American mathematician

Richard C. Schroeppel is an American mathematician born in Illinois. His research has included magic squares, elliptic curves, and cryptography. In 1964, Schroeppel won first place in the United States among over 225,000 high school students in the Annual High School Mathematics Examination, a contest sponsored by the Mathematical Association of America and the Society of Actuaries. In both 1966 and 1967, Schroeppel scored among the top 5 in the U.S. in the William Lowell Putnam Mathematical Competition. In 1973 he discovered that there are 275,305,224 normal magic squares of order 5. In 1998–1999 he designed the Hasty Pudding Cipher, which was a candidate for the Advanced Encryption Standard, and he is one of the designers of the SANDstorm hash, a submission to the NIST SHA-3 competition.

In number theory, a provable prime is an integer that has been calculated to be prime using a primality-proving algorithm. Boot-strapping techniques using Pocklington primality test are the most common ways to generate provable primes for cryptography. Contrast with probable prime, which is likely to be prime, based on the output of a probabilistic primality test.

Paul Leyland is a British astronomer and number theorist who has studied integer factorization and primality testing.

In number theory, a Leyland number is a number of the form

In computational number theory, the Adleman–Pomerance–Rumely primality test is an algorithm for determining whether a number is prime. Unlike other, more efficient algorithms for this purpose, it avoids the use of random numbers, so it is a deterministic primality test. It is named after its discoverers, Leonard Adleman, Carl Pomerance, and Robert Rumely. The test involves arithmetic in cyclotomic fields.

The Levi L. Conant Prize is a mathematics prize of the American Mathematical Society, which has been awarded since 2000 for outstanding expository papers published in the Bulletin of the American Mathematical Society or the Notices of the American Mathematical Society in the past five years. The award is worth $1,000 and is awarded annually.

References

  1. ↑ Carl Pomerance at the Mathematics Genealogy Project
  2. ↑ Crandall, R.; Pomerance, C. (2005). Prime numbers: a computational perspective (second ed.). Springer-Verlag, New York. doi:10.1007/0-387-28979-8. ISBN   978-0-387-25282-7.
  3. ↑ Canfield, E.R; Erdös, Paul; Pomerance, Carl (1983). "On a problem of Oppenheim concerning "factorisatio numerorum"". Journal of Number Theory . Elsevier BV. 17 (1): 1–28. doi: 10.1016/0022-314x(83)90002-1 . ISSN   0022-314X.
  4. ↑ Pomerance, Carl (1981). "Recent developments in primality testing". The Mathematical Intelligencer . Springer Science and Business Media LLC. 3 (3): 97–105. doi:10.1007/bf03022861. ISSN   0343-6993. S2CID   121750836.
  5. ↑ Pomerance, Carl (December 1996). "A Tale of Two Sieves". Notices of the AMS . 43 (12): 1473–1485.
  6. ↑ "List of Fellows of the American Mathematical Society". www.ams.org. 2017. Retrieved 2017-06-30.
  7. ↑ Blumberg, Joseph (2012-11-08). "Dartmouth Mathematicians Honored by Preeminent Professional Society | Dartmouth News". Dartmouth News. Retrieved 2017-06-30.
  8. ↑ Pomerance, Carl. "Curriculum Vitae" (PDF). Retrieved 30 June 2017.


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.