Algorithms for generating, testing and proving primes: A survey (Q2708615)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1588470
Language Label Description Also known as
default for all languages
No label defined
    English
    Algorithms for generating, testing and proving primes: A survey
    scientific article; zbMATH DE number 1588470

      Statements

      17 July 2001
      0 references
      primality testing
      0 references
      primality proving
      0 references
      computational number theory
      0 references
      cryptography
      0 references
      survey
      0 references
      pseudoprimes
      0 references
      elliptic curve primality proving
      0 references
      0 references
      0 references
      Algorithms for generating, testing and proving primes: A survey (English)
      0 references
      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].
      0 references

      Identifiers