Quote:
Originally Posted by wblipp
A bit more musing shows me the root can probably be large. It not, then the highest possible value for the polynomial is about 10^{72}. so the only way to make the modular value zero would be to make the polynomial value zero, which would mean that (xr) is a factor of the polynomial. Since it's trivial to create such polynomials as (xr) times anything, it's unlikely such polynomials are of any use.

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 201digit 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 201digit number.
Paul