[Cryptography] Random numbers for Diffie-Hellman

[Bill Stewart]

On 12/16/2024 8:38 PM, Pierre Abbat wrote:

> We're talking about Diffie-Hellman; K is a prime hundreds or thousands of bits
> long and doesn't fit in a computer register.

If it's classic prime-number Diffie-Hellman, logK is thousands, not 
hundreds.
Let j be some number in a range like 16-32-64,
and Qj be the last j bits of q.
do (Pick a random number J in 0..2**j) until J<Q.
Use J as the high-order bits, then fill in the lower-order bits.
You can pick your rejection rate.
If you want to get extra-fancy, if J==Q, go pick j more random bits and 
see if they're < the next j bits of Q, repeating as long as needed.