AI Impacts Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Progress in general purpose factoring ======

// Published 16 March, 2017; last updated 07 October, 2017 //

<HTML>
<p>The largest number factored to date grew by about 4.5 decimal digits per year over the past roughly half-century. Between 1988, when we first have good records, and 2009, when the largest number to date was factored, progress was roughly 6 decimal digits per year.</p>
</HTML>


<HTML>
<p>Progress was relatively smooth during the two decades for which we have good records, with half of new records being less than two years after the previous record, and the biggest advances between two records representing about five years of prior average progress.</p>
</HTML>


<HTML>
<p>Computing hardware used in record-setting factorings increased ten-thousand-fold over the records (roughly in line with falling computing prices), and we are unsure how much of overall factoring progress is due to this.</p>
</HTML>



===== Support =====


==== Background ====


<HTML>
<p>To <a href="https://en.wikipedia.org/wiki/Integer_factorization">factor an integer</a> N is to find two integers <em>l</em> and <em>m</em> such that <em>l*m</em> = N. There is no known efficient algorithm for the general case of this problem. While there are <a href="https://en.wikipedia.org/wiki/Integer_factorization#Special-purpose">special purpose algorithms</a> for some kinds of numbers with particular forms, here we are interested in ‘<a href="https://en.wikipedia.org/wiki/Integer_factorization#General-purpose">general purpose</a>‘ factoring algorithms. These factor any composite number with running time only dependent on the size of that number.<span class="easy-footnote-margin-adjust" id="easy-footnote-1-758"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-1-758" title='By &amp;#8220;general purpose&amp;#8221;, we mean a factoring algorithms whose running time is dependent upon only the size of the number being factored (i.e. not on the size of the prime factors or any particular form of the number). &amp;#8211; &lt;a href="http://www.crypto-world.com/FactorRecords.html"&gt;Scott Contini&lt;/a&gt;'><sup>1</sup></a></span></p>
</HTML>


<HTML>
<p>Factoring numbers large enough to break records frequently takes months or years, even with a large number of computers. For instance, RSA-768, the largest number to be factored to date, had 232 decimal digits and was factored over multiple years ending in 2009, using the equivalent of almost 2000 years of computing on a single 2.2 GHz AMD Opteron processor with 2GB RAM.<span class="easy-footnote-margin-adjust" id="easy-footnote-2-758"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-2-758" title='The following effort was involved. We spent half a year on 80 processors on polynomial selection. This was about 3% of the main task, the sieving, which was done on many hundreds of machines and took almost two years. On a single core 2.2 GHz AMD Opteron processor with 2 GB RAM, sieving would have taken about fifteen hundred years. &amp;#8230;Our computation required more than 10&lt;sup&gt;20&lt;/sup&gt; operations. With the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron, on the order of 2&lt;sup&gt;67&lt;/sup&gt; instructions were carried out. &amp;#8211; &lt;a href="http://eprint.iacr.org/2010/006.pdf"&gt;&lt;em&gt;Factorization of a 768-bit RSA modulus&lt;/em&gt;, Kleinjung et al, 2010&lt;/a&gt;'><sup>2</sup></a></span></p>
</HTML>


