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. However, note that the above congruence holds trivially for , because the congruence relation is compatible with exponentiation. It also holds trivially for if p is odd, for the same reason. That is why one usually chooses a random a in the interval . Any a such that when n is composite is known as a Fermat liar. In this case n is called Fermat pseudoprime to base a. If we do pick an a such that then a is known as a Fermat witness for the compositeness of n. Suppose we wish to determine whether n = 221 is prime. Randomly pick 1 < a < 220, say a = 38. We check the above congruence and find that it holds: Either 221 is prime, or 38 is a Fermat liar, so we take another a, say 24: So 221 is composite and 38 was indeed a Fermat liar. Furthermore, 24 is a Fermat witness for the compositeness of 221. The algorithm can be written as follows: Inputs: n: a value to test for primality, n>3; k: a parameter that determines the number of times to test for primality Output: composite if n is composite, otherwise probably prime Repeat k times: Pick a randomly in the range [2, n − 2] If , then return composite If composite is never returned: return probably prime The a values 1 and n-1 are not used as the equality holds for all n and all odd n respectively, hence testing them adds no value. Using fast algorithms for modular exponentiation and multiprecision multiplication, the running time of this algorithm is O(k log2n log log n) = Õ(k log2n), where k is the number of times we test a random a, and n is the value we want to test for primality; see Miller–Rabin primality test for details.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (3)

Related courses (3)

Related lectures (11)

Fermat primality test

Primality test

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 (its running time is polynomial in the size of the input).

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.

MATH-489: Number theory II.c - Cryptography

The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how

CS-308: Introduction to quantum computation

The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch

Fermat's Little Theorem: Applications and Probabilities

Explores Fermat's Little Theorem applications and probabilities in primality testing.

Prime Numbers and Primality Testing COM-401: Cryptography and security

Covers prime numbers, RSA cryptography, and primality testing, including the Chinese Remainder Theorem and the Miller-Rabin test.

Prime Numbers and Algorithms

Covers prime numbers, primality testing algorithms, modular arithmetic, and efficient exponentiation methods.