scope:

This International Standard specifies methods for generating and testing prime numbers as required in cryptographic protocols and algorithms. Firstly, this International Standard specifies methods for testing whether a given number is prime. The testing methods included in this International Standard can be divided into two groups: - Probabilistic primality tests, which have a small error probability. All probabilistic tests described here may declare a composite to be a prime. One test described here may declare a prime to be composite. - Deterministic methods, which are guaranteed to give the right verdict. These methods use so-called primality certificates. Secondly, this International Standard specifies methods to generate prime numbers. Again, both probabilistic and deterministic methods are presented. Annex B describes variants of the methods for generating primes so that particular cryptographic requirements can be met. The methods for generating, proving and verifying primality defined by this International Standard are applicable to cryptographic systems based on the properties of the primes.