<HTML>
<p>It is important to know what size numbers can be factored with current technology, because factoring large numbers is central to cryptographic security schemes such as <a href="https://en.wikipedia.org/wiki/RSA_(cryptosystem)">RSA</a>.<span class="easy-footnote-margin-adjust" id="easy-footnote-3-758"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-3-758" title='When the numbers are very large, no efficient, &lt;a class="mw-redirect" title="Quantum computer" href="https://en.wikipedia.org/wiki/Quantum_computer"&gt;non-quantum&lt;/a&gt; integer &lt;a title="Factorization" href="https://en.wikipedia.org/wiki/Factorization"&gt;factorization&lt;/a&gt; &lt;a title="Algorithm" href="https://en.wikipedia.org/wiki/Algorithm"&gt;algorithm&lt;/a&gt; is known&amp;#8230;However, it has not been proven that no efficient algorithm exists. The presumed difficulty of this problem is at the heart of widely used algorithms in &lt;a title="Cryptography" href="https://en.wikipedia.org/wiki/Cryptography"&gt;cryptography&lt;/a&gt; such as &lt;a class="mw-redirect" title="RSA (algorithm)" href="https://en.wikipedia.org/wiki/RSA_(algorithm)"&gt;RSA&lt;/a&gt;. &amp;#8211; &lt;a href="https://en.wikipedia.org/wiki/Integer_factorization"&gt;&lt;em&gt;Integer Factorization&lt;/em&gt;, Wikipedia, accessed Feb 10 2017&lt;/a&gt;'><sup>3</sup></a></span> Much of the specific data we have on progress in factoring is from the <a href="https://en.wikipedia.org/wiki/RSA_Factoring_Challenge">RSA Factoring Challenge:</a> a contest funded by <a href="https://en.wikipedia.org/wiki/RSA_Security">RSA Laboratories</a>, offering large cash prizes for factoring various numbers on their <a href="https://en.wikipedia.org/wiki/RSA_numbers">list</a> of 54 (the ‘<a href="https://en.wikipedia.org/wiki/RSA_numbers">RSA Numbers</a>‘).<span class="easy-footnote-margin-adjust" id="easy-footnote-4-758"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-4-758" title='&amp;#8216;The RSA Factoring challenge was an effort, sponsored by RSA Laboratories, to learn about the actual difficulty of factoring large numbers of the type used in RSA keys.&amp;#8217; &amp;#8211;&lt;a href="https://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm"&gt;RSA Factoring Challenge FAQ&lt;/a&gt;'><sup>4</sup></a></span> Their numbers are <a href="https://en.wikipedia.org/wiki/Semiprimes">semiprimes</a> (i.e. each has only two prime factors), and each number has between 100 and 617 decimal digits.<span class="easy-footnote-margin-adjust" id="easy-footnote-5-758"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-5-758" title='In &lt;a title="Mathematics" href="https://en.wikipedia.org/wiki/Mathematics"&gt;mathematics&lt;/a&gt;, the &lt;b&gt;RSA numbers&lt;/b&gt; are a set of large &lt;a class="mw-redirect" title="Semiprimes" href="https://en.wikipedia.org/wiki/Semiprimes"&gt;semiprimes&lt;/a&gt; (numbers with exactly two &lt;a title="Prime factor" href="https://en.wikipedia.org/wiki/Prime_factor"&gt;prime factors&lt;/a&gt;) that are part of the &lt;a title="RSA Factoring Challenge" href="https://en.wikipedia.org/wiki/RSA_Factoring_Challenge"&gt;RSA Factoring Challenge&lt;/a&gt;&amp;#8230;.&lt;a class="mw-redirect" title="RSA Laboratories" href="https://en.wikipedia.org/wiki/RSA_Laboratories"&gt;RSA Laboratories&lt;/a&gt; published a number of semiprimes with 100 to 617 &lt;a title="Decimal" href="https://en.wikipedia.org/wiki/Decimal"&gt;decimal&lt;/a&gt; digits. Cash prizes of varying size were offered for factorization of some of them. &amp;#8211; &lt;a href="https://en.wikipedia.org/wiki/RSA_numbers"&gt;Wikipedia&lt;/a&gt;'><sup>5</sup></a></span></p>
</HTML>


