Concept
Primality test
Related concepts (35)
Fermat primality test
The Fermat primality test is a probabilistic test to determine whether a number is a probable prime. Fermat's little theorem states that if p is prime and a is not divisible by p, then If one wants to test whether p is prime, then we can pick random integers a not divisible by p and see whether the congruence holds. If it does not hold for a value of a, then p is composite. This congruence is unlikely to hold for a random a if p is composite. Therefore, if the equality does hold for one or more values of a, then we say that p is probably prime.
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.
AKS primality test
The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P". The algorithm was the first one which is able to determine in polynomial time, whether a given number is prime or composite and this without relying on mathematical conjectures such as the generalized Riemann hypothesis.
Fermat pseudoprime
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem. Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. For an integer a > 1, if a composite integer x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a. In other words, a composite integer is a Fermat pseudoprime to base a if it successfully passes the Fermat primality test for the base a.
Randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.
Fermat's little theorem
Fermat's little theorem states that if p is a prime number, then for any integer a, the number is an integer multiple of p. In the notation of modular arithmetic, this is expressed as For example, if a = 2 and p = 7, then 27 = 128, and 128 − 2 = 126 = 7 × 18 is an integer multiple of 7. If a is not divisible by p, that is if a is coprime to p, Fermat's little theorem is equivalent to the statement that ap − 1 − 1 is an integer multiple of p, or in symbols: For example, if a = 2 and p = 7, then 26 = 64, and 64 − 1 = 63 = 7 × 9 is thus a multiple of 7.
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.
Carmichael number
In number theory, a Carmichael number is a composite number , which in modular arithmetic satisfies the congruence relation: for all integers . The relation may also be expressed in the form: for all integers which are relatively prime to . Carmichael numbers are named after American mathematician Robert Carmichael, the term having been introduced by Nicolaas Beeger in 1950 (Øystein Ore had referred to them in 1948 as numbers with the "Fermat property", or "F numbers" for short). They are infinite in number.
Composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, or the unit 1, so the composite numbers are exactly the numbers that are not prime and not a unit. For example, the integer 14 is a composite number because it is the product of the two smaller integers 2 × 7. Likewise, the integers 2 and 3 are not composite numbers because each of them can only be divided by one and itself.
Time complexity
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.