Introduction to Primality Test A primality test is an algorithm that checks if a number is prime. Given an integer n, it returns n is prime or composite. For small numbers, a simple approach would be using trial division, which tries to divide n by every integer up to $\sqrt{n}$. However, this kind of test becomes impractical when n contains hundreds of bits or more, which is common in fields like cryptography. ...