<HTML>
<p>The records collected on this page are for factoring specific large numbers, using algorithms whose performance depends on nothing but the scale of the number (general purpose algorithms). So a record for a specific N-digit number does not imply that that was the first time any N-digit number was factored. However if it is an important record, it strongly suggests that it was difficult to factor arbitrary N-digit numbers at the time, so others are unlikely to have been factored very much earlier, using general purpose algorithms. For a sense of scale, our records here include at least eight numbers that were not the largest ever factored at the time yet appear to have been considered difficult to factor, and many of those were factored five to seven years after the first time a number so large was factored. For numbers that are the first of their size in our records, we expect that they mostly are the first of that size to have been factored, with the exception of early records.<span class="easy-footnote-margin-adjust" id="easy-footnote-6-758"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-6-758" title="This is because record-breaking numbers appear to be expensive to factor and so unlikely to be done without good reason, or without the attempt being known, and authors on this topic appear to focus on the number of digits that can be factored, so if other larger numbers had been factored earlier, we expect that we would have seen them mentioned. The smallest RSA numbers are an exception, because they appear to have been selected to already be achievable when the contest began, and we do not have much data from before the contest."><sup>6</sup></a></span></p>
</HTML>


<HTML>
<p>Once a number of a certain size has been factored, it will still take years before numbers at that scale can be cheaply factored. For instance, while 116 digit numbers had been factored by 1991 (see below), it was an achievement in 1996 to <a href="http://www.crypto-world.com/announcements/siqs116.text">factor</a> a different specific 116 digit number, which had been on a ‘most wanted list’.</p>
</HTML>


<HTML>
<p>If we say a digit record is broken in some year (rather than a record for a particular number), we mean that that is the first time that any number with at least that many digits has been factored using a <a href="https://en.wikipedia.org/wiki/Integer_factorization#General-purpose">general purpose factoring algorithm.</a></p>
</HTML>


<HTML>
<p>Our impression is that length of numbers factored is a measure people were trying to make progress on, so that progress here is the result of relatively consistent effort to make progress, rather than occasional incidental overlap with some other goal.</p>
</HTML>


<HTML>
<p>Most of the research on this page is adapted from Katja Grace’s <a href="https://intelligence.org/files/AlgorithmicProgress.pdf">2013 report</a>, with substantial revision.</p>
</HTML>


==== Recent rate of progress ====


=== Data sources ===


<HTML>
<p>These are the sources of data we draw on for factoring records:</p>
</HTML>


<HTML>
<ul>
<li><div class="li">Wikipedia’s <a href="https://en.wikipedia.org/wiki/RSA_Factoring_Challenge">table</a> of ‘RSA numbers’, from the <a href="https://en.wikipedia.org/wiki/RSA_Factoring_Challenge">RSA factoring challenge</a> (active ’91-’07). Of these 19 have been factored, of 54 total. The table includes numbers of digits, dates, and cash prizes offered. (<a href="https://en.wikipedia.org/wiki/RSA_Factoring_Challenge">data</a>)
                </div></li>
<li><div class="li">Scott Contini’s list of ‘<a href="http://www.crypto-world.com/FactorRecords.html">general purpose factoring records’ since 1990</a>’, which includes the nine RSA numbers that set digit records, and three numbers that appear to have set digit records as part of the ‘<a href="https://en.wikipedia.org/wiki/Cunningham_project">Cunningham Project</a>‘. This list contains digits, date, solution time, and algorithm used.
                </div></li>
<li><div class="li">Two estimates of how many digits could be factored in earlier decades from an <a href="http://www.ams.org/notices/199612/pomerance.pdf">essay</a> by Carl Pomerance.<span class="easy-footnote-margin-adjust" id="easy-footnote-7-758"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-7-758" title='&amp;#8220;It is the best of times for the game of factoring large numbers into their prime factors. In 1970 it was barely possible to factor “hard” 20-digit numbers. In 1980, in the heyday of the Brillhart-Morrison continued fraction factoring algorithm, factoring of 50-digit numbers was becoming commonplace. In 1990 my own quadratic sieve factoring algorithm had doubled the length of the numbers that could be factored, the record having 116 digits.&amp;#8221; &amp;#8211; A Tale of Two Sieves, &lt;a href="http://www.ams.org/notices/199612/pomerance.pdf"&gt;Carl Pomerance&lt;/a&gt;, 1996'><sup>7</sup></a></span>
</div></li>
<li><div class="li">
<a href="http://www.crypto-world.com/announcements/RSA120.txt">This announcement</a>, that suggests that the 116 digit general purpose factoring record was set in January 1991, contrary to Factorworld and Pomerance.<span class="easy-footnote-margin-adjust" id="easy-footnote-8-758"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-8-758" title=' &amp;#8216;This is a new general purpose factoring record, beating the old 116-digit&lt;br /&gt; record that was set in January 1991, more than two years ago.&amp;#8217; &amp;#8211; &lt;a href="http://www.crypto-world.com/announcements/RSA120.txt"&gt;Factorization of RSA-120, Lenstra, 1993&lt;/a&gt; '><sup>8</sup></a></span> We will ignore it, since the dates are too close to matter substantially, and the other two sources agree.
                </div></li>
