Wednesday, September 21, 2016

[crnsbmxl] Generating random big integers

Given a source of uniform random unsigned integers over a range (not necessarily a power of two), generate a uniform random large integer.  This is probably not too hard.  Use a previous subroutine as a last step.

Inspiration was the Miller-Rabin probabilistic primality test, whose failure rate 1/4 requires that the bases be chosen uniformly randomly all the way up to the number being tested, typically a large number.  I'm guessing very few implementations of Miller-Rabin do this sampling correctly.  Arnault (August 1995). "Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases" has constructed large composite numbers which pass the Miller-Rabin test for all small bases, and it seems likely that one can construct such a pseudoprime for any given deterministic collection of bases.

If one were to attempt to construct a random large integer from just one double precision random deviate, then only about 2^52 bases are possible, and it's only a little preposterous to imagine constructing a pseudoprime that passes the test for all these bases.

No comments :