[Cryptography] Random numbers for Diffie-Hellman

[Jerry Leichter]

> So how would you generate a uniform random number from an arbitrary large 
> range with minimum waste?
There's quite a bit of published work on this going back years.  I don't have any references off-hand, but it shouldn't be hard to find.

Here's an observation to start with:  Assume you can generate uniform random n-bit values.  You want values uniformally distributed from 0 to (2^n)-k.  When k is small, your best bet is to just generate a random value.  If it happens to be more than (2^n)-k, discard it and generate another.  Obviously, the larger k is, the more values you have to discard.  So as k gets large you want to use a different strategy.  There's one that's obvious once you think of it ... but at the moment it won't come back to me!  But you play some games between at least two strategies.

You seem to be heading in somewhat the same direction, but I don't follow all the details of what you propose.
                                                        -- Jerry