Hints
Hint 1Show
When d is small (d < n^(1/4)/3), the true k and d appear among the convergents k/d of the continued fraction of e/n
Hint 2Show
Build each convergent num/den by taking a = numerator // denominator and updating num = a*num1 + num0 and den = a*den1 + den0. Treat num as the candidate k and den as the candidate d, and check whether (e*den - 1) is divisible by num
Hint 3Show
With φ = (e*d - 1)/k, the candidate is correct if the discriminant of x^2 - (n - φ + 1)x + n = 0 is a perfect square (check with math.isqrt)