With good probability, the algorithm will stumble on a which apparently isn't smooth over the factor base, but when taken as a negative number in turns out to be smooth, so you need to add to your factor base to benefit from this.
I have to understand the idea of the index calculus algorithm. The algorithm can be found here.
We have to find the discrete logarithm of an element of a multiplicative group of intergers modulo n (say n=5), let's say to base 2 (2 is a generator of ).
We need a factor base in the input. The factor base is a tuple , where is the r-th prime. My question is why do we want -1 in the factor base?
With good probability, the algorithm will stumble on a which apparently isn't smooth over the factor base, but when taken as a negative number in turns out to be smooth, so you need to add to your factor base to benefit from this.