解説

簡単のため、 $\varphi = (p - 1)(q - 1)$ とします。

$d \equiv e^{-1} \mod \varphi$ となる数 $d$ を求めることを考えます。

$\varphi \le 10^6$ 程度なら全探索でも可能ですが、今回は $\varphi \le 10^{18}$ 程度なのでそれでは間に合いません。

結論から言うと、拡張ユークリッドの互除法を使えば $O(\log \varphi)$ となり間に合います。