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 :
Post a Comment