12. Primality Tests

Prime number theorem: $\pi (x):=|\{n\in \mathbb{N}\mid n\le x,n\text{ prim}\}|$ $\sim \frac{x}{\ln x}$

GCD

• We can calculate the gcd in $\log n$ time using Euclid’s algorithm
• If $n$ is prime, then $\gcd (n,a)=1$ $\forall a<n$
• Pick a random $a$ and test

Not polynomial time b/c need exponentially many trials

Fermat

• If $n$ is a prime number, then ${\mathbb{Z}}^{\ast }=$ all nums $<n$ $⟹|{\mathbb{Z}}^{\ast }|=n-1$
• Chose $a<n$ randomly. $a\in {\mathbb{Z}}^{\ast }$ $⟹$ $a$ has some $\mathrm{ord}(a)$. By Lagrange: $\mathrm{ord}(a)\mid |{\mathbb{Z}}^{\ast }|$ $⟹$ $a^{n-1}=1$
• If $a^{n-1}\mathrm{mod}n=1$: return prime. Using iterative squaring, we can calculate that $\log n$

Correctness:

• If $n$ prime: always correct
• If $n$ not prime: Wrong answer with prob $\le 0.5$ unless $n$ is Carmichael num

Pseudo-prime bases: $P{B}_n:=\{a\in [n-1]\mid a^{n-1}{\equiv }_{n}1\}$ $=\{a\in {\mathbb{Z}}_n^{\ast }\mid a^{n-1}{\equiv }_{n}1\}$ ($\in {\mathbb{Z}}_n^{\ast }$ implies by condition)

$a^{n-1}{\equiv }_{n}1\wedge b^{n-1}{\equiv }_{n}1$ $⟹$ $a^{n-1}\cdot b^{n-1}{\equiv }_{n}1$ $⟹$ $(ab{)}^{n-1}{\equiv }_{n}1$ $⟹$ $P{B}_n$ is subgroup of ${\mathbb{Z}}_n$ (so Lagrange applies!)

Def. Carmichael nums: $n$ not prime and $P{B}_n={\mathbb{Z}}_n^{\ast }$

Correctness:

• If $n$ prime: Output always correct
• If $n$ not prime: Output correct with Prob $\frac{|{\text{PB}}_n|}{n-1}\le \frac{1}{2}$ (since $P{B}_n$ must divide $|{\mathbb{Z}}^{\ast }|$ $=n-1$) unless $n$ Carmichael

Miller-Rabin Certificate

Assume that $n$ is uneven (trivial to check)

Lemma

$n-1=2^{k}d$ with $k,d\in \mathbb{N}$ and $d$ uneven. If $n$ prime and $a\in [n-1]$:

$$a^d{\equiv }_{n}1\text{or}\exists i\in \{0,1,\dots ,k-1\}:a^{2^{i}d}{\equiv }_{n}n-1$$

Procedure:

• Chose $a\in [n-1]$ uniformly randomly
• Check if condition in $\mathcal{O}(\log n)$
• Return prime if met, else not prime

Ex. Carmichael Num 561

• $2^{560}{\equiv }_{561}1$
• $2^{280}{\equiv }_{561}1$
• $2^{140}{\equiv }_{561}67$ $⟹$ 2 is Miller-Rabin Certificate for 561 not prime

Correctness:

• If $n$ prime: always correct
• If $n$ not prime: wrong answer with probability $\le \frac{1}{2}$ (even $\le \frac{1}{4}$)