View Single Post
Old 2010-09-29, 03:38   #3
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

746010 Posts

Originally Posted by R.D. Silverman View Post
I just found an interesting bug in my siever. I discovered it while
making some improvements, including a larger sieve region.

Here is one instance. For special_q = 256300217 with root 137499035,
my lattice reduction routine returned (36738082, 6593) (137499035, 1)

This is not correct. The problem, of course is integer overflow. The
routine uses signed ints.

Of course, since the reduced lattice is wrong, everything that follows is
wrong and no relations get produced.

I had been getting a very low relation yield rate for the larger special q's
on my current factorization. This explains it. I've been losing valid

I am going to have to change the latred routine to use 64 bit ints.
I just realized that there are other problms as well.

We hope that norm(c + d alpha) is smooth. Let v1, v2 be the reduced
lattice row vectors for some special_q. Then (c,d) = i*v1 + j*v2
where (i,j) is a point in the reduced lattice. i and j are bounded by
the size of the sieve region, but for large special_q, it is possible that
eiither i*v1 or j*v2 (or both) may overflow, giving a wrong value for
c and/or d when they are defined as signed 32-bit ints.

I will need to deal with this as well.

Does anyone know if GGNFS uses 64-bits for any/all of these variables?

For 2,2166L, I am now sieving special_q near 250 million. The average yield
is now only about 3 relations/q. A fair fraction of the q's produce no relation
at all. I may need to fix my code, and go back and RESIEVE a large
set of q's that I have already done.
R.D. Silverman is offline   Reply With Quote