Abstract
The Quintic Reciprocity Law is used to produce an algorithm, that runs in polynomial time, and that determines the primality of numbers M such that M 4 − 1 is divisible by a power of 5 which is larger that \(\sqrt{M}\), provided that a small prime p, p ≡ 1 (mod 5) is given, such that M is not a fifth power modulo p. The same test equations are used for all such M.
If M is a fifth power modulo p, a sufficient condition that determines the primality of M is given.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adleman, L., Pomerance, C., Rumely, R.: On distinguishing prime numbers from composite numbers. Ann. of Math. 117, 173–206 (1983)
Bressoud, D.: Factorization and Primality Testing. Springer, New York (1989)
Berrizbeitia, P., Berry, T.G.: Cubic Reciprocity and generalised Lucas-Lehmer test for primality of A3n±1. In: Proc. AMS, vol. 127, pp. 1923–1925 (1999)
Cohen, H., Lenstra, H.W.: Primality testing and Jacobi sums. Math. Comp. 42, 297–330 (1984)
Cohen, H., Lenstra, A.K.: Implemetation of a new primality test. Math. Comp. 48, 103–121 (1987)
Guthmann, A.: Effective Primality Test for Integers of the Forms \({\rm N} = {\rm K}3^{{\rm n}}+1 \ {\rm and} \ {\rm N}={\rm K}2^{{\rm m}}3^{{\rm n}}+1\). BIT 32, 529–534 (1992)
Ireland, K., Rosen, M.: A Classical Introduction to Modern Number Theory, 2nd edn. Springer, New York (1982)
Rosen, M.: A Proof of the Lucas-Lehmer Test. Amer. Math. Monthly 95(9), 855–856 (1980)
Williams, H.C.: Effective Primality Tests for some Integers of the Forms \({\rm A}5^{{\rm n}}-1 \ {\rm and} \ {\rm A}7^{{\rm n}}-1\). Math. of Comp. 48, 385–403 (1987)
Williams, H.C.: A Generalization of Lehmer’s functions. Acta Arith 29, 315–341 (1976)
Williams, H.C., Judd, J.S.: Determination of the Primality of N by Using Factors of N 2±1. Math. of Comp. 30, 157–172 (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Berrizbeitia, P., Odreman Vera, M., Tena Ayuso, J. (2000). Quintic Reciprocity and Primality Test for Numbers of the Form \(M~=~A5^{n} \pm ~\omega_{n}\) . In: Gonnet, G.H., Viola, A. (eds) LATIN 2000: Theoretical Informatics. LATIN 2000. Lecture Notes in Computer Science, vol 1776. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10719839_28
Download citation
DOI: https://doi.org/10.1007/10719839_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67306-4
Online ISBN: 978-3-540-46415-0
eBook Packages: Springer Book Archive