Resume
Research
Learning
Blog
Teaching
Jokes
Kernel Papers

# Primality Testing

Suppose we want to know whether $$n$$ is prime. From Fermat’s little theorem for polynomials we know that $$\forall x \in \mathbb{Z}_n^*$$, $$x^{n-1} = 1 \mod n$$. This suggests the following algorithm:

## Algorithm

Given an $$n$$, choose $$x \in \{1, ..., n-1\}$$ uniformly at random. If $$x^{n-1} = 1 \mod n$$, output “prime”. Otherwise, output “composite”.

This will always work on prime numbers, but fail on Carmichael numbers (i.e. composite natural numbers such that \forall x \in \mathbb{Z}_n^*, x^{n-1} = 1 \mod n).

## Analysis

Theorem: Suppose $$n$$ is composite, but not a Carmichael number. Then the probability Fermat’s test outputs “composite” is $$\geq 1/2$$.

Proof:

Case 1: $$gcd(n, x) \neq 1$$. Then $$x^{n-1} \neq 1 \mod n$$. Why? Because if $$x^{n-1} = 1 \mod n$$, then $$x^{n-1} = nc + 1$$ for some $$c$$, and $$gcd(x,n)$$ can divide the LHS and $$nc$$, but thus cannot divide $$nc + 1$$. Thus the algorithm will always detect $$n$$ as composite.

Case 2: $$gcd(x, n) = 1$$. Then let $$H = \{ x: x\in \mathbb{Z}_n^*, x^{n-1} = 1 \mod n\}$$. Note that $$H \subseteq \mathbb{Z}_n^*$$ and $$H \neq \mathbb{Z}_n^*$$ since $$n$$ is not a Carmichael number. Thus per Lagrange’s Theorem, $$|H| \leq \frac{1}{2} |\mathbb{Z}_n^*|$$. Thus the probability $$n$$ is identified as composite is at least 0.5.