오일러의 규준

II-eugene-II Note

Home Math Code

오일러의 규준

오일러의 규준 (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}$ 보이기