4 ms·

Same as generating a 2 digit number. If the first digit is a zero, it is not a 2 digit number.

• opticfluorine 2y ago
  For the purposes of key generation, however, wouldn't you want the full n bits of entropy? Otherwise the search space for a brute force factorization (haha right) is 2^(n-1) instead of 2^n, or half as many possibilities. The domain of the product is still [0..2^(2n)] so the resulting key is the desired 2^(2n) bits. I guess another way to pose my question would be: is there an issue with sampling the entire 2^n space that makes us only take the highest 2^(n-1) subset of integers instead when selecting factors for a key?
  • adgjlsfhk1 2y ago
    you want the nth bit to be set because otherwise there is a small but noticable chance that you generate a surprisingly weak prime.
    • opticfluorine 2y ago
      Out of curiosity, if it is known that the nth bit is set, don't I also have the same risk but in (n-1) bits? Genuinely curious here. Edit: Ah, nevermind, I see now why I don't have that issue. It's because I can't easily iterate the primes in that domain even though I can iterate the reduced number of bits. Thanks!