[대학원 과제] Extended Euclidean Algorithm(확장 유클리드 호제법)을 이용한 모듈러 역원 구하기 with Java

앞의 포스팅에 앞서서 확장 유클리드 호제법을 이용한 모듈러 역원 구하는 방법을 코드화하였습니다.

<확장 유클리드 호제법 공식 / 28^-1mod75의 예제>

해당 방법을 코드화 하여 구현하였으며

<문제 예시>

과제로 나온 문제 예시는 다음과 같습니다.

이를 Java로 코드화하였을 때,

<결과창>

결과가 올바르게 나온 것을 확인할 수 있습니다.

 

코드는 아래 Repository에 담아 두었습니다.

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

ahrizwell/myRepository

 

물론 연산속도는 확장 유클리드 호제법을 이용하는 것이 훨씬 빠르지만...(현실에서, 시험칠때 특히...)

아래에 포스팅한 방법이 코딩하기는 훨씬 쉽습니다.

 

https://freloha.tistory.com/26

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