Algorithm Get modular inverse value
알고리듬 Get modular inverse value를 알아보겠습니다.
나머지 연산 역원을 구하기 위한 전제 조건이 필요합니다.
A mod M에서 A와 M이 서로소여야 합니다.
유클리드 호제법으로 다음 식이 성립합니다.
그리고 확장 유클리드(Extended Euclidean algorithm)와 혼합하면 다음과 같이
표현됩니다.
두 식은 동일하므로 x와 x1, y와 y1과의 관계로 표현하면 다음과 같이 됩니다.
이것을 코딩으로 표현하면 됩니다.
(7 mod 25)^-1 결과는 18이네요.
카테고리: Algorithm
댓글
댓글 쓰기
궁금한 점은 댓글 달아주세요.
Comment if you have any questions.