Fermat's factorization method with GMP

Hart's OLF:

http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S144678871200014...

is an interesting variant. Like Caroline mentioned, you won't have any success with this on properly formed RSA keys, but Hart's OLF will very quickly factor some poorly made ones, and works quite a bit better in that respect than standard Fermat. It not only quickly finds N=PQ where P=Q+x for a small x, but also where P=kQ+x for some integer k and small x. Again not something any proper RSA key generation method will produce, but the ways people can screw things up is pretty high, and it might be worth giving it a few seconds just in case.

For small values, unlike Hart I find SQUFOF to be faster, but this is implementation specific. HOLF is also, like Fermat's method, extremely simple to implement.

Nice article, although brief and short on some details. More something to get you started than to actually explain anything in real detail.

It always annoys me, though, when articles like this say:

  > This code has great performances
  > and can factorize prime numbers
  > in a very short amount of time.

Sloppy. Unnecessarily sloppy. One is not factoring primes. Yes, I know what is meant, but in subjects like programming, maths, and cryptography, surely one should be more precise.

Oh, and I'm sure every reader knows that in real life you'd never use this method to factor. Way too slow, and there are many ways to speed it up. Nice naive introduction, though.