Primality test

A procedure that determines whether an integer is prime. Some tests give a definitive answer, while randomized tests can give a small probability of error.

Trial division: A primality-testing method that checks divisibility by candidate factors up to the square root of an integer. It gives a simple deterministic baseline and shows why testing every possible divisor is inefficient.
Modular arithmetic: Arithmetic in which integers are identified by their remainders upon division by a fixed modulus. Most efficient primality tests reduce huge powers to computations modulo the candidate integer.
RSA: A public-key cryptosystem whose security relies on the difficulty of factoring products of large primes. Generating RSA keys requires finding large primes efficiently.
Deterministic algorithm: An algorithm whose execution and output are fixed by its input, without random choices. Deterministic primality tests guarantee the answer, unlike randomized probable-prime tests.
Fermat primality test: A randomized primality test based on Fermat's little theorem and modular exponentiation. Its false positives expose how a fast algebraic test can fail on composite numbers.
Fermat's little theorem: A theorem stating that if p is prime and p does not divide a, then a^(p−1) is congruent to 1 modulo p. It supplies the algebraic condition behind Fermat testing and the probable-prime idea.
Prime generation: The process of producing prime numbers, often by testing randomly selected candidates. Primality tests turn candidate generation into a practical way to obtain cryptographic primes.
Probabilistic algorithm: An algorithm that uses random choices and may have a bounded probability of error. Randomized primality tests gain speed by accepting a controllably small error risk.
Miller–Rabin primality test: A randomized primality test that repeatedly checks whether an integer is a strong probable prime to selected bases. Repeated rounds make its error probability small while keeping the computation efficient.
Euler's criterion: A theorem characterizing quadratic residues modulo an odd prime through modular exponentiation. Its residue test underlies the Solovay–Strassen test.

Linked from 17 pages