[CryptoHack] Modular Inverting (모듈로 역수)

유한한 필드 Fp 내에서 우리는 요소를 더하고, 곱하고, 항상 필드의 다른 요소를 얻을 수 있다.
필드의 모든 요소 g에 대해 g * d ≡ 1 mod p인 고유한 정수 d가 존재한다.
이것은 g의 곱셈의 역수이다.

(d = 1/g)

 

모듈로 역수의 예시는 다음과 같다.

7 * 8 = 56 ≡ 1 mod 11

 

연습 문제는 다음과 같다.
3 * d ≡ 1 mod 13

mod 13 에서 3*d = 1을 만족하는 수(모듈로 역수)를 찾으면 된다.

이는 3*d % 13 = 1을 만족함을 의미한다.

계산해보면 d는 9이다.

 

파이썬의 inverse 함수로도 구할 수 있다.

from Crypto.Util.number import inverse

print(inverse(3,13))

 

---

레퍼런스

https://cryptohack.org/courses/modular/mdiv/

CryptoHack – Home

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-inverses

모듈로 역수 (개념 이해하기) | 암호학이란? | Khan Academy