유클리드 호제법, 모듈로 역원

이 사이트에 설명이 잘 되어있고 공부하기 쉽다.

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

유클리드 호제법 (개념 이해하기) | 모듈로 연산 | Khan Academy

https://modoocode.com/313

추가로 볼 만한 자료

컴파일러는 정수 나눗셈을 어떻게 최적화 할까?

 

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 을 만족시키는