Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspxToday I'm going to talk about how the quadratic sieve factoring algorithm works, giving a comprehensive description assuming knowledge of only basic university-level mathematics.
The foundation of the most popular public-key cryptography algorithmen-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#9871648Sun, 16 Aug 2009 17:34:14 GMT91d46819-8472-40ad-a661-2c78acb4018c:9871648Lieven van der Heide<p>Actually, ignore the last sentence in my previous post, as I was confused with something else:)</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9871648" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#9871302Sun, 16 Aug 2009 02:43:05 GMT91d46819-8472-40ad-a661-2c78acb4018c:9871302Lieven van der Heide<p>Maybe this was intended to be obvious from the context, but note that raising a number to (p−1)/2 to test if it's a quadratic residue only works if p is prime. For non prime modulus, you have to raise to totient(p) / 2.</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9871302" width="1" height="1"> Developing for Developers Factoring large numbers with quadratic sieve | storage benchhttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#9782191Fri, 19 Jun 2009 10:45:19 GMT91d46819-8472-40ad-a661-2c78acb4018c:9782191 Developing for Developers Factoring large numbers with quadratic sieve | storage bench<p>PingBack from <a rel="nofollow" target="_new" href="http://thestoragebench.info/story.php?id=5411">http://thestoragebench.info/story.php?id=5411</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9782191" width="1" height="1"> Developing for Developers Factoring large numbers with quadratic sieve | patio sethttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#9771647Thu, 18 Jun 2009 05:07:37 GMT91d46819-8472-40ad-a661-2c78acb4018c:9771647 Developing for Developers Factoring large numbers with quadratic sieve | patio set<p>PingBack from <a rel="nofollow" target="_new" href="http://patiosetsite.info/story.php?id=674">http://patiosetsite.info/story.php?id=674</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9771647" width="1" height="1"> Developing for Developers Factoring large numbers with quadratic sieve | Outdoor Ceiling Fanshttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#9667571Sun, 31 May 2009 10:09:57 GMT91d46819-8472-40ad-a661-2c78acb4018c:9667571 Developing for Developers Factoring large numbers with quadratic sieve | Outdoor Ceiling Fans<p>PingBack from <a rel="nofollow" target="_new" href="http://outdoorceilingfansite.info/story.php?id=1072">http://outdoorceilingfansite.info/story.php?id=1072</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9667571" width="1" height="1">Xun’s blog » Blog Archive » ????????????http://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#9008527Tue, 21 Oct 2008 05:11:41 GMT91d46819-8472-40ad-a661-2c78acb4018c:9008527Xun’s blog » Blog Archive » ????????????<p>PingBack from <a rel="nofollow" target="_new" href="http://uthz.com/2008/10/20/%e7%b4%a0%e6%95%b0%e5%88%86%e8%a7%a3/">http://uthz.com/2008/10/20/%e7%b4%a0%e6%95%b0%e5%88%86%e8%a7%a3/</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9008527" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#8782307Mon, 28 Jul 2008 07:02:11 GMT91d46819-8472-40ad-a661-2c78acb4018c:8782307mark mcgoveran<p>I have read this six times and the light comes on a little brighter each time!! I am doing some number theroy stuff as a hobby, and this diesn't seem to apply to what I am doing at all but it is great to attempt to understand it.</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=8782307" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#8567503Sun, 01 Jun 2008 14:28:45 GMT91d46819-8472-40ad-a661-2c78acb4018c:8567503mohan srinivasan<p>Excellent way to explain to a layman.</p>
<p>I found it very enlightening. brings out the basics very clearly.</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=8567503" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#8563616Fri, 30 May 2008 19:28:45 GMT91d46819-8472-40ad-a661-2c78acb4018c:8563616Greg Johnson<p>I ran across this article while looking at the wquation for a qudratic reduction curve. I am not a mathematition in any way but need to calculate a cure for an application. I thought you may be able to answer a question.</p>
<p>I an using the equation y= ax2 + bx + c (sorry couldn't do exponent). In this equation I have determined the meaining of x and c but not a nad b. Is there a culculation for a and b?</p>
<p>Any help would be apptrciated</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=8563616" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#8527158Wed, 21 May 2008 11:55:33 GMT91d46819-8472-40ad-a661-2c78acb4018c:8527158Noelyuan<p>Thanks a billion! This article considerably enhance my understanding toward Quadratic Sieve.</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=8527158" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#6460044Thu, 22 Nov 2007 00:45:45 GMT91d46819-8472-40ad-a661-2c78acb4018c:6460044epsi<p>Thanks for your explanation of QS. It was very useful. I don't know why even in textbooks, authors manage to drown the fish as we say.</p>
<p>I came up with a variant of Fermat's method that does not require incrementing a by 1. I only consider numbers of the form 6K+1 and 6k-1. Any number that is not of that form is either divisible by 2 or by 3. Factors of 2 and 3 can be easily extracted I assume leaving only a final number of the form 6k+/-1.</p>
<p>Anyway, I am going to see if I can use the property of making a2-n values a square S.</p>
<p>It's the only thing I wasn't aware of.</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=6460044" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#3691612Wed, 04 Jul 2007 19:36:24 GMT91d46819-8472-40ad-a661-2c78acb4018c:3691612Tom<p>In your explanation of reducing the matrix, you say that one needs "more columns than rows" to ensure a zero row. This is incorrect (and probably just a typo), as you state in one of your responses the correct answer that you need more rows than columns. I just thought you might want to make the correction.</p>
<p>Also, thank you for a decent low-level description of the Quadratic Sieve and its improvements.</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=3691612" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#734315Fri, 01 Sep 2006 01:43:13 GMT91d46819-8472-40ad-a661-2c78acb4018c:734315MSDNArchiveHi Adam, that's a good question. It's rare to find an implementation of quadratic sieve in a high-level language because it depends on an efficient implementation of arbitrary-precision integers and reduction of sparse 0/1 matrices, which are easier to pull off in C, C++, or assembly language. I have no knowledge of such implementations, but it wouldn't be terribly difficult to write a basic one. Writing one with all the "bells and whistles" would be more involved and a nontrivial project.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=734315" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#730297Tue, 29 Aug 2006 20:33:17 GMT91d46819-8472-40ad-a661-2c78acb4018c:730297AdamDo you have any .NET/ VB /C# code that implements Quadratic Sieve ?<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=730297" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#728720Mon, 28 Aug 2006 21:27:58 GMT91d46819-8472-40ad-a661-2c78acb4018c:728720MSDNArchiveHi Claude. Those are good questions. To answer them:
<br>
<br>1) In the mathematical theory behind quadratic sieve, B must be chosen carefully according to a specific formula in terms of n in order to guarantee the best asymptotic running time. Carl Pomerance gives this formula:
<br>
<br>B = exp((1/2 + o(1))(log n log log n)^(1/2))
<br>
<br><a rel="nofollow" target="_new" href="http://www.math.leidenuniv.nl/~reinier/ant/sieving.pdf">http://www.math.leidenuniv.nl/~reinier/ant/sieving.pdf</a>
<br>
<br>In practice, though, the B is usually somewhat less than this "ideal" B, because the matrix reduction step (benefitting from small B) is much more memory-consuming and much more difficult to parallelize than the search for smooth numbers (benefitting form large B).
<br>
<br>2) In order to ensure for certain that we will find a nontrivial zero, linear algebra requires that the matrix have more rows than columns - in other words, that we have more smooth numbers than prime numbers less than or equal to B. In practice, it's typical to find a nontrivial zero with quite a few less factors, and it can be profitable to attempt the reduction as soon as a heuristically "good" number of smooth numbers are found. Conversely, sometimes the matrix will only have one solution, and that solution will be trivial; in this case, a good way to look for a nontrivial solution is to just find a few more smooth numbers, which (hopefully) expands the dimension of the null space.
<br>
<br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=728720" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#728383Mon, 28 Aug 2006 17:27:06 GMT91d46819-8472-40ad-a661-2c78acb4018c:728383Claude BissonnetteHi, thanks for your article, qs is something that I whish to learn for a while ... While reading, two questions comes to me and I would like you to explain more in detail if you can.
<br>
<br>1) I still can't figure out how to find the B-smooth bound for a given n. Is there a formula or guide to tell us how to establish the bound or do we have to guess it?
<br>
<br>2) How long do we have to search for smooth numbers? What would be the quantities of smooth numbers needed in order to solve the matrix? In you article you wrote "... we just need more numbers than prime factors ... " Is it the answer to my question?
<br>
<br>Claude Bissonnette <div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=728383" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#643117Thu, 22 Jun 2006 21:35:03 GMT91d46819-8472-40ad-a661-2c78acb4018c:643117MSDNArchiveThanks for your positive feedback, everyone. I assure you that incomprehensibility was not one of my goals (in this case :-). If there's anything I can do to help clarify this discussion or answer any specific questions, I'd appreciate your feedback. I do believe the quadratic sieve algorithm is accessible to everyone interested in algorithms if just explained in the right way.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=643117" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#642759Thu, 22 Jun 2006 14:34:02 GMT91d46819-8472-40ad-a661-2c78acb4018c:642759olssonGreat post as usual.
<br>
<br>And also far over my head, which I guess is part of the brilliance. Very inspiring!<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=642759" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#641742Wed, 21 Jun 2006 20:13:51 GMT91d46819-8472-40ad-a661-2c78acb4018c:641742SeshagiriI do not have any comments on this article but just wanted to say that I greatly appreciate your articles. I have subscribed to your site's rss feed and eagerly wait for new articles. The previous two on image compression and color quantization were very useful to me.
<br>
<br>Seshagiri (HP)<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=641742" width="1" height="1">re: Factoring large numbers with quadratic sievehttp://blogs.msdn.com/b/devdev/archive/2006/06/19/637332.aspx#640581Wed, 21 Jun 2006 02:25:11 GMT91d46819-8472-40ad-a661-2c78acb4018c:640581Adi OlteanWonderful post, as usual. <div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=640581" width="1" height="1">