Hart’s One-Line Factoring Algorithm
January 28, 2014
William Hart wrote, in one line of PARI, a function that factors integers. His method, which he gives in the form of a program, is a variant of Fermat’s method:
1 for i ← 1 … iter do
2 s ← ⌈√ni⌉
3 m ← s2 (mod n)
4 if ISSQUARE(m) then
5 t ← √m
6 return GCD(n, s − t)
Hart’s paper, which you should read, gives several optimizations. The algorithm works best when the two factors are near each other, so you should first perform trial division to n1/3, thus ensuring that there is a factor between n1/3 and n1/2, unless n is prime. The algorithm works well for semi-primes up to 1016 or 1018, and Hart claims it is faster than SQUFOF in that range.
Your task is to write a function that factors integers by Hart’s method. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Pages: 1 2