FactHacks 
RSA factorization in the real world 

Fermat's factorization methodFermat's factorization method factors N into p and q very quickly if p and q share half of their leading bits, i.e., if the gap between p and q is below the square root of p. It becomes much slower if p and q share significantly fewer bits.One can save time in RSA decryption by choosing, e.g., p and q very close to 2^512. Fermat's factorization method shows that this is unsafe if "very close" means, e.g., between 2^5122^256 and 2^512+2^256. Fermat's factorization method is also a first step towards understanding the quadratic sieve. Lattice techniques show that it's always unsafe to choose p very close to 2^512, even if q is chosen randomly. How it worksSage code:def fermatfactor(N): if N <= 0: return [N] if is_even(N): return [2,N/2] a = ceil(sqrt(N)) while not is_square(a^2N): a = a + 1 b = sqrt(a^2N) return [a  b,a + b]Examples: sage: print fermatfactor(91) [7, 13] sage: print fermatfactor(1009) # this one is prime [1, 1009] sage: print fermatfactor(6557) [79, 83] sage: N = 115792089237316195423570985008721211221144628262713908746538761285902758367353 sage: print fermatfactor(N) [340282366920938463463374607431817146293, 340282366920938463463374607431817146421] sage: N = 115792089237316195448679392282006640413199890130332179010243714077028592474181 sage: print fermatfactor(N) [340282366920938463463374607431817146293, 340282366920938463537161584701547790417]In the last example, q was chosen as the next prime after p+2^66+974892437589, and both p and q were very close to 2^128. In the previous example, q was chosen as the next prime after p; this would happen if the RSA implementor generated both p and q from the same sequential search. Speed degenerates rapidly when p and q share fewer than half their leading bits: sage: p = next_prime(2^512 + randrange(2^264)) sage: q = next_prime(p + 2^264 + randrange(2^262)) sage: time f = fermatfactor(p * q) Time: CPU 0.18 s, Wall: 0.17 s sage: p = next_prime(2^512 + randrange(2^265)) sage: q = next_prime(p + 2^265 + randrange(2^263)) sage: time f = fermatfactor(p * q) Time: CPU 0.37 s, Wall: 0.37 s sage: p = next_prime(2^512 + randrange(2^266)) sage: q = next_prime(p + 2^266 + randrange(2^264)) sage: time f = fermatfactor(p * q) Time: CPU 0.91 s, Wall: 0.91 s sage: p = next_prime(2^512 + randrange(2^267)) sage: q = next_prime(p + 2^267 + randrange(2^265)) sage: time f = fermatfactor(p * q) Time: CPU 4.64 s, Wall: 4.67 s sage: p = next_prime(2^512 + randrange(2^268)) sage: q = next_prime(p + 2^268 + randrange(2^266)) sage: time f = fermatfactor(p * q) Time: CPU 18.53 s, Wall: 18.57 s sage: p = next_prime(2^512 + randrange(2^269)) sage: q = next_prime(p + 2^269 + randrange(2^267)) sage: time f = fermatfactor(p * q) Time: CPU 50.85 s, Wall: 50.94 s Version: This is version 2012.12.28 of the fermat.html web page. 