[정보보안] Multiplicative Inverse(곱셈역)

[정의]

$Zn$에서 $(a*b)\mod n = 1 $이면 $a, b$는 곱셈역 관계이다. 

 

[구하는 방법 3가지]

1. 노가다로 구하기

2. 페르마의 소정리를 이용하기

3. extended euclid algorithm 사용하기

 

 

 

 

ex)

[Q] Z10에서 모든 곱셈역을 찾아보자. 

[A]

Z10 = {0, ..., 9}

(3, 7), (1, 1), (9, 9)

 

[Q] Z11에서 모든 곱셈역을 찾아보자.

[A]

Z11 = {0, ..., 10}

(1, 1), (2, 6), (3, 4), (5, 9), (7, 8), (10, 10)

 

그러면 Zn에 들어있는 b가 곱셈역을 가지고 있는지 어떻게 알 수 있을까?

b * (Zn에 들어있는 수) == n * 임의의 수 + 1인지 확인해도 되겠지만...

 

gcd(n, b) = 1, 즉 n과 b가 서로소이면 무조건 곱셈역이 존재한다. 

 

앞에서 배운 Extended Euclidean Algorithm을 이용해서 이를 증명해보자.

 

 

[증명]

 s x a + t x b = gcd(a, b) 를 만족하는 s,t 를 동시에 구해주는게 Extended Euclidean Algorithm이었다. 

 

a를 n으로 대체하면,  s x n + t x b = gcd(n, b) = 1이다. 

 

sn + tb = 1 이니까  양변에 mod n을 취해주면, (sn + tb) mod n = 1 mod n 이다. 

 

(a+b) mod n = ((a mod n) + (b mod n)) mod n 인 modular의 성질에 의해서, 

 

(sn mod n) + (tb mod n) = 1이다. 근데 sn mod n은 0이니까 tb mod n 은 1이다. 

 

그러므로 t는 Zn에서 b의 곱셈 역이다. 

 

 

[Zn*의 등장]

Zn이 덧셈역을 구할 때 쓰인다면, Zn*는 곱셈역을 위한 집합이라고 생각하면 될 것 같다. 

 

Z6 = { 0, 1, 2, 3, 4, 5 }

Z6* = { 1, 5 }

 

Z7 = { 0, 1, 2, 3, 4, 5, 6 }

Z7* = { 1, 2, 3, 4, 5, 6 }

 

n이 소수이면 Zn*는 전체 집합일 수 밖에 없다. 어느 수이든 gcd(a, n)이 1일거니까...

n이 소수이면  Zp = Zp* + {0} 이다. 

 

[Zn* 갯수 쉽게 구하기]

오일러의 phi-function의 개수와 Zn*의 개수가 같다. 내용물은 다 구하지는 못하지만 이걸로 개수라도 빠르게 구할 수 있으면 좀 편하지않을까 싶당!