Describes methods for generating large prime numbers as needed by public key cryptographic algorithms. It also provides testing methods for testing candidate primes presented by a third party. It allows primes to be generated either deterministically or probabilistically, where: - A number shall be accepted as prime when a probabilistic algorithm that declares it to be prime is in error with probability less than 2[-100]. - A deterministic prime shall be generated using a method that guarantees that it is prime.