Factoring large numbers with quadratic sieve

re: Factoring large numbers with quadratic sieve

Adi Oltean — Wed, 21 Jun 2006 02:25:11 GMT

Wonderful post, as usual.

re: Factoring large numbers with quadratic sieve

Seshagiri — Wed, 21 Jun 2006 20:13:51 GMT

I 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.

Seshagiri (HP)

re: Factoring large numbers with quadratic sieve

olsson — Thu, 22 Jun 2006 14:34:02 GMT

Great post as usual.

And also far over my head, which I guess is part of the brilliance. Very inspiring!

re: Factoring large numbers with quadratic sieve

dcoetzee — Thu, 22 Jun 2006 21:35:03 GMT

Thanks 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.

re: Factoring large numbers with quadratic sieve

Claude Bissonnette — Mon, 28 Aug 2006 17:27:06 GMT

Hi, 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.

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?

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?

Claude Bissonnette

re: Factoring large numbers with quadratic sieve

dcoetzee — Mon, 28 Aug 2006 21:27:58 GMT

Hi Claude. Those are good questions. To answer them:

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:

B = exp((1/2 + o(1))(log n log log n)^(1/2))

http://www.math.leidenuniv.nl/~reinier/ant/sieving.pdf

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).

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.

re: Factoring large numbers with quadratic sieve

Adam — Tue, 29 Aug 2006 20:33:17 GMT

Do you have any .NET/ VB /C# code that implements Quadratic Sieve ?

re: Factoring large numbers with quadratic sieve

dcoetzee — Fri, 01 Sep 2006 01:43:13 GMT

Hi 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.

re: Factoring large numbers with quadratic sieve

Tom — Wed, 04 Jul 2007 19:36:24 GMT

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.

Also, thank you for a decent low-level description of the Quadratic Sieve and its improvements.

re: Factoring large numbers with quadratic sieve

epsi — Thu, 22 Nov 2007 00:45:45 GMT

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.

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.

Anyway, I am going to see if I can use the property of making a2-n values a square S.

It's the only thing I wasn't aware of.

re: Factoring large numbers with quadratic sieve

Noelyuan — Wed, 21 May 2008 11:55:33 GMT

Thanks a billion! This article considerably enhance my understanding toward Quadratic Sieve.

re: Factoring large numbers with quadratic sieve

Greg Johnson — Fri, 30 May 2008 19:28:45 GMT

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.

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?

Any help would be apptrciated

re: Factoring large numbers with quadratic sieve

mohan srinivasan — Sun, 01 Jun 2008 14:28:45 GMT

Excellent way to explain to a layman.

I found it very enlightening. brings out the basics very clearly.

re: Factoring large numbers with quadratic sieve

mark mcgoveran — Mon, 28 Jul 2008 07:02:11 GMT

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.

Xun’s blog » Blog Archive » ????????????

Xun’s blog » Blog Archive » ???????????? — Tue, 21 Oct 2008 05:11:41 GMT

PingBack from http://uthz.com/2008/10/20/%e7%b4%a0%e6%95%b0%e5%88%86%e8%a7%a3/

Developing for Developers Factoring large numbers with quadratic sieve | Outdoor Ceiling Fans

Sun, 31 May 2009 10:09:57 GMT

PingBack from http://outdoorceilingfansite.info/story.php?id=1072

Developing for Developers Factoring large numbers with quadratic sieve | patio set

Thu, 18 Jun 2009 05:07:37 GMT

PingBack from http://patiosetsite.info/story.php?id=674

Developing for Developers Factoring large numbers with quadratic sieve | storage bench

Fri, 19 Jun 2009 10:45:19 GMT

PingBack from http://thestoragebench.info/story.php?id=5411

re: Factoring large numbers with quadratic sieve

Lieven van der Heide — Sun, 16 Aug 2009 02:43:05 GMT

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.

re: Factoring large numbers with quadratic sieve

Lieven van der Heide — Sun, 16 Aug 2009 17:34:14 GMT

Actually, ignore the last sentence in my previous post, as I was confused with something else:)