[CryptoHack | DreamHack] Chinese Remainder Theorem (중국인의 나머지 정리)

크립토핵 설명보다 드림핵 설명이 이해하기 쉬웠다.

dreamhack.io

 

---

연습문제는 다음과 같다.

x ≡ 2 mod 5
x ≡ 3 mod 11
x ≡ 5 mod 17

# Find the integer a such that x ≡ a mod 935

 
다음과 같이 풀 수 있다.

from Crypto.Util.number import inverse

p1 = 5
p2 = 11
p3 = 17
c1 = 2
c2 = 3
c3 = 5

m = p1*p2*p3

m1 = m // p1
m2 = m // p2
m3 = m // p3
n1 = inverse(m1, p1)
n2 = inverse(m2, p2)
n3 = inverse(m3, p3)

x = pow(c1*m1*n1 + c2*m2*n2 + c3*m3*n3, 1, m)
print(x)

 
또 다른 문제로는 드림핵의 chinese what? 문제가 있다.
https://dreamhack.io/wargame/challenges/660/

chinese what?

 

---

레퍼런스
https://cryptohack.org/courses/modular/crt1/

CryptoHack – Home

https://learn.dreamhack.io/76#8

로그인 | Dreamhack