Constructing Carmichael numbers through improved subset-product algorithms

Alford, \fbox{W. R. }; Grantham, Jon; Hayman, Steven; Shallue, Andrew

doi:10.1090/S0025-5718-2013-02737-8

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