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