_Posted on June 04, 2025_ ##### Introduction Given an integer, how do we determine if it is prime? To solve this problem, lets first recall the definition of a prime number: > [!definition] An integer $p \neq \pm 1$ is prime if the only integers which divide $p$ are $\pm 1$ and $\pm p$. Given this definition, we may devise a few algorithms called _primality tests_. Such algorithms, when given an integer $n$ as input, determine whether $n$ is prime. These algorithms are very useful in modern cryptosystems such as [[RSA]], which rely on finding (i.e. generating) very large prime numbers quickly. ##### Deterministic Primality Test (Trial Division) A natural primality test arising from the above definition would be to find all of the divisors of $n$. If the only divisors are $1$ and $n$ itself, then clearly $n$ is prime. One of the most basic primality tests, known as _trial division_, does something like this. In trial division, we consider all integers $k$ where $2 \leq k \leq \lfloor \sqrt n \rfloor$ and check whether they are divisors of $n$ (i.e. whether $k \mid n$). The reason we do not check any integer greater than $\lfloor \sqrt n \rfloor$ is that if $a > \lfloor \sqrt n \rfloor$ and $b > \lfloor \sqrt n \rfloor$, then $a \cdot b > n$. By the law of trichotomy, $a \cdot b \neq n$, implying that $a \nmid n$ and $b \nmid n$ (i.e. neither $a$ nor $b$ is a divisor of $n$). Therefore, one of $a$ or $b$ must be less than or equal to $\lfloor \sqrt n \rfloor$ to be a divisor of $n$. Additionally, we consider only the odd $k$ for $2 < k \leq \lfloor \sqrt n \rfloor$, since if $2$ is not a divisor of $n$, then no other even integer will be a divisor of $n$. To check whether $k$ is a divisor of $n$, we can use an [[Integer Division Algorithms|integer division algorithm]] to find the remainder $r$ of $n$ after division by $k$. If $r \neq 0$, then $k \nmid n$. If $k \nmid n$ for all the considered $k$, then we know that $n$ is prime. Sample code for the trial division test is implemented in [[SICP Exercise 1.22]] and [[SICP Exercise 1.23]]. ##### Probabilistic Primality Test (Fermat Primality Test) Interestingly, trial division is _deterministic._ That is, if $n$ is prime, trial division will definitely determine this. On the other hand, there are several non-deterministic primality tests, which return probabilistic results. The _Fermat primality test_ is one such test. The Fermat primality test test relies on the results of [[Fermat's Little Theorem]]: ![[Fermat's Little Theorem#^4baa36]] This implies that, given an integer $n$, if we find an integer $a$ where $1 < a < n$ such that $[a^{n-1}] \neq [1]$, then we know that $n$ is composite. We say that $a$ is a witness of the fact that $n$ is composite. It can be shown that most composite numbers have around at least $n/2$ such witnesses #TODO (NFTA ex2.20). As a result, if we choose $m$ integers between $1$ and $n$, then we will find a witness to $n$ with a probabilty of $1 - (1/2)^m$. To test whether an integer $a$ is a witness to $n$, we compute $a^{n -1}$ and find its remainder $r$ after division by $n$, using a [[Integer Division Algorithms|integer division algorithm]]. If $r \neq 1$, then $a$ is a witness. If none of these $m$ integers is a witness, then $n$ is prime with probability $1 - (1/2)^m$. This algorithm is implemented in [[SICP Exercise 1.24]].