정보보호이론에서 알아두어야할 공식

정보보호 이론을 공부하기 위해선 몇가지의 공식과 연산 방법들을 알아두어야 한다. 

최대공약수, 모듈로 연산, 오일러 정리 등일 기본적으로 알아야 한다. 

아래에는 그러한 연산들에 대해 설명되어 있다.

1. 최대공약수 (GCD)

위의 연산은 훗날 최대공약수가 1인 수를 구하기 위해 필요하다.

지금은 최대공약수가 7이라서 이 수는 쓸모가 없다.

나중에 최대공약수가 1인 두 수를 구해야할 것이다.

2. 모듈로 연산 (mod)

어떠한 수로 나누었을 때 나머지를 구하는 연산이다.

위의 연산은 27을 26으로 나누면 1이 나옴을 보여준다.

이는 0보단 크고 m보단 작은 수의 집합를 말한다.

이는 0보단 크고 m보단 작은 수 중에서 

m과 최대공약수가 1인 수의 집합을 말한다.

수를 | x | 로 감싸면 개수를 의미한다.

구하는 방법은 

m을 소수의 곱셈으로 만들어 각 소수의 -1 한 값을 모두 곱하면 개수가 된다.

이해가 되지 않으면 위의 그림을 보면 된다.

이를 이해하기 위해선 아래의 정리들을 이해해야 한다.

따라서 이해하기 싫으면 위까지만 암기하면 된다.

3. 알아두어야할 정리들

1) 덧셈의 역원

일 경우 b는 덧셈에 관한 a mod m 의 역원이 된다.

2) 곱셈의 역원

일 경우 b는 곱셈에 관한 a mod m의 역원이 된다.

예제는 다음그림과 같다.

3) 기타 알아두어야할 정리

정리1) 

정리2)

4) 큰 수에 대한 모듈로 연산 방법

만약 2^100 mod 11을 구하라고 한다면 이렇게 큰 수에 대해선 어떻게 구해야할까.

아래에 그에 대한 풀이가 있다.