[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??