SQUFOF (square forme factorization) is an algorithm for factorizing numbers.
As I understand, it is an improvement of Fermat's factorization. Fermat factorization assume that a composite number $N = pq$ can be written in the form $(a+b)(a-b)$ (which is always true for an odd $N$) and iterate on $a$. Thus effectively iterating on the value of $a = \frac{p + q}{2}$. If at one step $a^2 - N$ is a perfect square, then we found a factorization. $b = \sqrt{a^2 - N}$, $p = a + b$, $q = a - b$.
In a challenge, I had to factor this number : 55089599753625499150129246679078411260946554356961748980861372828434789664694269460953507615455541204658984798121874916511031276020889949113155608279765385693784204971246654484161179832345357692487854383961212865469152326807704510472371156179457167612793412416133943976901478047318514990960333355366785001217
In practice the factors are pretty close and the Fermat's method worked pretty well. But I don't understand why SQUFOF failed, both the one implemented in Pari/GP (via the factorint function) and the direct implementation I found on the net here: http://pari.math.u-bordeaux.fr/dochtml/scripts/squfof.gp.html
Therefore, I would like to understand SQUFOF, why it failed (appeared to loop for very long) and how to improve it.
Just for information, the factors are:
- 7422236843002619998657542152935407597465626963556444983366482781089760759017266051147512413638949173306397011800331344424158682304439958652982994939276427
- 7422236843002619998657542152935407597465626963556444983366482781089760760914403641211700959458736191688739694068306773186013683526913015038631710959988771
Squfof is not an improvement of Fermat's method. Fermat's method factors $N$ by finding two integers $x, y$, so that $N = x^2 - y^2$. Shanks' Squfof uses binary quadratic forms and factors $N$ by finding an ambiguous form with discriminant $N$ or $4N$. The running time for Fermat's method to factor $N$ is $\sqrt{N}$ in the worst case. However, when $N = p\cdot q$, with $p$ and $q$ very close, as in the example above, Fermat's method factors $N$ quickly. The running time for Squfof to factor $N$ is always a constant times the fourth root of $N$. When $N$ is a number of a few hundred decimal digits, its fourth root is much smaller than its square root, so you might expect Squfof to be faster than Fermat's method. This would be true if $N$ were a general hard number, not the special number in the example. However, this says that Squfof would take only $10^{50}$ years, while Fermat would take $10^{100}$ years, to factor $N$. Neither algorithm would factor a hard 200-digit number in a reasonable time.
See sections 5.2 and 6.7 of my book, The Joy of Factoring, for more details about these factoring algorithms.