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 (called pseudoprimes), 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 arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and
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".
SEAC was a first-generation electronic computer, built in 1950 by the U.S. National Bureau of Standards (NBS) and was initially called the National Bureau of Standards Interim Computer, because it was a small-scale computer designed to be built quickly and put into operation while the NBS waited for more powerful computers to be completed. The team that developed SEAC was organized by Samuel N. Alexander. SEAC was demonstrated in April 1950 and was dedicated in June 1950; it is claimed to be the first fully operational stored-program electronic computer in the US.
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.
The following tables list the computational complexity of various algorithms for common mathematical operations.
Emma Markovna Lehmer was a 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.
John David Brillhart was a mathematician who worked in number theory at the University of Arizona.
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 