# Thread: Index calculus algorithm, -1 in factorization

1. ## Index calculus algorithm, -1 in factorization

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 $\mathbb{Z}_5^*$).

We need a factor base in the input. The factor base is a tuple $(-1,2,3,5,7,11,...,p_r)$, where $p_r$ is the r-th prime. My question is why do we want -1 in the factor base?

2. ## Re: Index calculus algorithm, -1 in factorization

With good probability, the algorithm will stumble on a $g^k$ which apparently isn't smooth over the factor base, but when taken as a negative number in $\mathbb{Z} / n \mathbb{Z}$ turns out to be smooth, so you need to add $-1$ to your factor base to benefit from this.