> From: Nathan Russell [mailto:nrussell@...]

> What should be done to a number to make sure the chance of it being

> pseudoprime or a Carmichael number is below the human scale

> of reasonable things to worry about?

If you choose your numbers uniformly and at random from all integers of size N bits, then a single Miller-Rabin pseudoprimality test to a randomly chosen base is sufficient. Only a very tiny fraction of integers have the property that a M-R test has a probability close to 1/4 of failing.

If you are allowed to chose your numbers in such a way that you guarantee it has close to a 1/4 chance of failing a test, pick a power of four sufficiently large that you find it comfortable. I personally don't worry much about things which occur with probability less than 4^(-20) in my expected lifetime.

Paul