Algorithms for generating, testing and proving primes: A survey

From MaRDI portal





The paper gives a comprehensive survey of techniques for testing and proving primality. Section 2 first gives an overview of those properties of primes that will be of use for the testing and proving algorithms to follow. This includes the basis of the Miller-Rabin algorithm, that for \(n=2^k \cdot m +1\) and \(a_i \equiv a^{2^i m} \pmod{n}\) if \(n\) is a prime then either \(a_i \equiv 1 \pmod{n} ~~\forall i\) or there exists an \(i\) such that \(a_i \equiv -1 \pmod{n}\) and \(a_j \equiv 1 \pmod{n}\) for \(k \geq j > i\). Pocklington's theorem and its consequences and uses in provable primality is discussed. Its generalization to other group structures is discussed, including Lucas-Lehmer sequences and tests. The use of elliptic curves in primality is also considered and in particular the Goldwasser-Kilian approach to providing certificates for primes. Section 3 discusses the use of pseudoprimes in probabilistic proving methods. One is interested in the likelihood that a number is prime after having failed to have been proven composite by the probabilistic tests. The fourth section describes many of the prime search techniques that have been analyzed and used in the literature. This includes the production of provable primes for cryptographic use. The process of generating prime numbers, given the number of bits in the prime, is considered. The next section discusses certain aspects of currently implemented algorithms for general primality proving. This includes the elliptic curve primality proving (ECPP) algorithm and generalized Lucas-Lehmer tests, as developed by Lenstra. The sixth section discusses some security issues related to the generation of primes with biased random distributions and proves a general security result. Aspects of the security of the integer factoring and discrete logarithm problems are also considered. Finally a comparison is made between the most common approaches for prime generation related to performance and confidence. For the entire collection see [Zbl 0956.00037].











This page was built for publication: Algorithms for generating, testing and proving primes: A survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2708615)