<li><div class="li">A 1988 paper <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.1434&amp;rep=rep1&amp;type=pdf">discussing</a> recent work and constraints on possibility at that time. It lists four ‘state of the art’ efforts at factorization, among which the largest number factored using a general purpose algorithm (<a href="https://en.wikipedia.org/wiki/Quadratic_sieve#Multiple_polynomials">MPQS</a>) has 95 digits.<span class="easy-footnote-margin-adjust" id="easy-footnote-9-758"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-9-758" title='Before making our question more precise, let us illustrate its vagueness with four examples which, in the summer of 1988, represented the state of the art in factoring.&lt;br /&gt; (i) In [7, 24] Bob Silverman et al. describe their implementation of the multiple polynomial quadratic sieve algorithm (mpqs) on a network of 24 SUN-3 workstations. Using the idle cycles on these workstations, 90 digit integers have been factored in about six weeks (elapsed time).&lt;br /&gt; (ii) In [21] Herman te Riele et al. describe their implementation of the same algorithm on two different supercomputers. They factored a 92 digit integer using 95 hours of CPU time on a NEC SX-2.&lt;br /&gt; (iii) ‘Red’ Alford and Carl Pomerance implemented mpqs on 100 IBM PC’s; it took them about four months to factor a 95 digit integer.&lt;br /&gt; (iv) In [20] Carl Pomerance et al. propose to build a special purpose mpqs machine ‘which should cost about $20,000 in parts to build and which should be able to factor 100 digit integers in a month.’&lt;br /&gt; &amp;#8211; &lt;a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.1434&amp;amp;rep=rep1&amp;amp;type=pdf"&gt;Lenstra et al 1988&lt;/a&gt;'><sup>9</sup></a></span> It claims that 106 digits had been factored by 1988, which implies that the early RSA challenge numbers were not state of the art. <span class="easy-footnote-margin-adjust" id="easy-footnote-10-758"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-10-758" title='&amp;#8220;At the time Of writing this paper we have factored two 93, one 96, one 100, one 102, and 358 one 106 digit number using mpqs, and we m working on a 103 digit number, for all these numbers extensive ecm attempts had failed. &amp;#8220;- &lt;a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.1434&amp;amp;rep=rep1&amp;amp;type=pdf"&gt;Lenstra et al 1988&lt;/a&gt; '><sup>10</sup></a></span> Together these suggest that the work in the paper is responsible for moving the record from 95 to 106 digits, and this matches our impressions from elsewhere though we do not know of a specific claim to this effect.
                </div></li>
<li><div class="li">This ‘<a href="http://www.ontko.com/pub/rayo/primes/hr_rsa.txt">RSA honor roll</a>‘ contains meta-data for the RSA solutions.
                </div></li>
<li><div class="li">
<a href="https://books.google.com/books?id=yyfS7MKQhJUC&amp;lpg=PA45&amp;ots=ZuITD7DllA&amp;dq=alford%20pomerance%2095%20digit&amp;pg=PA44#v=onepage&amp;q=107-digit&amp;f=false">Cryptography and Computational Number Theory</a> (1989), Carl Pomerance and Shafi Goldwasser.<span class="easy-footnote-margin-adjust" id="easy-footnote-11-758"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-11-758" title="e.g. p44 mentions the 107-digit record and some details."><sup>11</sup></a></span>
</div></li>
</ul>
</HTML>


