Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-05T03:52:15.925Z Has data issue: false hasContentIssue false
  • English
  • Français

A generalised Lucasian primality test

Published online by Cambridge University Press:  17 April 2009

Zhenxiang Zhang ,
Weiping Zhou  and
Xianbei Liu
Zhenxiang Zhang
Affiliation:
Department of Mathematics, Anhui Normal University, Wuhu 241000, Anhui, Peoples Republic of China, e-mail: [email protected]
Weiping Zhou
Affiliation:
Department of Mathematics, Anqing Teachers College, Anqing 246011, Anhui, Peoples Republic of China, e-mail: [email protected]
Xianbei Liu
Affiliation:
Department of Applied Mathematics, Anhui University of Finance & Economics, Bengbu 233041, Anhui, Peoples Republic of China, e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We present a primality test for numbers of the form Mh, n = h·2n ±1 (in particular with h divisible by 15), which generalises Berrizbeitia and Berry's test for such numbers with h ≢ 0 mod 5. With our generalised test, the primality of such a number Mh, n can be proved by means of a Lucas sequence with a seed determined by h and πq — primary irreducible divisor of a prime q ≡ 1 mod 4. We call the prime q a judge of the number Mh, n. We prescribe a sequence S of 48 primes ≡ 1 mod 4 in the interval [13, 2593] such that, for all odd h = 15t < 108 and for all n < 7.3 1011, each number Mh, n has a judge q in . Comparisons with Bosma's explicit primality criteria in “a well-defined finite sense” for the case h = 3t < 105 are given.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 74 , Issue 3 , December 2006 , pp. 419 - 441
Copyright
Copyright © Australian Mathematical Society 2006

References

[1]Berrizbeitia, P. and Berry, T.G., ‘Biquadratic reciprocity and a Lucasian primality test’, Math. Comp. 73 (2004), 1559–1564.CrossRefGoogle Scholar
[2]Bosma, W., ‘Explicit primality criteria for h · 2n ± 1’, Math. Comp. 61 (1993), 97–109.Google Scholar
[3]Cohen, H., A course in computational algebraic number theory, Graduate Texts in Mathmatics 138 (Springer-Verlag, Berlin, 1996).Google Scholar
[4]Crandall, R. and Pomerance, C., Prime numbers, a computational perspective (Springer-Verlag, New York, 2005).Google Scholar
[5]Guy, R.K., Unsolved problems in number theory (Springer-Verlag, New York, 2004).CrossRefGoogle Scholar
[6]Ireland, K. and Rosen, M., A classical introduction to modern number theory, Graduate Texts in Mathematics 84 (Springer-Verlag, New York, 1990).CrossRefGoogle Scholar
[7]Lehmer, D.H., ‘On Lucas's test for the primality of Mersenne's number’, J. London Math. Soc. 10 (1935), 162–165.CrossRefGoogle Scholar
[8]Lucas, E., ‘Théorie des fonctions numériques simplement périodiques, I. II’, Amer. J. Math. 1 (1878), 184–239, 289–321.CrossRefGoogle Scholar
[9]Ribenboim, P., The little book of bigger primes (Springer-Verlag, New York, 2004).Google Scholar
[10]Riesel, H., ‘Lucasian criteria for the primality of N = h · 2n — 1’, Math. Comp. 23 (1969), 869–875.Google Scholar
[11]Riesel, H., Prime numbers and computer methods for factorization (Birkhaüser, Boston, 1985).CrossRefGoogle Scholar
[12]Zhang, Z., ‘Finding strong pseudoprimes to several bases’, Math. Comp. 70 (2001), 863–872.CrossRefGoogle Scholar