volume 30 issue 136 pages 867-886

Some algorithms for prime testing using generalized Lehmer functions

H. C. Williams
J S Judd
Publication typeJournal Article
Publication date2010-06-30
scimago Q1
wos Q1
SJR1.845
CiteScore4.4
Impact factor2.1
ISSN00255718, 10886842
Computational Mathematics
Applied Mathematics
Algebra and Number Theory
Abstract

Let N be an odd integer thought to be prime. The properties of special functions which are generalizations of the functions of Lehmer (Ann. of Math., v. 31, 1930, pp. 419-448) are used to develop algorithms that produce information concerning the possible prime divisors of N. It is shown how the factors of N ± 1 , N 2 + 1 , N 2 ± N + 1 N \pm 1,{N^2} + 1,{N^2} \pm N + 1 , together with the factor bounds on these numbers, may all be used to calculate lower bounds for the possible prime divisors of N. Frequently, these bounds are large enough that N may be shown to be prime. These tests were implemented on an IBM/370-158 computer and run on the pseudoprime divisors of the first 385 Fibonacci and Lucas numbers.

Found 

Are you a researcher?

Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
0
Share
Cite this
GOST |
Cite this
GOST Copy
Williams H. C., Judd J. S. Some algorithms for prime testing using generalized Lehmer functions // Mathematics of Computation. 2010. Vol. 30. No. 136. pp. 867-886.
GOST all authors (up to 50) Copy
Williams H. C., Judd J. S. Some algorithms for prime testing using generalized Lehmer functions // Mathematics of Computation. 2010. Vol. 30. No. 136. pp. 867-886.
RIS |
Cite this
RIS Copy
TY - JOUR
DO - 10.1090/s0025-5718-1976-0414473-6
UR - https://doi.org/10.1090/s0025-5718-1976-0414473-6
TI - Some algorithms for prime testing using generalized Lehmer functions
T2 - Mathematics of Computation
AU - Williams, H. C.
AU - Judd, J S
PY - 2010
DA - 2010/06/30
PB - American Mathematical Society
SP - 867-886
IS - 136
VL - 30
SN - 0025-5718
SN - 1088-6842
ER -
BibTex |
Cite this
BibTex (up to 50 authors) Copy
@article{2010_Williams,
author = {H. C. Williams and J S Judd},
title = {Some algorithms for prime testing using generalized Lehmer functions},
journal = {Mathematics of Computation},
year = {2010},
volume = {30},
publisher = {American Mathematical Society},
month = {jun},
url = {https://doi.org/10.1090/s0025-5718-1976-0414473-6},
number = {136},
pages = {867--886},
doi = {10.1090/s0025-5718-1976-0414473-6}
}
MLA
Cite this
MLA Copy
Williams, H. C., and J S Judd. “Some algorithms for prime testing using generalized Lehmer functions.” Mathematics of Computation, vol. 30, no. 136, Jun. 2010, pp. 867-886. https://doi.org/10.1090/s0025-5718-1976-0414473-6.