모듈러 연산 (Modular arithmetic)

암호 알고리즘은 모듈러 연산을 가장 빈번하게 사용하는데, mod m일때, 항상 0 ~ m의 범위를 가지는 값을 결과 값으로 가지게 된다.

만약 음수의 결과 값을 가진다면 절대 값을 취한 값에서 mod를 한 결과를 m을 더하거나 m을 2배, 3배한 값을 더해 0 ~ m의 범위의 결과 값을 가지도록 하면 된다.

모듈러 연산의 예시
17 mod 5 = 2
20 mod 3 = 2

음수일 때
-3 mod 11 = 8
-11 mod 11 = 0
-1 mod 11 =10

 

모듈러 합동(Modular congruent)

두 a, b의 숫자가 n을 modular한 결과 값이 같다면 모듈러 합동관계(congruent modulo n)이라고 한다.

$$ a\ mod\ n\ =\ b\ mod\ n\ $$

$$ a\ ≡\ b\ mod\ n $$

합동관계를 쉽게 알아낼 수 있는 방법이 존재한다.

mod n에 대해 a-b = kn 일때 a와 b는 합동(Congruent)관계이다.
(k는 상수)

예를들어 73과 4가 mod 23에 대해 합동관계이면 73-4 = 69 (23 * 3)으로 표시할 수 있고 k의 값이 3을 뜻한다.

$$ a\ ≡\ 9\ ≡\ 14\ ≡\ 19\ ≡\ -1\ ≡\ -6\ mod\ 5 $$

 

모듈러 연산의 특징(Properties of modular arithmetic)

모듈러 연산은 3가지의 특징을 가지고 있다.

$$ 1. (a\ mod\ n\ +\ b\ mod\ n)\ mod\ n\ =\ (a\ +\ b)\ mod\ n $$

$$ 2. (a\ mod\ n\ -\ b\ mod\ n)\ mod\ n\ =\ (a\ -\ b)\ mod\ n $$

$$ 3. (a\ mod\ n\ *\ b\ mod\ n)\ mod\ n\ =\ (a\ *\ b)\ mod\ n $$

예제로 모듈러 연산의 덧셈에 대한 특징이다. 예를들어 11 mod 8과 15 mod 8을 더한다고 하자.

$$ (11\ mod\ 8\ +\ 15\ mod\ 8)\ mod\ 8\ =\ 10\ mod\ 8\ =\ 2 $$

덧셈의 특징에 의해 위의 식으로 두 연산의 덧셈을 구할 수 있다.

 

모듈러 연산 특징을 이용해 지수 구하기(Exponentiation)

모듈러 연산에 대해 수학 식을 풀다보면 지수(Exponentiation) 형태를 가진 식이 종종 등장한다.

그때마다 계산기로 거듭제곱을 하다보면 시간이 오래걸리고 비 효율적이다.

하지만 위에서 배운 모듈러 연산의 특징을 이용한다면 간단하게 해결할 수 있다.

$$ 11^{7}\ mod\ 13을\ 구한다고\ 하자 $$

$$ 11^{2}\ =\ 121\ ≡\ 4\ (mod\ 13) $$

$$ 11^{4}\ =\ (11^{2})^{2}\ ≡\ 4^{2}\ ≡\ 3\ (mod\ 13) $$

$$ 11^{7}\ ≡\ 11*4*3\ ≡\ 132\ ≡\ 2\ (mod\ 13) $$

모듈러 연산의 곱셈 특징을 이용하면 위의 식처럼 더 간편하게 구할 수 있다.

 

모듈러 나눗셈(Modular Division)

만약 나눗셈 형태(역수, 분수형태)를 가진 모듈러 식이 나온다면 난감해진다.

위의 특징을 이용해 풀 수도 없고 소수점을 구하기도 애매한 상황이 된다.

이때 모듈러 나눗셈을 이용하면 된다.

$$ \cfrac{5}{3}\ mod\ 11을\ 구한다고\ 하자 $$

위 식을 구하기 위해서는 3의 역원을 구해주면 된다.

그러기 위해선 3을 1로 만들어 주는 t를 구하면 된다.

$$ 3*t\ mod\ 11\ =\ 1 $$
$$ 3*4\ mod\ 11\ =\ 1 $$

따라서 3의 역원은 4의 값을 가지게된다.

$$ \cfrac{5}{3}\ mod\ 11\ =\ 5*4\ mod\ 11\ =\ 9\ mod\ 11 $$