## Constructing Carmichael numbers through improved subset-product algorithms

HTML articles powered by AMS MathViewer

- by \fbox{W. R. } Alford, Jon Grantham, Steven Hayman and Andrew Shallue PDF
- Math. Comp.
**83**(2014), 899-915 Request permission

## 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

- 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**, DOI 10.2307/2118576 - Eric Bach and Jeffrey Shallit,
*Algorithmic number theory. Vol. 1*, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR**1406794** - Mark Chaimovich,
*New algorithm for dense subset-sum problem*, Astérisque**258**(1999), xvi, 363–373 (English, with English and French summaries). Structure theory of set addition. MR**1701210** - P. Erdös,
*On pseudoprimes and Carmichael numbers*, Publ. Math. Debrecen**4**(1956), 201–206. MR**79031** - 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**, DOI 10.1007/978-3-540-31856-9_{2}5 - D. Guillaume and F. Morain,
*Building pseudoprimes with a large number of prime factors*, Appl. Algebra Engrg. Comm. Comput.**7**(1996), no. 4, 263–277. MR**1464541**, DOI 10.1007/BF01195532 - 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**, DOI 10.1007/978-3-642-13190-5_{1}2 - Greg Kuperberg,
*A subexponential-time quantum algorithm for the dihedral hidden subgroup problem*, SIAM J. Comput.**35**(2005), no. 1, 170–188. MR**2178804**, DOI 10.1137/S0097539703436345 - 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**, DOI 10.1090/S0025-5718-96-00692-8 - Vadim Lyubashevsky,
*The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem (extended abstract)*, Approximation, randomization and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 3624, Springer, Berlin, 2005, pp. 378–389. MR**2193702**, DOI 10.1007/11538462_{3}2 - Lorenz Minder and Alistair Sinclair,
*The extended $k$-tree algorithm*, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2009, pp. 586–595. MR**2809263** - R. G. E. Pinch,
*The Carmichael numbers up to $10^{15}$*, Math. Comp.**61**(1993), no. 203, 381–391. MR**1202611**, DOI 10.1090/S0025-5718-1993-1202611-7 - 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**, DOI 10.1090/S0025-5718-1980-0572872-7 - 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**, DOI 10.1023/A:1009764017495 - 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**, DOI 10.1007/978-3-540-79456-1_{2}8 - Victor Shoup,
*Number theory library (NTL)*, http://www.shoup.net/ntl. - Abraham Sinkov,
*Elementary cryptanalysis*, 2nd ed., Anneli Lax New Mathematical Library, vol. 22, Mathematical Association of America, Washington, DC, 2009. A mathematical approach; Revised, updated and with a preface by Todd Feil. MR**2530836** - 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**, DOI 10.1007/3-540-45708-9_{1}9 - Ming Zhi Zhang,
*A method for finding large Carmichael numbers*, Sichuan Daxue Xuebao**29**(1992), no. 4, 472–479 (Chinese, with English and Chinese summaries). MR**1210286**

## 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
- MR Author ID: 805175
- Email: ashallue@iwu.edu
- 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 - © Copyright 2013
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp.
**83**(2014), 899-915 - MSC (2010): Primary 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-2013-02737-8
- MathSciNet review: 3143697