Processing math: 100%

본문 바로가기

Discrete Logarithm

(1)

71. Order & Discrete Logarithm 모듈러 산술이 사용되는 이산 구조에서의 추가적인 연산에 대해 알아본다. 서로소인 두 정수

$a, m$ 와 양의 정수

$a^k \equiv 1 \pmod{m}$ 이고

$k$ 보다 작은 임의의 양의 정수

$k'$ 에 대해

$a^{k'} \not\equiv 1 \pmod{m}$ 일 때

$k$ 를 모듈러

$a$ 의 위수(Order)라고 하며 기호로는

$\text{ord}_m(a)$ 로 나타낸다. 오일러 토션트 함수의 성질에 의하면

$a^{\phi(m)} \equiv 1 \pmod{m}$ 이므로

$k$ 는

$\phi(m)$ 보다 커질 수 없으며 조금 더 확장하면

$k$ 는

$\phi(m)$ 의 약수가 되어야 한다. 모듈러

$a$ 의 위수가

$\phi(m)$ 일 때

$a$ 를 모듈러 $..

티스토리툴바