[Cryptography] Generating random values in a particular range

[Arnold Reinhold]

On Sun, 7 Aug 2016 14:09 Sidney Markowitz wrote:

> This means that it is irrelevant that there are prior examples of rejection
> sampling. This is not a patent on rejection sampling. It is a patent on using
> rejection sampling to eliminate the bias when generating a series of candidate
> random numbers between 0 and L-bit prime p by getting an initial random number
> (the seed) from a PRNG, hashing it to get a number of length L, rejecting it
> if it is greater than p before checking it for primality, then if it is
> rejected doing any transformation of the seed including simply incr4menting
> it, hashing that new value, and trying again.
> 
> Challenging this patent would probably involve trying to convince the PTO or
> the courts and/or a jury that once you know that the problem is that a simple
> mod p introduces bias, the solution is obvious to anyone who has any expertise
> in random number generation that you can solve the problem by using rejection
> sampling in this way. Considering that the original algorithm was "1) take
> H(seed) mod p to ensure a value less than p; 2) check if it is prime; 3) if it
> isn't prime, increment or otherwise get a new seed to hash and loop back,
> otherwise exit" and the new patented algorithm is identical except that
> instead of taking the hash mod p in step 1 you instead make step 2 "check if
> it smaller than p and is prime", there should be a good case for it being
> obvious. However that makes the patent lawsuit something unpredictable. It is
> not the slam dunk that it would be if it were an attempt to patent rejection
> sampling itself.

The 2007 Supreme Court ruling in KSR Int'l Co, v. Teleflex inc., which held that combing art from two previous patents in a straightforward way was not patentable, might be relevant here. 

Arnold Reinhold