<HTML>
<p><em>Excel spreadsheet containing our data for download: <a href="http://aiimpacts.org/wp-content/uploads/2017/03/Factoring-data-2017-1.xlsx">Factoring data 2017</a></em></p>
</HTML>


==== Trends ====


=== Digits by year ===


<HTML>
<p>Figure 1 shows how the scale of numbers that could be factored (using general purpose methods) grew over the last half-century (as of 2017). In red are the numbers that broke the record for the largest number of digits, as far as we know.</p>
</HTML>


<HTML>
<p>From it we see that since 1970, the numbers that can be factored have increased from around twenty digits to 232 digits, for an average of about 4.5 digits per year.</p>
</HTML>


<HTML>
<p>After the first record we have in 1988, we know of thirteen more records being set, for an average of one every 1.6 years between 1988 and 2009. Half of these were set the same or the following year as the last record, and the largest gap between records was four years. As of 2017, seven years have passed without further records being set.</p>
</HTML>


<HTML>
<p>The largest amount of progress seen in a single step is the last one—32 additional digits at once, or over five years of progress at the average rate seen since 1988 just prior to that point. The 200 digit record was also around five years of progress.</p>
</HTML>


<HTML>
<figure aria-describedby="caption-attachment-816" class="wp-caption alignnone" id="attachment_816" style="width: 600px">
<a href="http://aiimpacts.org/wp-content/uploads/2017/03/Factoring-records-March-2017-with-labels-and-axes.png"><img class="wp-image-816" height="504" src="https://aiimpacts.org/wp-content/uploads/2017/03/Factoring-records-March-2017-with-labels-and-axes.png" width="600"/></a>
<figcaption class="wp-caption-text" id="caption-attachment-816">
                  Figure 1: Size of numbers (in decimal digits) that could be factored over recent history. Green ‘approximate state of the art’ points do not necessarily represent specific numbers or the very largest that could be at that time—they are qualitative estimates. The other points represent specific large numbers being factored, either as the first number of that size ever to be factored (red) or not (orange). Dates are accurate to the year. Some points are annotated with decimal digit size, for ease of reading.
                </figcaption>
</figure>
</HTML>


=== Hardware inputs ===


<HTML>
<p>New digit records tend to use more computation, which makes progress in software alone hard to measure. At any point in the past it was in principle possible to factor larger numbers with more hardware. So the records we see are effectively records for what can be done with however much hardware anyone is willing to purchase for the purpose. Which grows from a combination of software improvements, hardware improvements, and increasing wealth among other things. Figure 2 shows how computing used for solutions increased with time.</p>
</HTML>


<HTML>
<figure aria-describedby="caption-attachment-813" class="wp-caption alignnone" id="attachment_813" style="width: 600px">
<a href="http://aiimpacts.org/wp-content/uploads/2017/03/time-to-factor.jpeg"><img alt="CPU time to factor numbers. Measured in 1,000 MIPS-years before 2000, and in GHz-years after 2000; note that these are not directly comparable, and the conversion here is approximate. Data from Contini (2010)." class="wp-image-813" height="336" loading="lazy" sizes="(max-width: 600px) 100vw, 600px" src="https://aiimpacts.org/wp-content/uploads/2017/03/time-to-factor.jpeg" srcset="https://aiimpacts.org/wp-content/uploads/2017/03/time-to-factor.jpeg 1408w, https://aiimpacts.org/wp-content/uploads/2017/03/time-to-factor-300x168.jpeg 300w, https://aiimpacts.org/wp-content/uploads/2017/03/time-to-factor-768x430.jpeg 768w, https://aiimpacts.org/wp-content/uploads/2017/03/time-to-factor-1024x573.jpeg 1024w" width="600"/></a>
<figcaption class="wp-caption-text" id="caption-attachment-813">
                  Figure 2: CPU time to factor digit-record breaking numbers. Measured in 1,000 MIPS-years before 2000, and in GHz-years after 2000. These are similar, but not directly comparable, so the conversion here is approximate. Data from <a href="http://www.crypto-world.com/FactorRecords.html">Contini (2010)</a>. Figure from <a href="https://intelligence.org/files/AlgorithmicProgress.pdf">Grace (2013)</a>. (Original caption: “Figure 31 shows CPU times for the FactorWorld records. These times have increased by a factor of around ten thousand since 1990. At 2000 the data changes from being in MIPS-years to 1 GHz CPU-years. These aren’t directly comparable. The figure uses 1 GHz CPU-year = 1,000 MIPS-years, because it is in the right ballpark and simple, and no estimates were forthcoming. The figure suggests that a GHz CPU-year is in fact worth a little more, given that the data seems to dip around 2000 with this conversion.”)
                </figcaption>
