Hacker News Reader

In the meantime, I wrote this up in (too much elementary) detail: 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.

View on HN

If 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)

Reply on news.ycombinator.com