4 ms·
In the meantime, I wrote this up in (too much elementary) detail: https://colab.research.google.com/drive/10t4WRhyAPK1pCzBkaauFIkRUYek6YN2p#scrollTo=o3-qIlIgt7z
by svat 5y ago
In the meantime, I wrote this up in (too much elementary) detail: https://colab.research.google.com/drive/10t4WRhyAPK1pCzBkaauFIkRUYek6YN2p#scrollTo=o3-qIlIgt7zk https://colab.research.google.com/drive/10t4WRhyAPK1pCzBkaau...
The funny thing is, it's often the case that already √(m^2 - 4N) > N^(1/4), so we can answer "No" to whether such a factorization exists, without even trying a single attempt.
- dmdox 5y agoIf you're interested in investigating more, take a look at "Continued Fraction Factorization". This is essentially the first step of that more advanced algorithm. From the continued fraction of √n, you get a series of best rational approximations a/b to √n. Each such approximation gives you: a/b ~ √n a² ~ b² n The first approximation is a = floor(√n), b = 1 These approximations satisfy |a² - b² n| < 2 √n. (this can be used for generating relations as input to Dixon's method)