모듈러 연산(Modular Arithmetic)

<모듈러 연산(Modular Arithmetic)>
- 앞 절에서 논의된 나눗셈 관계식 (a = q*n+r)은 두 개의 입력값 (a, n)과 두 개의 출력값 (q, r)을 가진다
- 모듈러 연산에서는 하나의 결과 값, 즉 나머지 r에만 관심이 있고 몫 q는 신경쓰지 않는다
- 이진 연산자를 모듈러 연산자라고 하고, mod로 표기한다
- 두 번째 입력값(n)은 모듈러(Modulus)라고 하고, 결과값 r은나머지(Residue)라고 한다


<잉여류(Set of Residues)>
- 모듈러 n을 이용하는 모듈러 연산의 결과는 항상 0과 n-1사이의 정수 값
  즉, a mod n의 결과값은 항상 n보다 작은 음이 아닌 정수 값이 된다
- 모듈러 연산자는 하나의 집합을 생성하는데, 모듈러 연산에서 이 집합을 모듈러 최소 잉여 집합 또는 Zn이라고 한다
- 두 정수가 합동(Congruence)임을 보이기 위해서는 합동 연산자( )를 사용한다



<Zn에서의 연산(Operation in Zn)>
- 집합 Z에서의 논의했던 세 개의 이진 연산자(덧셈, 뺄셈, 곱셈)역시 집합 Zn에 정의될 수 있다
- 세 개의 이진연산(+, - *)를 적용하기 전에, (Z에서 선택되었다면) 두 입력 값을 Zn에 우선 대응시킬 수 있도록 해준다
  1. (a+b) mod n = [(a mod n) + (b mod n)] mod n
  2. (a-b) mod n = [(a mod n) - (b mod n)] mod n
  3. (a*b) mod n = [(a mod n) * (b mod n)] mod n

- 정수론에서, 정수를 3으로 나눈 나머지는 그 정수의 각 자리수의 합을 나눈 나머지와 같다고 한다
  정수를 10의 지수승와 각 자리 수를 곱한 것의 합으로 표현한다



<덧셈에 대한 역원(Additive Inverse)>
- 모듈러 연산을 할 떄, 종종 연산에 대한 어떤 수의 역원을 계산해야하는 경우가 있는데
  일반적으로 덧셈에 대한 역원과 곱셈에 대한 역원을 계산한다
- 모듈러 연산에서, 각각의 정수는 덧셈에 대한 역원을 가진다
  어떤 정수와 그 정수의 덧셈에 대한 역원의 합은 모듈러 n에 대하여 0과 합동이다
  *덧셈에 대한 항등원(Identity) a + 0 = a
  *곱셈에 대한 항등원 a * 1 = a
   
  *덧셈에 대한 역원 a + ( ) = 0
  *곱셈에 대한 역원 a * ( ) = 1



<곱셈에 대한 역원(Multiplicative Inverse)>
- 모듈러 연산에서, 정수는 곱셈에 대한 역원이 있을 수도 있고 없을 수도 있다
  만약 곱셈에 대한 역원이 있다면, 그 정수와 해당하는 곱셈에 대한 역원의 곱은 모듈러 n에서 1과 합동이다
- 확장 유클리드 알고리즘을 이용하면, n과 b가 주어지고, gcd(n, b) = 1일 때, Zn에서 b의 곱셈에 대한 역원을 찾을 수 있다



<다른 두 집합(Different Sets)>
- 덧셈에 대한 역원이 필요할 때는 Zn을 사용해야 하지만,
  곱셉에 대한 역원이 필요할 때는 Zn*을 사용해야 한다
- 암호는 종종 두 개 이상의 집합, 즉 Zp와 Zp*를 사용한다 
  - 이 두 집합(Zp, Zp*)에서 모듈러는 소수이다