모듈로 연산(Modulo Operation) 기본

소수 모듈러 (Modular arithmetic)는 정수 계산에서 일종의 나머지 연산이다. 즉, 어떤 정수를 다른 정수로 나눈 나머지를 계산하는 것이다.

 

소수 모듈러 연산은 특히 암호학과 관련된 계산에서 매우 유용하다. 예를 들어, 두 소수 p와 q를 곱한 수 n을 사용하여 RSA 암호화를 할 때, 이러한 연산이 사용된다.

 

보통 소수 모듈러 연산은 mod 연산자로 표시된다. 예를 들어, a mod b는 a를 b로 나눈 나머지를 나타낸다.

 

소수 모듈러 연산은 다양한 수학적 성질을 가지고 있다.

예를 들어 a mod b == c 이고 d mod b = e 이면, (a+d) mod b = (c+e) mod b 이다.

이러한 성질들을 암호학에서 매우 중요하게 사용되며, 특히 공개키 암호 시스템에서는 소수 모듈러 연산을 기반으로 한다.

ex)

12와 8을 5로 모듈러 연산

12 mod 5 = 2

8 mod 5 = 3

(12+8) mod 5 = 0

(2+3) mod 5 = 0

 

 

모듈러 곱셈 역원

소수 p와 p와 서로소인 정수 b에 대해서, b의 p에 대한 모듈러 곱셈 역원은 다음과 같다.

b x b^-1 ≡ 1 (mod p)

여기서 b^-1 는 b의 모듈러 곱셈 역원을 나타낸다.

예를 들어, p = 7, b = 3 일 때, 3의 7에 대한 모듈러 곱셈 역원을 구해보자.

먼저, 3,6,9,12,15,... 등 3의 배수를 7로 나눈 나머지를 구해보면 다음과 같다.

3 mod 7 = 3

6 mod 7 = 6

9 mod 7 = 2

12 mod 7 = 5

15 mod 7 = 1

따라서, 3x5 ≡ 1 (mod 7) 이므로, 3의 7에 대한 모듈러 곱셈 역원은 5가 된다.

 

음수일 때 모듈러 연산

예를들어, -5를 3으로 모듈러 연산하고자 하는 경우

-5 mod 3 -> (-5) mod 3 +3 = -2 + 3 = 1

따라서, -5를 3으로 모듈러 연산한 결과는 1이 된다.

 

모듈러 합동

두 수가 같은 나머지를 갖는지를 나타내는 개념이다.

만약 야의 정수 a,b,n에 대해서 a와 b가 n으로 나누어졌을 때 나머지가 같다면, 즉 (a mod n) = (b mod n) 이라면, 다음과 같이 표현할 수 있다.

a ≡ b (mod n)

이를 'a는 b와 모듈러 n에 대해서 합동이다' 라고 해석한다.

예를 들어 14 ≡ 2 (mod 4)

 

페르마의 소정리는 소수 p와 p와 서로소인 정수 a에 대해서 다음과 같은 성질을 가지는 정리이다.

a^(p-1) ≡ 1 (mod p)

즉, a^(p-1)를 p로 나눈 나머지는 1과 같다는 것을 의미한다. 이때 a는 p의 배수가 아니어야 한다.

a x a^(p-2) ≡ 1 (mod p)이므로 a^(-1) ≡ a^(p-2) (mod p)