[Cryptography] Generating random values in a particular range

[Jerry Leichter]

Suppose you want to generate a fair random integer in the range [0, N); but your random number generator only produces fair random bit strings.  What do you do?

The obvious thing is to generate a k-bit string, k = ceil(log2 N) or larger, and then reduce the result modulo N.  But that's biased unless N is itself a power of 2.  

So there's always the other classic technique:  Generate the random value; if it's less than N, keep it; otherwise try again.

Guess what:  The use of that second technique *for generating a random element of a group of order q for use in cryptograpnhy* is the subject of a patent, filed in 2000, https://www.google.com/patents/US7372961.  Blackberry is asserting it (among others that I haven't looked at) against Avaya.

Amazing.
                                                        -- Jerry