Dreamhack/CryptoPS
2023. 11. 11.
[Dreamhack][CryptoPS] Chinese what?
1.문제 분석 중국인의 나머지 정리를 활용하는 문제 확장된 유클리드 알고리즘을 활용하는 문제 (modular inverse) 2. 기본 아이디어 주어진 p1, p2, p3, c1, c2, c3를 통해 수식을 계산해준다. M, M에 따른 m1, m2, m3, 각각의 역원을 계산해준다. 3.문제 풀이 먼저 문제에서는 다음과 같은 값이 주어진다. 느낌상으로도 나중에 c1, c2, c3를 병합하면 flag가 나올 것 같다. 중국인의 나머지 정리는 간단하게 다음과 같다. 연립 합동식 문제고 자세한 것은 구글링하면 금방 찾을 수 있다. 이제 코드를 짜보면 이 문제의 경우 p값들이 굉장히 큰 값이므로 모듈러 역원을 구하기 위해서는 확장된 유클리드 알고리즘을 사용할 필요가 있다. 그것을 구현한 것이 바로 mod_inv..