Discrete Logarithm (1) 썸네일형 리스트형 71. Order & Discrete Logarithm 모듈러 산술이 사용되는 이산 구조에서의 추가적인 연산에 대해 알아본다. 서로소인 두 정수 $a, m$와 양의 정수 $k$에 대해 $a^k \equiv 1 \pmod{m}$이고 $k$보다 작은 임의의 양의 정수 $k'$에 대해 $a^{k'} \not\equiv 1 \pmod{m}$일 때 $k$를 모듈러 $m$에 대한 $a$의 위수(Order)라고 하며 기호로는 $\text{ord}_m(a)$로 나타낸다. 오일러 토션트 함수의 성질에 의하면 $a^{\phi(m)} \equiv 1 \pmod{m}$이므로 $a$의 위수 $k$는 $\phi(m)$보다 커질 수 없으며 조금 더 확장하면 $k$는 $\phi(m)$의 약수가 되어야 한다. 모듈러 $m$에 대한 $a$의 위수가 $\phi(m)$일 때 $a$를 모듈러 $.. 이전 1 다음
