信息技术.安全技术.素数生成

[中文适用范围]： 本文件规定了生成素数和测试素数的方法，以满足加密协议和算法的要求。首先，本文件规定了测试给定整数是否为素数的方法。本文件中包含的测试方法分为以下两类：——概率素性测试，其错误概率较小；所有此处描述的概率测试均可声明合数为素数；——确定性方法，这些方法保证给出正确的判断结果。这些方法使用所谓的素性证书。其次，本文件规定了生成素数的方法。同样，此处还介绍了概率和确定性方法。注：具有算法理论背景的读者可能已经与概率和确定性算法有过接触。本文档中的确定性方法内部仍使用随机位（通过ISO/IEC 18031中所述的方法生成），而“确定性”仅指输出正确概率为一的事实。附录A给出了错误概率，这些错误概率被Miller-Rabin素性测试所利用。附录B描述了生成素数的方法的变体，以便满足特定的加密要求。附录C定义了用于素数生成和验证方法的原语。 [外文原描述]： This document specifies methods for generating and testing prime numbers as required in cryptographic protocols and algorithms. Firstly, this document specifies methods for testing whether a given number is prime. The testing methods included in this document are divided into two groups: — probabilistic primality tests, which have a small error probability. All probabilistic tests described here can declare a composite to be a prime; — deterministic methods, which are guaranteed to give the right verdict. These methods use so-called primality certificates. Secondly, this document specifies methods to generate prime numbers. Again, both probabilistic and deterministic methods are presented. NOTE It is possible that readers with a background in algorithm theory have already had previous encounters with probabilistic and deterministic algorithms. The deterministic methods in this document internally still make use of random bits (to be generated via methods described in ISO/IEC 18031), and "deterministic" only refers to the fact that the output is correct with probability one. Annex A provides error probabilities that are utilized by the Miller-Rabin primality test. Annex B describes variants of the methods for generating primes so that particular cryptographic requirements can be met. Annex C defines primitives utilized by the prime generation and verification methods.