</figure>
</HTML>


<HTML>
<p>In the two decades between 1990 and 2010, figure 2 suggests that computing used has increased by about four orders of magnitude. During that time computing available per dollar has probably increased by a factor of <a href="/doku.php?id=ai_timelines:trends_in_the_cost_of_computing">ten every four years or so</a>, for about five orders of magnitude. So we are seeing something like digits that can be factored at a fixed expense.</p>
</HTML>


===== Further research =====


<HTML>
<ul>
<li><div class="li">Discover how computation used is expected to scale with the number of digits factored, and use that to factor out increased hardware use from this trendline, and so measure non-hardware progress alone.</div></li>
<li><div class="li">This area appears to have seen a small number of new algorithms, among smaller changes in how they are implemented. Check how much the new algorithms affected progress, and similarly for anything else with apparent potential for large impacts (e.g. a move to borrowing other people’s spare computing hardware via the internet, rather than paying for hardware).</div></li>
<li><div class="li">Find records from earlier times.</div></li>
<li><div class="li">Some numbers had large prizes associated with their factoring, and others of similar sizes had none. Examine the relationship between progress and financial incentives in this case.</div></li>
<li><div class="li">
<a href="https://homes.cerias.purdue.edu/~ssw/cun/index.html">The Cunningham Project</a> maintains a vast collection of recorded factorings of numbers, across many scales, along with dates, algorithms used, and people or projects responsible. Gather that data, and use to make similar inferences to the data we have here (see <em>Relevance</em> section below for more on that).
                </div></li>
</ul>
</HTML>




===== Relevance =====


<HTML>
<p>We are interested in factoring, because it is an example of an algorithmic problem on which there has been well-documented progress. Such examples should inform our expectations for algorithmic problems in general (including problems in AI), regarding:</p>
</HTML>


<HTML>
<ul>
<li><div class="li">How smooth or jumpy progress tends to be, and related characteristics of its shape.</div></li>
<li><div class="li">How much warning there is of rapid progress.</div></li>
<li><div class="li">How events that are qualitatively considered ‘conceptual insights’ or ‘important progress’ relate to measured performance progress.</div></li>
<li><div class="li">How software progress interacts with hardware (for instance, does a larger step of software progress cause a disproportionate increase in overall software output, because of redistribution of hardware?).</div></li>
<li><div class="li">If performance is improving, how much of that is because of better hardware, and how much is because of better algorithms or other aspects of software.</div></li>
</ul>
</HTML>




===== Assorted sources =====


<HTML>
<ul>
<li><div class="li">
<a href="https://www.fdi.ucm.es/profesor/m_alonso/Documentos/factorizacion/arjlensfac.pdf">Integer factoring</a>
</div></li>
<li><div class="li">
<a href="https://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm">RSA Factoring Challenge FAQ</a>
</div></li>
<li><div class="li">Other pages around e.g. <a href="https://members.loria.fr/PZimmermann/records/factor-previous.html#general">this one</a>, seem to have data for run times etc of other things
                </div></li>
