[ 알고리즘 ] 모듈러 연산(Modular Arithmetic)

오늘은 모듈러 연산에 대해 설명드리겠습니다. 특정 수 M을 넘는 수에 모듈러 연산을 하려면 어떻게 해야 할까요?

 

모듈러 연산의 특성을 활용하면 쉽게 구할 수 있습니다.

 

[ 동작 원리 ]

 

정수 A와 B를 M으로 나눈 나머지를 각각 a, b라고 한다면, 이때 A+B를 M으로 나눈 나머지는 얼마일까요?

 

A = xM + a

B = yM + b

A + B = (x + y)M + (a + b)

(A + B)%M = (a + b)%M

 

따라서, (A + B)%M = ((a%M) + (b%M))%M이라는 결과가 나옵니다. 이러한 성질은 덧셈, 뺄셈, 곱셈에 모두 성립합니다.

 

하지만 음수에 모듈러를 적용하면 다음과 같은 결과가 나옵니다.

 

-9 % 11 = 2

-5 % 11 = 6

-23 % 11 = 10

=>

(23%11) = 1

-1 + 11 = 10

 

따라서 음수는 양수로 바꾼 값을 M으로 나눈 값을 다시 음수로 바꿉니다. 그 후 그 값에 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