12327RE: [PrimeNumbers] Pseudoprimes
- May 1 1:37 AM
> From: Nathan Russell [mailto:nrussell@...]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.
> 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 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.
- << Previous post in topic