오일러의 규준

오일러의 규준 (Euler's Criterion) 은 다음과 같습니다.

임의의 모든 홀수 소수 $p$와 정수 $a$에 대하여 $$ \left( \frac{a}{p} \right) \equiv a^{\frac{p - 1}{2}} \pmod{p} $$ 이다.
$\left( \frac{a}{p} \right)$는 르장드르 기호 입니다.
오일러의 규준 덕분에 $\left( \frac{a}{p} \right)$ 의 값을 소인수분해 같은 것이 필요없이 빠른 거듭제곱법 등으로 $O(\lg p)$ 시간 내로 구할 수 있게 되었습니다. ($\lg x$는 이진로그함수 )
오일러의 규준 증명

우선 페르마의 소정리 를 이용해 $a^{p - 1} \equiv 1 \pmod{p}$부터 시작...
이로부터 $a^{\frac{p - 1}{2}} \pmod{p}$는 $1 \equiv \pmod{p}$이거나 $-1 \equiv \pmod{p}$ 보이기