Constructing Carmichael numbers through improved subset-product algorithms

W.R. Alford, Jon Grantham, Steven Hayman, Andrew Shallue

Research output: Journal ArticleArticlepeer-review

Abstract

<div class="line" id="line-21"> <span style='color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;'> We have constructed a Carmichael number with 10,333,229,505 prime factors, and have also constructed Carmichael numbers with&nbsp; </span> <img src="http://www.ams.org/journals/mcom/2014-83-286/S0025-5718-2013-02737-8/images/img1.gif"/> <span style='color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;'> &nbsp;prime factors for every&nbsp; </span> <img src="http://www.ams.org/journals/mcom/2014-83-286/S0025-5718-2013-02737-8/images/img2.gif"/> <span style='color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;'> &nbsp;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&nbsp; </span> <img src="http://www.ams.org/journals/mcom/2014-83-286/S0025-5718-2013-02737-8/images/img3.gif"/> <span style='color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;'> with the property that&nbsp; </span> <img src="http://www.ams.org/journals/mcom/2014-83-286/S0025-5718-2013-02737-8/images/img4.gif"/> <span style='color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;'> &nbsp;divides a highly composite&nbsp; </span> <img src="http://www.ams.org/journals/mcom/2014-83-286/S0025-5718-2013-02737-8/images/img5.gif"/> <span style='color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;'> . </span></div>
Original languageAmerican English
JournalMathematics of Computation
Volume83
StatePublished - 2014

Keywords

  • subset sum
  • Carmichael numbers

Disciplines

  • Theory and Algorithms
  • Mathematics
  • Number Theory

Cite this