×

A primality test for \(4Kp^n-1\) numbers. (English) Zbl 1461.11018

Classical Lucasian type primality tests provide primality criteria for an integer \(N\) written in a specific form and based on the use of a recursive sequence. The initial value, \(S_0\), of the recursion usually depends on the specific parameter values used to represent \(N\). Motivated by this dependence of \(S_0\) on the specific \(N\), the authors provide an alternative in which the necessity is dropped in order to obtain a laxer sufficient primality condition independent of any parameters of \(N\) in a given parametrised set of integers.
The authors present in Corollary 1 a Lucasian type primality test for numbers written in the form \(N=4 K p^n - 1\), in which \(p\) is an odd prime, \(n\geq 1\) and \(K\) an odd integer with \(4K \leq p^n\). Moreover, in Corollary 2 and setting \(p=2\), a Gaussian analogue to the classical Lucas-Lehmer-Riesel test is presented. In Section 4 the computational complexity of their proposed algorithm is discussed. Finally, in Section 5 the algorithm is compared to other methods and the probability with which a prime is correctly certified by the algorithm is discussed as well.
It is noted that similar results have been obtained by different authors [E. L. Roettger et al., Des. Codes Cryptography 77, No. 2-3, 515–539 (2015; Zbl 1364.11161)], but that the presentation of the results is novel and original.

MSC:

11A51 Factorization; primality
11Y11 Primality
11Y40 Algebraic number theory computations

Citations:

Zbl 1364.11161
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berrizbeitia, P.; Berry, Tg, Cubic reciprocity and generalised Lucas-Lehmer tests for primality of \(A\cdot 3^n\pm 1\), Proc. Am. Math. Soc., 127, 7, 1923-1925 (1999) · Zbl 0997.11010 · doi:10.1090/S0002-9939-99-04786-3
[2] Berrizbeitia, P.; Berry, Tg, Biquadratic reciprocity and a Lucasian primality test, Math. Comput., 73, 247, 1559-1564 (2004) · Zbl 1090.11004 · doi:10.1090/S0025-5718-03-01575-8
[3] Bosma, W.: Cubic reciprocity and explicit primality tests for \(h\cdot 3^k\pm 1\). In: van der Poorten, A., Stein, A. (eds.) High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams, volume 41 of Fields Inst. Commun., pp. 77-89. American Mathematical Society, Providence, RI (2004) · Zbl 1103.11039
[4] Crandall, R.; Pomerance, C., Prime Numbers: A Computational Perspective (2005), New York: Springer, New York · Zbl 1088.11001
[5] Deng, Y.; Lv, C., Primality test for numbers of the form \(Ap^n+w_n\), J. Discret. Algorithms, 33, 81-92 (2015) · Zbl 1364.11160 · doi:10.1016/j.jda.2015.03.003
[6] Deng, Y.; Huang, D., Explicit primality criteria for \(h \cdot 2^n \pm 1\), Journal de Theorie des Nombres de Bordeaux, 28, 1, 55-74 (2016) · Zbl 1364.11014 · doi:10.5802/jtnb.928
[7] GIMPS, GreatInternet Mersenne Prime Search. Founded by G. Woltman. https://www.mersenne.org. Accessed 1 Nov 2019
[8] Grau, Jm; Oller-Marcén, Am; Sadornil, D., A primality test for \(Kp^n+1\) numbers, Math. Comput., 84, 291, 505-512 (2015) · Zbl 1352.11105 · doi:10.1090/S0025-5718-2014-02849-4
[9] Grau, Jm; Oller-Marcén, Am; Sadornil, D., Fermat test with Gaussian base and Gaussian pseudoprimes, Czechoslov. Math. J., 65, 140, 969-982 (2015) · Zbl 1363.11012 · doi:10.1007/s10587-015-0221-2
[10] Koval, A.; Latifi, S., Algorithm for Gaussian integer exponentiation, Information Technology: New Generations. Advances in Intelligent Systems and Computing, 1075-1085 (2016), Berlin: Springer, Berlin
[11] Lehmer, Dh, An extended theory of Lucas’ functions, Ann. Math. Second Ser., 31, 3, 419-448 (1930) · JFM 56.0874.04 · doi:10.2307/1968235
[12] Lemmermeyer, F.: Conics—a poor man’s elliptic curves. arXiv:math/0311306v1, preprint at http://www.fen.bilkent.edu.tr/franz/publ/conics.pdf
[13] Lucas, E., Théorie des fonctions numériques simplement périodiques, Am. J. Math. Pure Appl., 1, 184-239, 289-321 (1878) · JFM 10.0134.05
[14] Riesel, H., Lucasian criteria for the primality of \(N = h\cdot 2^n - 1\), Math. Comput., 23, 108, 869-875 (1969) · Zbl 0186.07803
[15] Rödseth, Oj, A note on primality tests for \(N=h\cdot 2^n-1\), BIT, 34, 3, 451-454 (1994) · Zbl 0814.11007 · doi:10.1007/BF01935653
[16] Roettger, El; Williams, Hc; Guy, Rk, Some primality tests that eluded Lucas, Des. Codes Cryptogr., 77, 515-539 (2015) · Zbl 1364.11161 · doi:10.1007/s10623-015-0088-0
[17] Sadovnik, Ev, Testing numbers of the form \(N = 2kp^m - 1\) for primality, Discret. Math. Appl., 16, 2, 99-108 (2006) · Zbl 1126.11071 · doi:10.1163/156939206777344610
[18] Schönhage, A.; Strassen, V., Schnelle multiplikation grosser zahlen, Computing (Arch. Elektron. Rechnen), 7, 281-292 (1971) · Zbl 0223.68007
[19] Stechkin, Sb, Lucas’s criterion for the primality of numbers of the form \(N = h2^n-1\), Math. Notes Acad. Sci. USSR, 10, 3, 578-584 (1971) · Zbl 0232.10007
[20] Stein, A.; Williams, Hc, Explicit primality criteria for \((p-1)p^n-1\), Math. Comput., 69, 232, 1721-1734 (2000) · Zbl 1018.11062 · doi:10.1090/S0025-5718-00-01212-6
[21] Sun, Z-H, Primality tests for numbers of the form \(K\cdot 2^m \pm 1\), Fibonacci Q., 44, 2, 121-130 (2006) · Zbl 1110.11037
[22] Williams, Hc, The primality of certain integers of the form \(2Ar^n-1\), Acta Arith., 39, 1, 7-17 (1981) · Zbl 0475.10003 · doi:10.4064/aa-39-1-7-17
[23] Williams, Hc, Édouard Lucas and Primality Testing (1998), New York: Wiley, New York · Zbl 1155.11363
[24] Williams, Hc; Zarnke, Cr, Some prime numbers of the forms \(2A3^n+1\) and \(2A3^n-1\), Math. Comput., 26, 995-998 (1972) · Zbl 0259.10005
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.