[Cryptography] Generating random values in a particular range

[Watson Ladd]

On Fri, Aug 5, 2016 at 11:59 PM, Sidney Markowitz <sidney at sidney.com> wrote:
> Jerry Leichter wrote on 6/08/16 7:39 AM:
>> 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.
>
> That patent link says that it has a priority date of Dec 27, 2000 (with a
> disclaimer that Google has not performed a legal analysis to come up with that
> date).
>
> The Gnu GMP library version 3.0.1 source code at https://ftp.gnu.org/gnu/gmp/
> tarball https://ftp.gnu.org/gnu/gmp/gmp-3.0.1.tar.gz date stamped 2000-04-07
> in file gmp-3.0.1/mpz/urandomm.c uses that algorithm for function mpz_urandomm
>
> Later versions of GMP have the improvement of iterating a maximum number of
> times then return the value mod n if it doesn't get a result less than n by
> then, but that improvement does not appear in the patent claims.

That second method is known as rejection sampling and was invented by
John von Neumann.
>
>
>  Sidney Markowitz
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.