Hacker News new | ask | show | jobs
by honzaik 524 days ago
it might be this https://facthacks.cr.yp.to/fermat.html

if N=p*q and p-q < sqrt(p) then its easy to factor

1 comments

Encountering this by chance is exceedingly unlikely of course, if p and q are randomly generated. In probability terms it amounts to the first half of p (or q) all being zero (apart from a leading 1) so roughly 2^(-n/4) where n is the bit size of n. So for RSA 2048 the probability of this happening is on the order of 2^-512, or in base-10 terms 0.0000000...0000001, with roughly 150 zeros before the one!