AlpacaHack Round 3 (Crypto) Rainbow Sweet Alchemist Writeup
$ p,q を直接求めない解法です。
$ p - 1,q - 1をそれぞれ素因数分解すると、deterministicGetPrime() によって生成されるある素数の列の一部と2が素因数になる。
つまり、deterministicGetPrime() によって生成される素数を十分な個数(この問題では3000とした)生成し、それらの積をMとすると、$ \frac{(p-1)(q-1)}{4} \mid M になる。これより $ (p-1)(q-1) \mid 4M なので、$ d*e \equiv 1 \pmod {4M} を満たす$ dは $ d*e \equiv 1 \pmod{(p-1)(q-1)} をみたす。
よって最終的に計算するべき m は、m = pow(c, pow(e, -1, 4*M), n) になる。