Primality test for numbers of the form \((2p)^{2^n}+1\). (English) Zbl 1370.11139
An algorithm determining whether an integer is prime or not is called a primality test. Primality tests are used in computational number theory (namely, in cryptography). Although in 2004, Agrawal-Kayal-Saxena have provided a polynomial time primality test [M. Agrawal et al., Ann. Math. (2) 160, No. 2, 781–793 (2004; Zbl 1071.11070)], more efficient tests for specific families of numbers are needed.
The main result of the current paper is an efficient deterministic polynomial time algorithm for the numbers of the form \(M=(2 p)^{2n} + 1\) (generalized Fermat numbers), where \(p\) is an odd prime. It is worth noting that these numbers were studied by H. C. Williams [Fibonacci Q. 26, No. 4, 296–305 (1988; Zbl 0661.10009)], P. Berrizbeitia et al. [Theor. Comput. Sci. 297, No. 1–3, 25–36 (2003; Zbl 1048.11101)] and others.
The authors provide a running complexity of their primality test (a deterministic polynomial time in the input size \(\log_2 M\)). For \(p\leq 19\), they gave more efficient special primality tests. Some implementation and computational results are also given. This makes the paper clear and complete.
The main result of the current paper is an efficient deterministic polynomial time algorithm for the numbers of the form \(M=(2 p)^{2n} + 1\) (generalized Fermat numbers), where \(p\) is an odd prime. It is worth noting that these numbers were studied by H. C. Williams [Fibonacci Q. 26, No. 4, 296–305 (1988; Zbl 0661.10009)], P. Berrizbeitia et al. [Theor. Comput. Sci. 297, No. 1–3, 25–36 (2003; Zbl 1048.11101)] and others.
The authors provide a running complexity of their primality test (a deterministic polynomial time in the input size \(\log_2 M\)). For \(p\leq 19\), they gave more efficient special primality tests. Some implementation and computational results are also given. This makes the paper clear and complete.
Reviewer: Othman Echi (Dhahran)
Software:
MagmaReferences:
| [1] | [AKS]M. Agrawal, N. Kayal and N. Saxena, PRIMES is in P, Ann. of Math. 160 (2004), 781–793. · Zbl 1071.11070 |
| [2] | [BB]P. Berrizbeitia and T. G. Berry, Cubic reciprocity and generalized Lucas–Lehmer tests for primality of A {\(\cdot\)} 3n{\(\pm\)} 1, Proc. Amer. Math. Soc. 127 (1999), 1923–1925. · Zbl 0997.11010 |
| [3] | [BBT]P. Berrizbeitia, T. G. Berry and J. Tena, A generalization of Proth’s theorem, Acta Arith. 110 (2003), 107–115. · Zbl 1028.11001 |
| [4] | [BOT]P. Berrizbeitia, M. Odreman and J. Tena, Primality test for numbers M with a large power of 5 dividing M4- 1, Theoret. Computer Sci. 297 (2003), 25–36. · Zbl 1048.11101 |
| [5] | [BCP]W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I. The user language, J. Symbolic Comput. 24 (1997), 235–265. · Zbl 0898.68039 |
| [6] | [DL]Y. Deng and C. Lv, Primality test for numbers of the form Apn+ wn, J. Discrete Algorithms 33 (2015), 81–92. · Zbl 1364.11160 |
| [7] | [IR]K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Grad. Texts in Math. 84, Springer, New York, 1990. · Zbl 0712.11001 |
| [8] | [LE]D. H. Lehmer, On Lucas’s test for the primality of Mersenne’s numbers, J. London Math. Soc. 10 (1935), 162–165. · JFM 61.0133.02 |
| [9] | [LU]E. Lucas, Th\'{}eorie des fonctions num\'{}eriques simplement p\'{}eriodiques, Amer. J. Math. 1 (1878), 184–240, 289–321. · JFM 10.0134.05 |
| [10] | [RB]P. Ribenboim, The New Book of Prime Number Records, Springer, New York, 1996. · Zbl 0856.11001 |
| [11] | [RE]H. Riesel, Some factors of the numbers Gn= 62n+ 1 and Hn= 102n+ 1, Math. Comp. 23 (1969), 413–415; Corrigenda, ibid. 24 (1970), 243. |
| [12] | [WA]L. C. Washington, Introduction to Cyclotomic Fields, 2nd ed., Grad. Texts in Math. 83, Springer, New York, 1997. · Zbl 0966.11047 |
| [13] | [W1]H. C. Williams, A note on the primality of 62n+1 and 102n+1, Fibonacci Quart. 26 (1988), 296–305. Primality test for (2p)2n+ 1317 |
| [14] | [W2]H. C. Williams, \'{}Edouard Lucas and Primality Testing, Canad. Math. Soc. Ser. Monogr. Adv. Texts 22, Wiley, New York, 1998. |
| [15] | [WW]http://www.prothsearch.net/GFNfacs.html. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
