[Cryptography] Generating random values in a particular range
Jerry Leichter
leichter at lrw.com
Fri Aug 5 15:39:04 EDT 2016
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
More information about the cryptography
mailing list