This International Standard specifies methods for generating and testing prime numbers as required incryptographic protocols and algorithms.Firstly, this International Standard specifies methods for testing whether a given number is prime. The testingmethods included in this International Standard can be divided into two groups:• Probabilistic primality tests, which have a small error probability. All probabilistic tests described heremay declare a composite to be a prime. One test described here may declare a prime to becomposite.• Deterministic methods, which are guaranteed to give the right verdict. These methods use so-calledprimality certificates.Secon