Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


Constructing Carmichael numbers through improved subset-product algorithms

Authors: W. R. Alford, Jon Grantham, Steven Hayman and Andrew Shallue
Journal: Math. Comp. 83 (2014), 899-915
MSC (2010): Primary 11Y16
Published electronically: July 9, 2013
MathSciNet review: 3143697
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We have constructed a Carmichael number with 10,333,229,505 prime factors, and have also constructed Carmichael numbers with $ k$ prime factors for every $ k$ between 3 and 19,565,220. These computations are the product of implementations of two new algorithms for the subset product problem that exploit the non-uniform distribution of primes $ p$ with the property that $ p-1$ divides a highly composite $ \Lambda $.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16

Retrieve articles in all journals with MSC (2010): 11Y16

Additional Information

Jon Grantham
Affiliation: Institute for Defense Analyses, Center for Computing Sciences, 17100 Science Drive, Bowie, Maryland 20715

Steven Hayman
Affiliation: 1331 East Washington Street, Unit A, Greenville, South Carolina 29607

Andrew Shallue
Affiliation: Illinois Wesleyan University, 1312 Park St., Bloomington, Illinois 61701

Keywords: Subset sum, Carmichael numbers
Received by editor(s): December 15, 2011
Received by editor(s) in revised form: May 24, 2012
Published electronically: July 9, 2013
Additional Notes: W. R. Alford passed away in 2003
This research was supported by an Illinois Wesleyan University grant
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.