Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

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
DOI: https://doi.org/10.1090/S0025-5718-2013-02737-8
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?)

  • 1. W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703-722. MR 1283874 (95k:11114)
  • 2. Eric Bach and Jeffrey Shallit, Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996, Efficient algorithms. MR 1406794 (97e:11157)
  • 3. Mark Chaimovich, New algorithm for dense subset-sum problem, Astérisque (1999), no. 258, xvi, 363-373, Structure theory of set addition. MR 1701210 (2000h:90047)
  • 4. P. Erdős, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201-206. MR 0079031 (18:18e)
  • 5. Abraham D. Flaxman and Bartosz Przydatek, Solving medium-density subset sum problems in expected polynomial time, STACS 2005, Lecture Notes in Comput. Sci., vol. 3404, Springer, Berlin, 2005, pp. 305-314. MR 2151627 (2006c:68082)
  • 6. Dominique Guillaume and François Morain, Building pseudoprimes with a large number of prime factors, Appl. Algebra Engrg. Comm. Comput. 7 (1996), no. 4, 263-277. MR 1464541 (98d:11011)
  • 7. Nick Howgrave-Graham and Antoine Joux, New generic algorithms for hard knapsacks, Advances in cryptology--EUROCRYPT 2010, Lecture Notes in Comput. Sci., vol. 6110, Springer, Berlin, 2010, pp. 235-256. MR 2660491
  • 8. Greg Kuperberg, A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, SIAM J. Comput. 35 (2005), no. 1, 170-188 (electronic). MR 2178804 (2007d:81040)
  • 9. Günter Löh and Wolfgang Niebuhr, A new algorithm for constructing large Carmichael numbers, Math. Comp. 65 (1996), no. 214, 823-836. MR 1325872 (96g:11148)
  • 10. Vadim Lyubashevsky, The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem, APPROX-RANDOM, Lecture Notes in Comput. Sci., vol. 3624, Springer, 2005, pp. 378-389. MR 2193702
  • 11. Lorenz Minder and Alistair Sinclair, The extended k-tree algorithm, SODA '09: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Philadelphia, PA, USA), Society for Industrial and Applied Mathematics, 2009, pp. 586-595. MR 2809263
  • 12. R. G. E. Pinch, The Carmichael numbers up to $ 10^{15}$, Math. Comp. 61 (1993), no. 203, 381-391. MR 1202611 (93m:11137)
  • 13. Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff, Jr., The pseudoprimes to $ 25\cdot 10^{9}$, Math. Comp. 35 (1980), no. 151, 1003-1026. MR 572872 (82g:10030)
  • 14. Srinivasa Ramanujan, Highly composite numbers, Ramanujan J. 1 (1997), no. 2, 119-153, Annotated and with a foreword by Jean-Louis Nicolas and Guy Robin. MR 1606180 (99b:11112)
  • 15. Andrew Shallue, An improved multi-set algorithm for the dense subset sum problem, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 416-429. MR 2467862 (2009j:11198)
  • 16. Victor Shoup, Number theory library (NTL), http://www.shoup.net/ntl.
  • 17. Abraham Sinkov, Elementary cryptanalysis, a mathematical approach, first ed., Random House New Mathematical Library, vol. 22, Random House, New York, 1968. MR 2530836 (2010h:94197)
  • 18. David Wagner, A generalized birthday problem (extended abstract), Advances in Cryptology - CRYPTO 2002, Lecture Notes in Comput. Sci., vol. 2442, Springer, Berlin, 2002, pp. 288-303. MR 2054827 (2004m:94076)
  • 19. Ming Zhi Zhang, A method for finding large Carmichael numbers, Sichuan Daxue Xuebao 29 (1992), no. 4, 472-479. MR 1210286 (93m:11009)

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
Email: grantham@super.org

Steven Hayman
Affiliation: 1331 East Washington Street, Unit A, Greenville, South Carolina 29607
Email: steven.paul.hayman@gmail.com

Andrew Shallue
Affiliation: Illinois Wesleyan University, 1312 Park St., Bloomington, Illinois 61701
Email: ashallue@iwu.edu

DOI: https://doi.org/10.1090/S0025-5718-2013-02737-8
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.

American Mathematical Society