Week01 - Code01 분석 with 곱셈 역원(Multiplicative Inverse)

이번에는 Elixir를 활용하여 곱셈 역원(Multiplicative Inverse)라는 것을 구현해볼 예정이다. 사실 이런 용어를 처음 들어보기 때문에 이 개념이 왜 탄생했으며, 어떤 면에서 장점이 있고, 또 실생활에서는 어떻게 사용이 되는지에 대해서 먼저 알아보는 것이 순서라 하겠다. 그래야 하나를 공부해도 왜 공부하는지에 대해 명확하게 인지하고 이해할 수 있기 때문이다.

곱셈 역원(multiplicative inverse)이 뭔가?

곱셈 역원(multiplicative inverse)은 주로 수학, 알고리즘, 암호학 등에서 중요한 개념으로 사용된다. 이 개념은 어떤 수 $�$와 다른 수 $�$가 있을 때, 이 두 수를 곱했을 때 특정 조건을 만족시키는 수 $�$를 찾는 것을 의미한다. 보통은 $�\times �=1$ 또는 $�\times �\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}�$ 같은 조건이다. 즉, a와 t의 결과가 n으로 나눠 떨어지면서 나머지가 1이 되는 어떤 수 t를 찾는 것이다. 말이 너무 어렵다. 그래서 이렇게 개념적으로 접근하면 어려우니 예시를 들어보자.

수학적인 원리까지 가면 너무 깊고, 복잡하니 결론만 따오자. 이렇게 곱셈 역원의 결과가 존재하려면 최대 공약수가 1인 경우만 해당이 된다고 한다. 즉, 최대 공약수가 1이 아닌 경우에는 곱셈 역원이 존재하지 않게된다는 이야기이다. 따라서 최대 공약수(Greatest Common Divisor, gcd)를 통해서 곱셈 역원의 존재여부를 판단해야 한다.

inverse_mod(a, n) = t 라고 할때 곱셈 역원이 존재하는 경우는 아래와 같다.

• inverse_mod(3, 7) = 5
• 우선 gcd로 판별을 하면 3과 7의 최대공약수는 1이므로 곱셈 역원이 존재한다.
• 3 x t를 7로 나눴을 때 나머지가 1인 숫자를 찾는다.
• t = 1 일 경우, 3 x 1 = 3이고, 3 mod 7 = 3
• t = 2 일 경우, 3 x 2 = 6이고, 6 mod 7 = 6
• t = 3 일 경우, 3 x 3 = 9이고, 9 mod 7 = 2
• t = 4 일 경우, 3 x 4 = 12이고, 12 mod 7 = 5
• t = 5 일 경우, 3 x 5 = 15이고, 15 mod 7 = 1
• 즉, t = 5 가 정답이 된다.
• inverse_mod(2, 9) = 5
• 2 x t를 9로 나눴을 때 나머지가 1인 숫자를 찾는다.
• 2 x 5 = 10, 10 mod 9 = 1
• inverse_mod(7, 40) = 23
• 7 x n을 40으로 나눴을 때 나머지가 1인 숫자를 찾는다.
• 7 x 23 = 161, 161 mod 40 = 1
• inverse_mod(5, 11) = 9
• inverse_mod(12, 17) = 10

이번에는 not invertible의 예시를 찾아보자.

• inverse_mod(2, 4)
• 2와 4의 gcd는 2이다. 즉 1이 아니므로 invert가 불가능하다.
• inverse_mod(6, 9)
• 6과 9읠 gcd는 3이다. 즉 1이 아니므로 역시나 inver가 불가능하다.
• inverse_mod(5, 15)

왜 이런 개념이 탄생했나?

• 알고리즘과 계산 복잡성: 곱셈 역원을 알고 있으면, 나눗셈을 곱셈으로 대체할 수 있어 계산 복잡성이 줄어든다.
• 암호학: 공개키와 비밀키의 생성에서 곱셈 역원이 사용된다. RSA 알고리즘은 대표적인 예이다.
• 수학적 엄밀성: 여러 수학적 이론과 알고리즘에 기반을 제공한다.

어떤 면에서 장점이 있는가?

