728x90
modular inverse
에 대한 설명은 다음 포스트 참고...
2024.01.16 - [study/수학&암호] - [CryptoHack] Extended GCD
[CryptoHack] Extended GCD
베주 항등식 (Bezout's Identity) 두 정수의 최대공약수를 원래 두 수의 배수의 합으로 나타낼 수 있다. 이때 x 와 y 는 베주 계수(Bezout coefficient)라고 한다!! 정리하자면 GCD(a, b) = d라고 할 때, - ax + by = d
lucykorea414.tistory.com
퀴즈)
3 mod 13의 inverse를 구하라~
역수가 일단 존재하기 위해서는 3과 13이 서로소여야 한다!! (즉, gcd가 1 이어야 함)
-> 3과 13은 서로소 O
그러면 오일러 확장 호제법(베주 항등식)을 통해서 구할 수 있는데
이 식을 활용하면
이렇게 풀 수 있을듯??
그럼 전에 했던 베주항 계수 찾는 문제랑 동일함!!
d만 구하면 됨~~
근데...
-4... 가 답이 아니라고 합니다... ㅜㅜ 아마 음수라서 그런듯
그러면 페르마의 소정리를 이용해서 풀어봅시다
그러면 얘를 문제에 적용해보면
요로코롬!!
바로 d 를 계산하면 됩니둥
답은?
굳~
728x90
'WARGAME > cryptography' 카테고리의 다른 글
| [CryptoHack] Resisting Bruteforce (0) | 2024.01.22 |
|---|---|
| [CryptoHack] Keyed Permutations (0) | 2024.01.22 |
| [CryptoHack] Modular Arithmetic 2 (0) | 2024.01.16 |
| [CryptoHack] Modular Arithmetic 1 (0) | 2024.01.16 |
| [CryptoHack] Extended GCD (0) | 2024.01.16 |