**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 GraphSearch.

Concept# Primality test

Summary

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). 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 simplest primality test is trial division: given an input number, , check whether it is divisible by any prime number between 2 and (i.e., whether the division leaves no remainder). If so, then is composite. Otherwise, it is prime. In fact, for any divisor , there must be another divisor , and a prime divisor of , and therefore looking for prime divisors at most is sufficient.
For example, consider the number 100, whose divisors are these numbers:
1, 2, 4, 5, 10, 20, 25, 50, 100.
When all possible divisors up to are tested, some divisors will be discovered twice. To observe this, consider the list of divisor pairs of 100:
Notice that products past are the reverse of products which appeared earlier. For example, and are the reverse of each other. Note further that of the two divisors, and . This observation generalizes to all : all divisor pairs of contain a divisor less than or equal to , so the algorithm need only search for divisors less than / equal to to guarantee detection of all divisor pairs.
Also notice that 2 is a prime dividing 100, which immediately proves that 100 is not prime. Every positive integer except 1 is divisible by at least one prime number by the Fundamental Theorem of Arithmetic. Therefore the algorithm need only search for prime divisors less than / equal to .
For another example, consider how this algorithm determines the primality of 17.

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 lectures (81)

Related publications (3)

Related concepts (55)

Related courses (14)

Prime Numbers and Algorithms

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

Prime Numbers and Primality Testing

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

Local Rings and Minimal Primes

Explores local rings, Noetherian rings, and minimal primes in the context of integral domains.

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.

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.

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.

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

MATH-489: Number theory in 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

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

Since the discovery of the utility of the numbers, the human being tried to differentiate them. We decide between them according to whether they are even or odd. Or, according to the fact that they ar

2006Matthew De Courcy-Ireland, Sandy Lee

We confirm, for the primes up to 3000, the conjecture of Bourgain-Gamburd-Sarnak and Baragar on strong approximation for the Markoff surface modulo primes. For primes congruent to 3 modulo 4, we find