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

RE: [PrimeNumbers] Pseudoprimes

Expand Messages
  • Paul Leyland
    ... 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
    Message 1 of 8 , May 1, 2003
    • 0 Attachment
      > 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
    Your message has been successfully submitted and would be delivered to recipients shortly.