QS questions
 

OK, guys:
The montomery paper says that quadratic sieving gives a bunch of congruences as its output, with Qi^2 === Product(Pj^ej).

How are the Qi's chosen, and how does the sieve find the products? Can we do a very small example, one that *could* be done completely without a computer?

[The next step is to find the null space of the matrix formed by all of the relations. ]

[QUOTE=Christenson;256506]OK, guys:
The montomery paper says that quadratic sieving gives a bunch of congruences as its output, with Qi^2 === Product(Pj^ej).

How are the Qi's chosen, and how does the sieve find the products? Can we do a very small example, one that *could* be done completely without a computer?

[The next step is to find the null space of the matrix formed by all of the relations. ][/QUOTE]

Read my paper: The Multiple Polynomial Quadratic Sieve, Math. Comp. 1987

It explains everything you might need to know.

Wikipedia also has a decent quadratic sieve page.

[QUOTE=jasonp;256513]Wikipedia also has a decent quadratic sieve page.[/QUOTE]
Thank you gentlemen; it is now up to me to be a scholar. I'm temporarily saturated working through the references but expect to have more questions soon.

I will not waste time on SM88
I will not waste time on SM88
I will not waste time on SM88.....

Still working on understanding the basics of the quadratic sieve.
At this point, I am interested in the fundamentals of the algorithms first. The optimizations are relatively easy in comparison.

[QUOTE=jasonp;256513]Wikipedia also has a decent quadratic sieve page.[/QUOTE]

Would an expert kindly check my statement of the quadratic sieve algorithm, with the understanding that I am omitting optimization needed for practical problems (especially the notion of "small" primes) and don't actually intend to run things as stated, I am just trying to check my "homework"?

Suppose we want to factor a large number, say 50 digits. I begin by squaring numbers near (on both sides) of its 25-digit fractional square root, square them, subtract the number to be factored, and sieve these quadratic residues for factors; some of which will factor completely in small primes, say, those including -1 but less than 10^10.

The output of sieving is a list of 25-digit square roots, quadratic residues, and a moderately-sparse list of prime factors and powers. The matrix to be reduced represents the problem of combining some of the quadratic residues into a perfect square by multiplication with the maximum power of any quadratic residue being 1; the problem is equivalent to having a matrix of the exponents modulo 2 and trying to find null vectors modulo 2.

Once we have this square product of residues, we note that modulo the number to be factored, the product of quadratic residues is the square of the product of the 25-digit square roots, and we have, as in the fermat method,
C50 = (square root by residues, product of C25s)^2 - (square root by factoring, product of P10 or smaller)^2
and
C50 = (square root by product of C25s+ square root by P10 product) *
(square root by product of C25s - square root by P10 product)

Block Lanczos in this case would be trying to find null vectors modulo 2. I'm still reading a bit on quadratic sieving, so it will be a bit before I get to SNFS and GNFS.

I think you pretty much got it. A relation (think of it as a square-root to list of factors pair) can appear as many times as you like in the complete product, as long as not all relations appear an even number of times.

You wouldn't want a relationship to appear an even number of times; if that were useful, we'd just take the first number greater than the square root and it's quadratic residue, square the both of them, factor the polynomial, and have factors, and we wouldn't need block lanczos or a bunch of sieving!

But then all relations appear an even number of times...

The first rule is that exponents of prime factors must be even. The second rule is that at least some relations must appear in the product a odd number of times. [i]Any[/i] collection of relations that satisfies both rules has a shot at splitting N. You can of course ignore any relation that appears an even number of times, and only count all the other relations once, and that will make the square root phase faster and easier, but the point is that you don't [i]have[/i] to, and in fact msieve's QS code doesn't bother to do that.

I'm still working on the MP part of MPQS. If I get dragged back to UVA often enough, I might even be able to hit the library for Mr Silverman's paper. But, in the mean time, I observe that in arithmetic modulo N, for N large, there are *many* approximate square roots of N, the smallest being the ones closest to the classical square root of N.

Is there a reason this would be an unreasonable trick to try when Quadratic Sieving, that is, some X(i)s to be squared near sqrt(N), more near sqrt(2N), sqrt(3N), etc?

Bob's paper is now available [url="http://www.ams.org/mcom/1987-48-177/S0025-5718-1987-0866119-8/S0025-5718-1987-0866119-8.pdf"]here[/url]

Your question comes up fairly often, but the basic answer is that relations are more difficult to find when they are a congruence involving increasingly large multiples of N, while conventional MPQS chooses one (small) multiple of N and the probability of finding relations is the same throughout the sieving phase.