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