유한한 필드 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
A fun, free platform to learn about cryptography through solving challenges and cracking insecure code. Can you reach the top of the leaderboard?
cryptohack.org
https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-inverses
모듈로 역수 (개념 이해하기) | 암호학이란? | Khan Academy
수학, 예술, 컴퓨터 프로그래밍, 경제, 물리학, 화학, 생물학, 의학, 금융, 역사 등을 무료로 학습해 보세요. 칸아카데미는 어디에서나 누구에게나 세계 최고의 무료 교육을 제공하는 미션을 가진
ko.khanacademy.org
'background > crypto' 카테고리의 다른 글
[CryptoHack] Legendre Symbol (르장드르 기호) (0) | 2023.07.04 |
---|---|
[CryptoHack] Quadratic Residues (제곱 잉여) (0) | 2023.07.01 |
[CryptoHack] Modular Arithmetic 2 (0) | 2023.07.01 |
[CryptoHack] Modular Arithmetic 1 (0) | 2023.07.01 |
[CryptoHack] Extended GCD (0) | 2023.07.01 |