Re:Factoring composite numbers into nearly equal factors
by dmdox on Sunday February 13, 2022 @06:30PM
(#30326681)
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)
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)