[BOJ] 15293번: Knapsack Cryptosystem

https://www.acmicpc.net/problem/15293

 

NEERC 2017 기출인데 솔직히 만약 대회 중이었다면 이 문제는 무조건 버렸어야 한다고 생각합니다. 물론 로씨아 형님들은 강해서 무려 3팀이나 이걸 풀었지만..

 

1도 감이 안와 홈페이지에서 풀이를 찾아봤습니다. $N$이 42정도면 그냥 MITM으로 해결하고, $N$이 42보다 크면 $a[0]$이 $2^{64-N}$보다 작아야한다는 점을 이용해 $r$의 후보들을 구하고 해당 $r$에서 super increasing sequence가 되는지 체크하면 됩니다. inverse를 구할 때 __int128을 쓰면 시간초과가 발생하고 오일러 파이를 이용해야 합니다.

 

나름 암호학 전공하겠다는 사람인데 안풀고가긴 섭섭해서 풀고 가지만 정말 쉽지 않은 문제였습니다. 참고로 같은 대회에 RSA 부채널 공격도 나왔습니다. 정말 미친 것 같습니다. 참고로 $q = 2^{64}$로 제한되지 않은 Knapsack Cryptosystem도 P algorithm이 있다고 하네요.

 

https://github.com/blisstoner/BOJ/blob/master/15293.cpp