 | This article may be expanded with text translated from the corresponding article in German. (October 2018)Click [show] for important translation instructions.
|
Hugh C. Williams | |
|---|---|
 Williams in 1984 | |
| Born | 23 July 1943 London, Ontario, Canada |
| Nationality | Canadian |
| Occupation | Mathematician |
Hugh Cowie Williams (born 23 July 1943) is a Canadian mathematician. He deals with number theory and cryptography.
Williams studied mathematics at the University of Waterloo (bachelor's degree 1966, master's degree 1967), where he received his doctorate in 1969 in computer science under Ronald C. Mullin (A generalization of the Lucas functions). He was a post-doctoral student at York University.
In 1970 he became assistant professor at the University of Manitoba, where in 1972 he attained associate professor status and professor in 1979.
In 2001 he became a professor at the University of Calgary, and professor emeritus since 2004. Since 2001 he has held the "iCore Chair" in Algorithmic Number Theory and Cryptography.
Together with Rei Safavi-Naini he heads the Institute for Security, Privacy and Information Assurance (ISPIA) - formerly Centre for Information Security and Cryptography - at Calgary. [1] Between 1998 and 2001 he was an adjunct professor at the University of Waterloo. He was a visiting scholar at the University of Bordeaux, at Macquarie University and at University of Leiden. From 1978 to January 2007 he was associate editor of the journal Mathematics of Computation .
Among other things Williams dealt with primality tests; [2] Williams primes were named for him. He developed custom hardware for number-theoretical calculations, for example the MSSU in 1995. [3] In cryptography, he developed in 1994 with Renate Scheidler and Johannes Buchmann a method of public key cryptography based on real quadratic number fields. [4] Williams developed algorithms for calculating invariants of algebraic number fields such as class numbers and regulators.
Williams deals with math history and wrote a book about the history of primality tests. In it, he showed among other things that Édouard Lucas worked shortly before his early death on a test similar to today's elliptic curve method. He reconstructed the method that Fortuné Landry used in 1880 (at the age of 82) to factor the sixth Fermat number (a 20-digit number). [5]
Together with Jeffrey Shallit and François Morain he discovered a forgotten mechanical number sieve created by Eugène Olivier Carissan, the first such device from the beginning of the 20th century (1912), and described it in detail. [6]
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
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, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:
Leonard Adleman is an American computer scientist. He is one of the creators of the RSA encryption algorithm, for which he received the 2002 Turing Award, often called the Nobel prize of Computer science. He is also known for the creation of the field of DNA computing.
Michael Oser Rabin is an Israeli mathematician and computer scientist and a recipient of the Turing Award.
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.
"The Magic Words are Squeamish Ossifrage" was the solution to a challenge ciphertext posed by the inventors of the RSA cipher in 1977. The problem appeared in Martin Gardner's Mathematical Games column in the August 1977 issue of Scientific American. It was solved in 1993–94 by a large, joint computer project co-ordinated by Derek Atkins, Michael Graff, Arjen Lenstra and Paul Leyland. More than 600 volunteers contributed CPU time from about 1,600 machines over six months. The coordination was done via the Internet and was one of the first such projects.
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 computational number theory, Williams's p + 1 algorithm is an integer factorization algorithm, one of the family of algebraic-group factorisation algorithms. It was invented by Hugh C. Williams in 1982.
Carl Bernard Pomerance 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. 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.
In computational number theory, a variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, for example hashing, public-key cryptography, and search of prime factors in large numbers.
In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test. "Succinct" usually means that the proof should be at most polynomially larger than the number of digits in the number itself.
Arthur Oliver Lonsdale Atkin, who published under the name A. O. L. Atkin, was a British mathematician.
Hendrik Willem Lenstra Jr. is a Dutch mathematician.
Arjen Klaas Lenstra is a Dutch mathematician, cryptographer and computational number theorist. He is currently a professor at the École Polytechnique Fédérale de Lausanne (EPFL) where he heads of the Laboratory for Cryptologic Algorithms.
In computational number theory, a factor base is a small set of prime numbers commonly used as a mathematical tool in algorithms involving extensive sieving for potential factors of a given integer.
In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain, in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing followed quickly.
Johannes Alfred Buchmann is a German computer scientist, mathematician and professor emeritus at the department of computer science of the Technische Universität Darmstadt.
Primality Testing for Beginners is an undergraduate-level mathematics book on primality tests, methods for testing whether a given number is a prime number, centered on the AKS primality test, the first method to solve this problem in polynomial time. It was written by Lasse Rempe-Gillen and Rebecca Waldecker, and originally published in German as Primzahltests für Einsteiger: Zahlentheorie, Algorithmik, Kryptographie. It was translated into English as Primality Testing for Beginners and published in 2014 by the American Mathematical Society, as volume 70 of their Student Mathematical Library book series. A second German-language edition was publisher by Springer in 2016.
| General | |
|---|---|
| National libraries | |
| Scientific databases | |
| Other | |
