algorithm
유클리드 호제법, 모듈로 역원
fungod
2022. 8. 3. 16:14
이 사이트에 설명이 잘 되어있고 공부하기 쉽다.
유클리드 호제법 (개념 이해하기) | 모듈로 연산 | Khan Academy
ko.khanacademy.org
추가로 볼 만한 자료
컴파일러는 정수 나눗셈을 어떻게 최적화 할까?
modoocode.com
A ≡ B(mod C) 인 것은 즉 A mod C = B mod C , A와 B는 값이 같은 동치류
동치관계 : 반사성, 대칭성, 추이성
성질 :
(A+B) mod C = (A mod C + B mod C) mod C
(A-B) mod C = (A mod C - B mod C) mod C
(A * B) mod C = (A mod C * B mod C) mod C
A^B mod C = ((A mod C)^B) mod C
모듈로 역원 :
ax ≡ 1 (mod m)
1) m이 소수이면 a^(m-2)
2) 아니면, ax+ by = 1 을 만족시키는