Prime numbers are important in modern computing, especially in cryptography, where the security of systems like RSA encryption is based on the difficulty of factoring the product of two large primes. Generating and verifying large primes, which can be hundreds or even thousands of bits long, is critical for creating secure cryptographic keys. However, as numbers grow in size, simple divisibility checks become computationally infeasible, necessitating efficient primality testing algorithms. These algorithms allow computers to quickly distinguish primes from composites and generate new large primes without conducting a thorough search, ensuring that encryption, digital signatures, and secure communications remain both fast and mathematically sound.
The very simple and naive approach to checking primes would be to simply check if your number is divisible by any number less than it. Implementing this in Javascript would give this veryu simple loop.
function CheckPrimeNaive(n){
for (let i = 2; i < n; i++){
if (n % i == 0) return true
}
return false
}
This is VERY inefficient with a time complexity of $O(n)$. With primes used in RSA being $1024$ bits most commonly this would require $2^{1024}$ iterations. That is $\sim1.798\times 10^{308}$ iterations which even at $1$ trillion trillion iterations per second would take about $\sim 3\times 10^{276}$ YEARS which is $\sim10^{266}\times$ longer than the age of the universe. Making it completely unfeasible.
A very simple and easy optimisation is to only iterate up to $\sqrt n$ as if $n$ is composite the smallest prime factor must be $\leq \sqrt n$ This now gives us a time complexity of $O(\sqrt n)$ which is a very good improvement however it is still nowhere near good enough as it would still take $10^{154}$ iterations which at the same speed of $1$ trillion trillion iterations per second would take $\sim 3 \times 10^{138}$ years again nowhere near good enough.
The algorithm would be virtually the same only with a slight change in the condition of the loop.
function CheckPrimeNaive(n){
for (let i = 2; i <= Math.sqrt(n); i++){
if (n % i == 0) return true
}
return false
}
The Fermat Primality Test is an algorithm that can check primes extremely fast however it does not do so with 100% accuracy. Fermat's Little Theorem is a very well known result in number theory which uses Modular Arithmetic which is a system where you only consider the remainder when dividing by a number. For example $1 \equiv 13 \pmod{12}$ this is effectivley say that $1$ and $13$ are equivalent under mod 12 as they both have the same remainder of $1$ when divided by $12$. Think of it like a 12 hour clock. For shameless self promo and a proof of Fermat's little theorem check out my notes on modular arithmetic.
Fermat's Little Theorem states:
Let $p$ be prime and $\gcd(a, p) = 1$, then $$a^{p-1} \equiv 1\pmod {p}$$
If $p$ is prime than any $a$ that satisfies $1 \leq a < p$ will have $\gcd(a,p)=1$
However the converse is not necessasarily true if $a^{n-1}\equiv 1 \pmod{n}$ does NOT mean that $n$ is a prime. But in most cases if n is composite $a^{n-1} \not\equiv 1 \pmod{n}$.
If $n$ is composite and $\gcd(a, n) > 1$ then $a^{n-1}\not\equiv 1 \pmod{n}$. However if $\gcd(a, n) = 1$ then we don't knwow the result. If $a^{n-1}\equiv 1 \pmod{n}$ still holds true and $\gcd(a, n) = 1$ then $a$ is called a Fermat Liar.
On average for a given composite $n$ the percent of numbers $a \in [1, n-1]$ that are fermat liars is $\sim 10\%$. However this can reach up to $50\%$ for normal composite numbers.
And for special composite numbers called Carmichael Numbers where EVERY number $a < n, \ \gcd(a, n) = 1$ is a fermat liar if $n$ is a Carmichael number. However these numbers are extremely uncommon and since $\gcd(a, n) = 1$ is required to be a fermat liar carmicahel numbers can still be caught relatively easily for low numbers as the chance of picking an $a$ that shares a prime factor with the carmichael number is not that low. For numbers used in RSA, numbers in the range $2^{1023} < n < 2^{1024}$ the probality of a carmicheal numer is $1$ in $10^{89}$.
To actual check for a prime we use the contrapositive of Fermat's Little Theorem.
Since Fermat's Little Theorem states $p \text{ prime} \implies a^{p-1} \equiv 1 \pmod{p}$. The contrapositive is $a^{n-1} \not\equiv 1 \pmod {n} \implies n \text{ not prime}$
This means given a number $n$ we can iterate over numbers less than $n$ and check if $a^{n-1}\equiv 1 \pmod{n}$. If it's true we can't say for certain if $n$ is prime as $a$ could be a fermat liar. However if $a^{n-1} \not\equiv 1 \pmod{n}$ we know for certain that $n$ is not prime. After $k$ iterations the probability of a false positive is at most $2^{-k}$ (due to the max chance of Fermat liar being $50\%$) this means after only 20 iterations the chance of a false positive is $<0.0001 \% $ and it only exponentially decreases for each iteration.
// k = number of bases of a used.
// modPow(a,b,c) computes (a^b) % c.
// For very large a, b, c computing a^b then having to a divsion by c is extremely slow.
// So a more optimised algorithm is used that only computes the result.
function IsPrimeFermart(n, k = 5) {
if (n < 2) return false;
if (n === 2 || n === 3) return true;
if (n % 2 === 0) return false;
for (let i = 0; i < k; i++) {
// Pick a random integer a in [2, n-2]
let a = 2 + Math.floor(Math.random() * (n - 3));
// Fermat test: if a^(n-1) % n != 1, n is composite
if (modPow(a, n - 1, n) !== 1) {
return false; // definitely composite
}
}
return true; // probably prime
}
The time complexity of this algorithm is $O(k\cdot(\log n)^3)$ as an exponentiation by repeatedly squaring requires $\log n$ multiplications and using regular multiplication algorithms each multiplication is $O((\log n)^2)$ and we do all of this $k$ times. Using more optimised multiplication algorightms this gets down to $O(k\cdot (\log n)^2\cdot \log\log n \cdot \log\log\log n)$