[대학원 과제] 모듈러(Modulo, %)의 역원 구하는 프로그램 with Java

이번에는 모듈러의 역원을 구하는 문제가 과제로 나왔습니다.

원래 모듈로의 역원을 구하기 위해서는 1) 유클리드 호제법, 그리고 이를 확장한 2) Extended 유클리드 호제법, 그 후 3) Multiplicative Inverse 를 배우고 구하는 방식을 권고(?)하고 있습니다.

하지만 생각해보니 단순히 모듈러의 역원을 구하는 것이라면, 위 방식을 응용한 방법을 사용하는 것이 좋다고 생각하여 알고리즘들을 찾아보았습니다. 원래 네트워크 암호학 배울 때 다 그렇지만 시험기간이 다가올수록 꼼수(?)를 사용하여 한방에 구할 수 있는 공식 혹은 알고리즘을 만들어 시험장에 가는게 정석(?)이기 때문이죠. 

참고로, 구하는 속도 측면에서는 확장된 유클리드 호제법을 이용한 Multiplicative Inverse를 이용해 구하는게 훨씬 빠릅니다. 다만, 이를 코드화 하는게 너무 복잡(이라 쓰고 귀찮다)하기 때문에 단순한 방법을 찾고 있었습니다.

그러던 와중,

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-inverses

모듈로 역수 (개념 이해하기) | 암호학이란? | 칸아카데미

위 방법은 장단점이 있는데

장점

- 코드화 하기 쉽다(컴퓨터를 사용할 시)

단점

- 현실에서(시험장에서) 쓰면 한문제풀다가 시험이 종료될 수 있다. 값이 커지면 일일히 다 연산하기 좀...

- 비효율적이다

 

이를 발견하였고, 논리 자체는 매우 쉬웠기 때문에 코드화하였습니다.

나중에 시간이 된다면 확장된 유클리드 호제법을 이용한 모듈러 역원 구하는 코드도 구현할 생각입니다.

 

https://github.com/ahrizwell/myRepository/blob/java/inverseModulo.java

ahrizwell/myRepository

코드는 위 주소에 포스팅해두었습니다.

 

결과값

<코드와 결과창>

<확장된 유클리드 호제법을 이용한 계산과 결과대조>