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) \)이지만...