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

댓글

이 블로그의 인기 게시물

Python urllib.parse.quote()

KiCad 시작하기 7 (FreeRoute 사용하기 2)

Forensics .pyc 파일 .py로 복구하기

KiCad 시작하기 2 (PCB 만들기)

Android Compose Hilt

Android Compose Coil library

Python bs4.SoupStrainer()

음악 총보(Score), 파트보(Part)

KiCad 시작하기 4 (기존 회로도 수정 및 추가)

Android GDPR Consent 사용