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
6 February 2004
0 references
primality tests
0 references
Pocklington theorem
0 references
0.770844042301178
0 references
0.7431938648223877
0 references
0.7271177768707275
0 references
0.7269503474235535
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