<li><div class="li">
<a href="https://members.loria.fr/PZimmermann/records/gnfsrecord.jpg">Graph of history of factorization with GNFS</a>
</div></li>
<li><div class="li">More <a href="https://members.loria.fr/PZimmermann/records/factor.html">data on records</a>, probably largely overlapping, including different methods (that I have probably seen elsewhere)
                </div></li>
<li><div class="li">Announcements such as <a href="http://www.crypto-world.com/announcements/siqs116.text">this one</a> contain much info, many on Scott Contini’s page.
                </div></li>
</ul>
</HTML>






<HTML>
<ol class="easy-footnotes-wrapper">
<li><div class="li">
<span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-1-758"></span>By “general purpose”, we mean a factoring algorithms whose running time is dependent upon only the size of the number being factored (i.e. not on the size of the prime factors or any particular form of the number). – <a href="http://www.crypto-world.com/FactorRecords.html">Scott Contini</a><a class="easy-footnote-to-top" href="#easy-footnote-1-758"></a>
</div></li>
<li><div class="li">
<span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-2-758"></span>The following effort was involved. We spent half a year on 80 processors on polynomial selection. This was about 3% of the main task, the sieving, which was done on many hundreds of machines and took almost two years. On a single core 2.2 GHz AMD Opteron processor with 2 GB RAM, sieving would have taken about fifteen hundred years. …Our computation required more than 10<sup>20</sup> operations. With the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron, on the order of 2<sup>67</sup> instructions were carried out. – <a href="http://eprint.iacr.org/2010/006.pdf"><em>Factorization of a 768-bit RSA modulus</em>, Kleinjung et al, 2010</a><a class="easy-footnote-to-top" href="#easy-footnote-2-758"></a>
</div></li>
<li><div class="li">
<span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-3-758"></span>When the numbers are very large, no efficient, <a class="mw-redirect" href="https://en.wikipedia.org/wiki/Quantum_computer" title="Quantum computer">non-quantum</a> integer <a href="https://en.wikipedia.org/wiki/Factorization" title="Factorization">factorization</a> <a href="https://en.wikipedia.org/wiki/Algorithm" title="Algorithm">algorithm</a> is known…However, it has not been proven that no efficient algorithm exists. The presumed difficulty of this problem is at the heart of widely used algorithms in <a href="https://en.wikipedia.org/wiki/Cryptography" title="Cryptography">cryptography</a> such as <a class="mw-redirect" href="https://en.wikipedia.org/wiki/RSA_(algorithm)" title="RSA (algorithm)">RSA</a>. – <a href="https://en.wikipedia.org/wiki/Integer_factorization"><em>Integer Factorization</em>, Wikipedia, accessed Feb 10 2017</a><a class="easy-footnote-to-top" href="#easy-footnote-3-758"></a>
</div></li>
<li><div class="li">
<span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-4-758"></span>‘The RSA Factoring challenge was an effort, sponsored by RSA Laboratories, to learn about the actual difficulty of factoring large numbers of the type used in RSA keys.’ –<a href="https://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm">RSA Factoring Challenge FAQ</a><a class="easy-footnote-to-top" href="#easy-footnote-4-758"></a>
</div></li>
<li><div class="li">
<span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-5-758"></span>In <a href="https://en.wikipedia.org/wiki/Mathematics" title="Mathematics">mathematics</a>, the <b>RSA numbers</b> are a set of large <a class="mw-redirect" href="https://en.wikipedia.org/wiki/Semiprimes" title="Semiprimes">semiprimes</a> (numbers with exactly two <a href="https://en.wikipedia.org/wiki/Prime_factor" title="Prime factor">prime factors</a>) that are part of the <a href="https://en.wikipedia.org/wiki/RSA_Factoring_Challenge" title="RSA Factoring Challenge">RSA Factoring Challenge</a>….<a class="mw-redirect" href="https://en.wikipedia.org/wiki/RSA_Laboratories" title="RSA Laboratories">RSA Laboratories</a> published a number of semiprimes with 100 to 617 <a href="https://en.wikipedia.org/wiki/Decimal" title="Decimal">decimal</a> digits. Cash prizes of varying size were offered for factorization of some of them. – <a href="https://en.wikipedia.org/wiki/RSA_numbers">Wikipedia</a><a class="easy-footnote-to-top" href="#easy-footnote-5-758"></a>
</div></li>
<li><div class="li">
<span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-6-758"></span>This is because record-breaking numbers appear to be expensive to factor and so unlikely to be done without good reason, or without the attempt being known, and authors on this topic appear to focus on the number of digits that can be factored, so if other larger numbers had been factored earlier, we expect that we would have seen them mentioned. The smallest RSA numbers are an exception, because they appear to have been selected to already be achievable when the contest began, and we do not have much data from before the contest.<a class="easy-footnote-to-top" href="#easy-footnote-6-758"></a>
</div></li>
<li><div class="li">
<span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-7-758"></span>“It is the best of times for the game of factoring large numbers into their prime factors. In 1970 it was barely possible to factor “hard” 20-digit numbers. In 1980, in the heyday of the Brillhart-Morrison continued fraction factoring algorithm, factoring of 50-digit numbers was becoming commonplace. In 1990 my own quadratic sieve factoring algorithm had doubled the length of the numbers that could be factored, the record having 116 digits.” – A Tale of Two Sieves, <a href="http://www.ams.org/notices/199612/pomerance.pdf">Carl Pomerance</a>, 1996<a class="easy-footnote-to-top" href="#easy-footnote-7-758"></a>
</div></li>
<li><div class="li">
<span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-8-758"></span> ‘This is a new general purpose factoring record, beating the old 116-digit<br/>
                  record that was set in January 1991, more than two years ago.’ – <a href="http://www.crypto-world.com/announcements/RSA120.txt">Factorization of RSA-120, Lenstra, 1993</a> <a class="easy-footnote-to-top" href="#easy-footnote-8-758"></a>
