View Single Post
Old 2004-03-09, 16:24   #19
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Thumbs up

Quote:
Originally Posted by xilman
The root can be any size you like. What's important is the size of the coefficients of the polynomials.

Actually, that's an oversimplification, but it's a good first cut. If you want more details, dig out Brian Murphy's thesis.

An example may help. NFSNET is currently sieving the 201-digit composite cofactor of 10^223+1. We are using the polynomials x^6+10 and 1 - (10^37)*x which share a root 10^(-37) modulo 10^223+1. The latter value is a 201-digit number.


Paul
Actually Paul, the size of the root does matter. Let's use your example
and look at a 'typical' lattice point. (say (3x10^6, 3x10^6)) (choose
another if you like)

We have two polynomials. The corresponding norms at lattice point (b,a)
are a + 10^37 b and a^6 + 10b^6. For our typical point, the norms are
about 3x10^43 and 7x10^39. Note that the linear norm is larger. The
product is about 2x10^82

If we were to use a quintic, the linear norm becomes about 3 x 10^51
while the algebraic norm shrinks to 2 x 10^33. The product is now about
6 x 10^84, i.e. larger.

A septic would yield norms of about 3x10^38 and 2 x 10^46.

Having equal norms would be optimal.

The size of the root affects the norm of the linear polynomial. There is a
ying-yang effect. Reducing one norm increases the other and vice versa.
We want the product to be as small as possible averaged over the sieve
region.

See my recent paper for a more detailed analysis.
R.D. Silverman is offline