[Cryptography] Random numbers for Diffie-Hellman

[Christian Huitema]

On 12/3/2024 10:50 PM, Pierre Abbat wrote:

> What I outlined for 5 and 7 and detailed for 3 is the method of generating
> uniform numbers in [0,n) where n is a power of a small prime, given uniform
> bits. Given uniform numbers in [0,2^8), [0,3^17), [0,5^31), and [0,7^11), you
> can generate uniform numbers in [0,n), where n is any 7-smooth number.

This seems like a simple derivation of writing a number in a specific 
base. Assume that a number x can be written as:

x = sum(a[i]*b^i), for in in 0..n

The coefficients a[i] are all between 0 and b-1. You can get a random 
number <= b^n by picking each of the coefficients at random in [0..n-1].

-- Christian Huitema