The generation of random numbers that are probably prime (Q1118632): Difference between revisions

This paper discusses Rabin's probabilistic primality test. It states, rather provocatively, that Rabin's test can only fail with a nonnegligible probability if the test number is easy to split into two nontrivial factors. Furthermore, it discusses how Rabin's test can be used to generate random probable prime numbers (rather than test a specific integer for primality).