#chinese-remainder-theorem

256비트 소수 p, q, r 을 2의 256제곱 진법 자릿수로 늘어놓아 만든 768비트 소수 a 와 b 는 서로 자릿수를 뒤집은 쌍이다. 그러면 2의 512제곱 빼기 1 로 나눈 나머지에서 두 소수가 같은 값으로 접히고, N 은 그 값의 제곱이 된다. 2의 512제곱 빼기 1 은 서로 다른 소수 13개로 완전분해되니 제곱근 8192개를 전부 만들어 걸러내면 된다. 전체 0.1초.

flag를 정수로 본 뒤 세 개의 420비트 소수로 나눈 나머지만 공개된 crypto 문제. 나머지 하나로는 flag가 소수보다 커서 복원되지 않지만, 서로소인 세 소수의 곱이 flag보다 크므로 중국인의 나머지 정리(CRT)로 세 합동식을 합치면 flag가 유일하게 결정된다. CRT로 정수를 복원해 바이트로 되돌렸다.