Loading ...
Sorry, an error occurred while loading the content.

12327RE: [PrimeNumbers] Pseudoprimes

Expand Messages
  • Paul Leyland
    May 1 1:37 AM
      > 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.

    • Show all 8 messages in this topic