</div></li>
<li><div class="li">
<span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-9-758"></span>Before making our question more precise, let us illustrate its vagueness with four examples which, in the summer of 1988, represented the state of the art in factoring.<br/>
                  (i) In [7, 24] Bob Silverman et al. describe their implementation of the multiple polynomial quadratic sieve algorithm (mpqs) on a network of 24 SUN-3 workstations. Using the idle cycles on these workstations, 90 digit integers have been factored in about six weeks (elapsed time).<br/>
                  (ii) In [21] Herman te Riele et al. describe their implementation of the same algorithm on two different supercomputers. They factored a 92 digit integer using 95 hours of CPU time on a NEC SX-2.<br/>
                  (iii) ‘Red’ Alford and Carl Pomerance implemented mpqs on 100 IBM PC’s; it took them about four months to factor a 95 digit integer.<br/>
                  (iv) In [20] Carl Pomerance et al. propose to build a special purpose mpqs machine ‘which should cost about $20,000 in parts to build and which should be able to factor 100 digit integers in a month.’<br/>
                  – <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.1434&amp;rep=rep1&amp;type=pdf">Lenstra et al 1988</a><a class="easy-footnote-to-top" href="#easy-footnote-9-758"></a>
</div></li>
<li><div class="li">
<span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-10-758"></span>“At the time Of writing this paper we have factored two 93, one 96, one 100, one 102, and 358 one 106 digit number using mpqs, and we m working on a 103 digit number, for all these numbers extensive ecm attempts had failed. “- <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.1434&amp;rep=rep1&amp;type=pdf">Lenstra et al 1988</a> <a class="easy-footnote-to-top" href="#easy-footnote-10-758"></a>
</div></li>
<li><div class="li">
<span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-11-758"></span>e.g. p44 mentions the 107-digit record and some details.<a class="easy-footnote-to-top" href="#easy-footnote-11-758"></a>
</div></li>
</ol>
</HTML>
AI Impacts Wiki

User Tools

Site Tools

Page Tools