• 계산 효율성: 나눗셈보다 곱셈이 계산적으로 더 효율적이다.
• 암호 안전성: 암호학에서 복잡한 키 생성 메커니즘을 가능하게 해준다.

실생활에서의 활용

• 암호화: 위에서 언급했듯이 RSA나 ECC 같은 암호 알고리즘에서 중요한 역할을 한다.
• 컴퓨터 그래픽스: 특정 변환의 역변환을 찾을 때 사용될 수 있다.
• 코드 이론: 에러 검출 및 수정 알고리즘에 사용된다.
• 경제학: 몇몇 경제 모델에서도 사용되기도 한다.

결론적으로 곱셈 역원은 빠른 속도를 통해 이론적으로나 실제 응용에서나 다양한 분야에 걸쳐 광범위하게 사용되고 있다.

이제 이 Multiplicative inverse라는 개념을 Elixir에서 구현해 보기로 하자.

 

  def inverse_mod(a, n) do

    {g, x, _} = extended_gcd(a, n)

    if g != 1, do: :not_invertible, else: rem(x + n, n)

  end

  defp extended_gcd(0, b), do: {b, 0, 1}

  defp extended_gcd(a, b) do

    {g, x1, y1} = extended_gcd(rem(b, a), a)

    {g, y1 - div(b, a) * x1, x1}

  end

코드의 길이는 그리 길지 않다. Elixir에서도 OCaml에서와 마찬가지로 recursive를 통해서 코드를 구현해서 그렇다.

우선 entry point는 inverse_mod/2 가 된다. 여기서 파라메터로 a와 n을 받게 된다. 그리고 이후에 extended_gcd(a, n) 함수를 호출하여 리턴된 값을 {g, x, _}와 패턴 매칭을 하여 변수 g, x에 넣게된다. 여기서 마지막 리턴값은 _로 무시하라는 얘기이다.

extended_gcd(a, n)은 recursive로 extended_gcd(rem(b, a), a)를 호출하는데, 여기서는 rem(b, a) 즉 b mod a와 a의 최대공약수를 구하게 된다. 여기서 3가지 값이 리턴되게 되는데, g는 x1과 y1의 최대공약수 결과 값이고, x1과 y1은 확장된 유클리드 알고리즘의 중간 계산 결과값을 나타낸다.

유클리드 알고리즘(Eucliden Algorithm)과 확장된 유클리드 알고리즘이란?

유클리드 알고리즘은 최대공약수를 구하는 알고리즘이고, 확장된 유클리드 알고리즘은 여기에 더 나아가 ax + by = gcd(a, b)를 만족하는 x와 y 값도 함께 찾아준다. 이는 현재 우리가 하고 있는 곱셈 역원을 구하는데 필요한 인자들이기 때문에 확장된 유클리드 알고리즘을 이용하는 것이다.

다시 본론으로 돌아와서..

extended_gcd(a, b)는 확장된 유클리드 알고리즘을 계산하는 공식에 의해 최대공약수 g, x1, y1을 구해서 리턴을 하게된다. 그 계산 로직은 여기서 따로 다루지는 않겠다.

이후에 다시 두번째 줄로 돌아와서 그 리턴값에서 gcd인 g 값과 모듈러 역원 값인 x값만 가져온다. 참고로 모듈러 역원은 주어진 숫자를 다른 숫자로 나눈 나머지가 1인 경우를 말한다. 그리고 g 가 1이 아니면(즉, gcd가 1이 아니면 곱셈 역원이 존재하지 않게 되므로 :not_invertible을 뿌려주고, 만약 gcd가 1이라면 rem(x + n, n)을 리턴한다.

여기서 rem(x + n, n)을 사용하는 이유는 x의 범위를 조정하기 위함이다. 즉, 이렇게 하면 항상 0 <= x < n 범위를 유지하게 되기 때문이다.

수학적으로 뭔가 너무 복잡해서 한번에 이해하기가 어려웠다. 만약에 나중에 인터뷰에 이런 유형의 질문이 나올 수도 있기에 그저 상식적인 차원에서 알아두면 좋을것 같다.