Pépin's test

페르마 수의 primality test에 Miller - Rabin을 쓰면 어떨까? 라는 생각에서 기존 이론을 search하다가 찾아낸 이론인데, 생각해보니 옛날에 배웠던 거다... 그럼 그렇지.

$$F_n = 2^{2^n} + 1 \text{ is prime} \\ \Leftrightarrow 3^{\frac{F_n-1}{2}} \equiv -1 (\text{mod} \ F_n) (n>0)$$

pf)

$\Rightarrow)$

$\text{by Euler's Criterion,}$

$3^{{F_n-1}/2} \equiv \left(\frac{3}{F_n}\right)$

이 때 $F_n \equiv 2 (mod 3)$이므로 $F_n$은 법 3에 대한 이차잉여가 아니다. 

$\left(\frac{F_n}{3}\right) = -1$

$\left(\frac{p}{q}\right) \cdot \left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}$ (이차 상보성 법칙) 이고,

$F_n \equiv 1 (\text{mod }4)$이므로

$\left( \frac{3}{F_n} \right) = 1 \cdot \left(\frac{F_n}{3} \right) = -1 \blacksquare$

$\Leftarrow)$

$3^{\frac{F_n-1}{2}} \equiv -1$

$\Rightarrow \text{ord}_{F_n}(a) \not{|} \frac{F_n-1}{2}$

$\Rightarrow \frac{F_n-1}{2} | \text{ord}_{F_n}(a) | \phi (F_n)$

$\Rightarrow \phi(F_n)  = F_n -1 \Rightarrow F_n \text{ : prime} \blacksquare$

나름 현재 알려진 Fermat's number primality test 중에는 가장 빠르다고 한다. 그래봤자 $\Omega(n \cdot 2^n)$이지만...