- The idea is that you initialize a pgen object with a starting
- place. It spends a short time initializing itself, and then
- tells you whether the number you gave it is (a) definitely
- composite, (b) definitely prime (only for small numbers), or (c)
- it doesn't know. The advantage of the pgen system is that it's
- good at stepping regularly. You can advance it by 2 or 4 very
- rapidly, and it will give you the same sort of answer for the
- next number.
-
- When you find a number which pgen says it doesn't know about,
- you must test it more thoroughly. This is time-consuming, but
- pgen has weeded out many no-hopers so it's not so bad.
-
- The Rabin-Miller test takes a number to test, and stores it in a
- context. You then give it some random numbers, and it gives you
- results. When you've finished, you destroy the context.
-
- The Rabin-Miller test has two possible responses: (a) definitely
- not prime, and (b) probably prime. Answer (a) is certain.
- Answer (b) you may get with a composite number at most one time
- in four. If you try n times, the probability of a composite
- number going unnoticed is at most one in 4^n. In fact, the real
- probability is *much* lower than this.
-
- It's also important to bear in mind that this is examining the
- probability that a number passes n Rabin-Miller tests given
- that it's composite. What's actually interesting the the
- probability that a number is composite given that it passed n
- tests. This probability is lower still. For 1024-bit numbers,
- which are about the right size by current standards of security,
- you need only five tests to ensure a probability of less than 1
- in 2^80 of a composite number slipping through.
-
- There are specialized functions for finding various sorts of
- prime numbers with particular properties. Read the header files
- to find out what they do.