AlpacaHack Round 3 (Crypto) - qrime
方程式を解くという発想も、n/2r の平方根付近を探索するという発想もなぜかなかったため大変なことになりました。
ちなみにこの解法なら$ p = q * nextPrime(r) + getRandomNBitInteger(256) * rとかでも解けます（？）
$ p = q(r+a) + r(q+b)（a,b は小さい）
$ n = 2q^2r + aq^2 + bqr
$ n \equiv aq^2 \bmod r
小さい$ aを全部試して平方剰余を取れば$ q \bmod rが分かりそう
ただし、$ rは合成数なので工夫が必要
まず、$ aに逆元がないと困るので$ r' = r/gcd(a,r)として$ q^2 \equiv n/a \bmod r'を使う
合成数modの平方剰余はそのままでは難しい
factorコマンドで$ rを素因数分解してみると、できた
r=2*3*5*127*137*785197007920727*74994230814184840181764160925127093363224653769413658733
素数modでの平方剰余はTonelli-Shanks algorithmで出来るので、その結果をCRTでまとめる
素数ごとに正負２通りずつあるので$ 2^6通りの候補が出てくる
$ q/r は小さいと思われるので$ qが求まる
補足
$ aは容易に計算可能でした。さらに$ r,nextPrime(r)が互いに素なので$ r,aも互いに素ですね。
睡眠リズムが合わず、頭完全に寝てました・・・
他の問題も知見があって面白かったです。