**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Fermat primality test

Summary

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.

Official source

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 publications (8)

Related concepts (2)

Related courses (3)

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.

Related lectures (11)

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

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.

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed p ...

This dissertation explores techniques that synthesize and generate program fragments and test inputs. The main goal of these techniques is to improve and support automation in program synthesis and test input generation. This is important because performin ...

Martin Vetterli, Amin Karbasi, Ali Hormati, Mahdi Cheraghchi Bashi Astaneh

Identification of defective members of large populations has been widely studied in the statistics community under the name of group testing. It involves grouping subsets of items into different pools and detecting defective members based on the set of tes ...