소수 모듈러 (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)
댓글