暗号解析 - RSAのWiener攻撃

d < n^(1/4)/3 のようにdが小さいと、e/nの連分数展開の近似分数 k/d の中に本物のkとdが現れます

近似分数 num/den は、a = 分子 // 分母 を取りながら num = a×num1 + num0、den = a×den1 + den0 で作ります。分子 num を k の候補、分母 den を d の候補とし、(e×den − 1) が num で割り切れるかを見ます

φ = (e×d − 1)/k として、x² − (n − φ + 1)x + n = 0 の判別式が平方数（math.isqrt で確認）になれば正解です