Hacker News Reader

>Moreover, p and q must be chosen independently. If p and q share approximately half of their upper bits, then N can be factored using Fermat’s method.

Wouldn't p and q normally share around half their upper bits if chosen independently? I suspect the probability distribution would be centered around 0.5

View on HN

This is a good point. Perhaps they meant to say "if approximately the upper half of p and q's bits are identical"?

That might make more sense. If you have two integers in the same approximate range you might expect the upper halves to look similar.

Why would they? Given two random numbers with a size of n, the probability that upper halves (size of upper half is n/2) are the same is 1/(1+n/2).

That's not how the parent is interpreting that statement; their interpretation of,

> If p and q share approximately half of their upper bits

That, of the upper bits, are approximately half are the same? Since the combinations of two corresponding bits in p & q are 00, 01, 10, and 11, and, if they're chosen uniformly, one would expect about half to be the same.

I suspect that your interpretation is what the article wants to say, but I think that the parent's interpretation is reasonable given how it was written.

Reply on news.ycombinator.com