In number theory, a Carmichael number is a composite number which in modular arithmetic satisfies the congruence relation:
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
In number theory, an odd integer n is called an Euler–Jacobi probable prime to base a, if a and n are coprime, and
The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.
In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite, the condition is generally chosen in order to make such exceptions rare.
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.
The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test.
In mathematics, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and
Richard Kenneth Guy was a British mathematician. He was a professor in the Department of Mathematics at the University of Calgary. He is known for his work in number theory, geometry, recreational mathematics, combinatorics, and graph theory. He is best known for co-authorship of Winning Ways for your Mathematical Plays and authorship of Unsolved Problems in Number Theory. He published more than 300 scholarly articles. Guy proposed the partially tongue-in-cheek "strong law of small numbers", which says there are not enough small integers available for the many tasks assigned to them – thus explaining many coincidences and patterns found among numerous cultures. For this paper he received the MAA Lester R. Ford Award.
John Lewis Selfridge, was an American mathematician who contributed to the fields of analytic number theory, computational number theory, and combinatorics.
Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.
A strong pseudoprime is a composite number that passes the Miller–Rabin primality test. All prime numbers pass this test, but a small fraction of composites also pass, making them "pseudoprimes".
In number theory, a Frobenius pseudoprime is a pseudoprime, whose definition was inspired by the quadratic Frobenius test described by Jon Grantham in a 1998 preprint and published in 2000. Frobenius pseudoprimes can be defined with respect to polynomials of degree at least 2, but they have been most extensively studied in the case of quadratic polynomials.
The Baillie–PSW primality test is a probabilistic or possibly deterministic primality testing algorithm that determines whether a number is composite or is a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff.
Gene Howard Golub, was an American numerical analyst who taught at Stanford University as Fletcher Jones Professor of Computer Science and held a courtesy appointment in electrical engineering.
The following tables list the computational complexity of various algorithms for common mathematical operations.
Emma Markovna Lehmer was an American mathematician known for her work on reciprocity laws in algebraic number theory. She preferred to deal with complex number fields and integers, rather than the more abstract aspects of the theory.
In number theory, Gillies' conjecture is a conjecture about the distribution of prime divisors of Mersenne numbers and was made by Donald B. Gillies in a 1964 paper in which he also announced the discovery of three new Mersenne primes. The conjecture is a specialization of the prime number theorem and is a refinement of conjectures due to I. J. Good and Daniel Shanks. The conjecture remains an open problem: several papers give empirical support, but it disagrees with the widely accepted Lenstra–Pomerance–Wagstaff conjecture.
Beresford Neill Parlett is an English applied mathematician, specializing in numerical analysis and scientific computation.
United States 