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.

[QUOTE=Christenson;259437]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. [/QUOTE]Assuming they don't change their deep-link structure, his article is available [URL="http://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866119-8/"]here[/URL] free of charge from AMS....

[QUOTE=jasonp;259440]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.[/QUOTE]
Thanks to both of you for the link. I'm still confused, but I can't ask intelligent questions at the moment without significantly raising my crank score.

[QUOTE=Christenson;259437]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?[/QUOTE]

Read the paper. If you want q(x)^2 = A mod (kN) with A small for
k = 1,2,3, ..... note that every time k changes, you will need a NEW FACTOR
BASE. Computing them is expensive. Also, the final factor base will be
very large since it will be the union of the factor bases for each k.

And your proposal is not going to reduce the size of A (on average). So
there is no point.

[QUOTE=jasonp;259440]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.[/QUOTE]

Not [i]quite[/i]. For a given polynomial, q(x), as we sieve q(r + p_i x)
for x = ....-2, -1, 0, 1, ..... M, the norms that we want to be smooth
increase with increasing x. Thus, the probability of success at q(r + p_i M)
is lower than near the origin.

The [i]average[/i] probability of success per polynomial is the same
across all polynomials.

[QUOTE=R.D. Silverman;259600]Not [i]quite[/i]. For a given polynomial, q(x), as we sieve q(r + p_i x)
for x = ....-2, -1, 0, 1, ..... M, the norms that we want to be smooth
increase with increasing x. Thus, the probability of success at q(r + p_i M)
is lower than near the origin.

The [i]average[/i] probability of success per polynomial is the same
across all polynomials.[/QUOTE]

Can you give me a brief idea of the "norms" and how "smoothness" is defined on a discrete space such as the integers or integers modulo N?

[QUOTE=Christenson;259610]Can you give me a brief idea of the "norms" and how "smoothness" is defined on a discrete space such as the integers or integers modulo N?[/QUOTE]

The norm of an algebraic number is simply the product of [b]all[/b] of its
conjugates. For an element of Q (or Z), there are no conjugates, so
its norm is just itself. norm(q(x)) is just its value.

If you don't know what smoothness is, you are going to have some
difficulty. The concept is prevalent throughout all of computational
number theory. An integer N is smooth up to M if all of its prime
factors are less than M. If u = log(N)/log(M), then the probability that
a random integer near N is M-smooth is approximately u^-u. (by a theorem
of Canfield, Erdos & Pomerance). It can be estimated more accurately
through the use of Dickman's function. Knuth Vol II has an excellent
exposition on this.



Read the Crandall & Pomerance book. Take a course in number theory.
Understanding NFS will require knowledge of algebraic number theory.
Larry Washington's book is excellent for this.

[QUOTE=R.D. Silverman;259612]An integer N is smooth up to M if all of its prime
factors are less than M. If u = log(N)/log(M), then the probability that
a random integer near N is M-smooth is approximately u^-u. (by a theorem
of Canfield, Erdos & Pomerance).[/QUOTE]

That's surely older than the Erdos & Pomerance paper... isn't that approximation in Dickman's original paper?

[QUOTE=CRGreathouse;259614]That's surely older than the Erdos & Pomerance paper... isn't that approximation in Dickman's original paper?[/QUOTE]

I don't know. I would need to check. However, it is indeed a
theorem by Canfield, Erdos, and Pomerance, from the paper
"On a problem of Oppenheim concerning "Factorisatio Numerorum"

from 1983.

[QUOTE=R.D. Silverman;259600]Not [i]quite[/i]. For a given polynomial, q(x), as we sieve q(r + p_i x)
for x = ....-2, -1, 0, 1, ..... M, the norms that we want to be smooth
increase with increasing x.
<snip>

.[/QUOTE]

Mea Culpa. The above should be "with increasing |x|".

[QUOTE=R.D. Silverman;259612]The norm of an algebraic number is simply the product of [b]all[/b] of its
conjugates. For an element of Q (or Z), there are no conjugates, so
its norm is just itself. norm(q(x)) is just its value.

If you don't know what smoothness is, you are going to have some
difficulty. The concept is prevalent throughout all of computational
number theory. An integer N is smooth up to M if all of its prime
factors are less than M. If u = log(N)/log(M), then the probability that
a random integer near N is M-smooth is approximately u^-u. (by a theorem
of Canfield, Erdos & Pomerance). It can be estimated more accurately
through the use of Dickman's function. Knuth Vol II has an excellent
exposition on this.

Read the Crandall & Pomerance book. Take a course in number theory.
Understanding NFS will require knowledge of algebraic number theory.
Larry Washington's book is excellent for this.[/QUOTE]

The definition of smoothness makes sense...just having trouble figuring out how that property got to be called smooth....

As for the course in number theory, I'm getting it by correspondence here, from you, and I thank you for your tolerance...I'm still trying to understand the MP part of MPQS, certain distractions (counting chess positions, linux GPU drivers) keep getting in the way, not to mention my day job, which pays for it all.

[QUOTE=Christenson;260198]The definition of smoothness makes sense...just having trouble figuring out how that property got to be called smooth....

.[/QUOTE]

smooth = fine-grained = many factors

It's just a name. Why worry over a name??

[QUOTE=R.D. Silverman;259599]Read the paper. If you want q(x)^2 = A mod (kN) with A small for
k = 1,2,3, ..... note that every time k changes, you will need a NEW FACTOR
BASE. Computing them is expensive. Also, the final factor base will be
very large since it will be the union of the factor bases for each k.
[/QUOTE]
Not very large but about twice as big, because the factor base includes about half the primes below the bound, so you will have different factor bases but their union will not exceed twice the size of a particular factor base. Anyway I do not think this method can be useful at all.

[QUOTE=alpertron;260263]Not very large but about twice as big, because the factor base includes about half the primes below the bound, so you will have different factor bases but their union will not exceed twice the size of a particular factor base. Anyway I do not think this method can be useful at all.[/QUOTE]

Agreed.