[종만북] 모듈라 연산 / 정수론

[종만북] 모듈라 연산 / 정수론

[종만북] 모듈라 연산 / 정수론

 

모듈라 연산 (Modular Arithmetic)

• 모듈라 M 에 도달 하면, 다시 0으로 돌아가는 정수들로 하는 연산
• 모듈라 연산에서 모든 정수는 M 으로 나눈 나머지로 표현됨
  • ex) 시계

 

 

모듈라 덧셈

• 두 수의 합의 모듈라 연산은, 두 수의 모듈라 연산 결과의 합과 같다.
• (a + b) % M = (a' + b') % M

a % M = a' , b % M = b' -> (a + b) % M = ?

a = Mx + a' , b = My + b'

(a + b) = (Mx + a') + (My + b') = M(x+y) + ( a'+b')

(a + b) % M = ( M(x+y) + a' + b') % M = (a' + b') % M
-> (a + b) % M = (a' + b') % M

 

덧셈/뺄셈/곱셈 모두 적용됨

• (a + b) % M = ((a % M) + (b % M)) % M
• (a - b) % M = ((a % M) - (b % M) + M) % M
• (a * b) % M = ((a % M) * (b % M)) % M

 

 

 

모듈라 연산의 나눗셈

• 모듈라 연산에서의 나눗셈 a/b는 b로 나누는 대신 b의 곱셈 역원(multipli­ cative inverse)을 곱하는 방식
• b의 곱셈 역원은 항상 존재 하는 것이 아니라， b가 M과 서로소일 때만 존재
• 모듈라 연산의 나눗셈은 일반적인 알고리즘 범위를 벗어나는 수학적인 문제