View Single Post
Old 2004-03-04, 09:29   #18
xilman's Avatar
May 2003
Down not across

22·3·877 Posts

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 1072. so the only way to make the modular value zero would be to make the polynomial value zero, which would mean that (x-r) is a factor of the polynomial. Since it's trivial to create such polynomials as (x-r) 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 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.

xilman is online now