Prime Number Generation Based On Pocklington's Theorem (Q3147307)

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 1802853
Language Label Description Also known as
default for all languages
No label defined
    English
    Prime Number Generation Based On Pocklington's Theorem
    scientific article; zbMATH DE number 1802853

      Statements

      Prime Number Generation Based On Pocklington's Theorem (English)
      0 references
      0 references
      6 February 2004
      0 references
      primality tests
      0 references
      Pocklington theorem
      0 references
      The paper proposes a method to build a prime number with 100 digits, using the classical theorem of Pocklington: Let \(n=2kp+1, k\in {\mathcal N}\), \(p\) an odd prime not dividing \(k\), \(1<k<2(p+1)\). The following conditions are equivalent: \(n\) is prime There exist \(a\in{\mathcal N},2\leq a < n\) such that: \[ a^{kp}\equiv -1 \bmod n \] \[ \gcd(a^k +1,n)=1 \] Beginning with a 5-digits prime \(p_1\)\, the method successively builds, using Pocklington's, theorem primes \(p_i=2k_{i-1}p_{i-1}+1\), in such a way that \(p_6\) has 100 digits as wanted. The paper implements this algorithm in pseudo-C++, discusses some implementation issues and presents some examples. As the authors point out the method is slow (an average of 15'86 minutes on a Sun Sparc Ultra 10). A more serious drawback is the fact that such an implementation only checks condition (1) in the theorem of Pocklington (see above) ``since the second could not be implemented''. Unfortunately such a relaxed version of Pocklington's theorem does not provide a deterministic primality test, in contradiction with the purpose of the authors.
      0 references

      Identifiers