3 ms·
>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'
by MaximumYComb 6y ago
>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
- NullPrefix 6y agoWhy 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).
- deathanatos 6y agoThat'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.
- brianberns 6y agoThis is a good point. Perhaps they meant to say "if approximately the upper half of p and q's bits are identical"?
- MaximumYComb 6y agoThat might make more sense. If you have two integers in the same approximate range you might expect the upper halves to look similar.