The index calculus method using non-smooth polynomials (Q2719078)

The discrete logarithm problem of interest uses the index calculus method for the finite field \({\mathbb F}_q\), \(q=p^n\) for \(p\) a prime and \(n>1\). The elements of \({\mathbb F}_q\) are represented as polynomials over \({\mathbb F}_p\) of degree smaller than \(n\), and arithmetic in the field is modulo an irreducible polynomial \(f(x)\) of degree \(n\). The case of interest here is for \(p\) small and \(n \rightarrow \infty\). A set \(S\) of irreducible polynomials over \({\mathbb F}_p\) is chosen, called the factor base. Given a generator \(g\) of the multiplicative group of \({\mathbb F}_q\), it is desired to compute the discrete logarithm of the polynomial \(h^*\) to the base \(g\). NEWLINENEWLINENEWLINEThe algorithm proceeds in two stages. In the first stage an attempt is made to find the logarithms of the polynomials in the factor base \(S\) by forming random relations between powers of \(g\) and powers of polynomials in \(S\) by seeing if \(g^s \pmod{f}\) factors over \(S\). The relations obtained are solved by matrix techniques. In the second stage one attempts to find the logarithm of \(h \equiv h^* g^s \pmod{f}\) for randomly chosen \(s\). NEWLINENEWLINENEWLINEOne usually chooses for the factor base \(S\) the set of irreducible polynomials of degree less than some bound. In this work, the effect of choosing \(S\) to be the set of irreducible polynomials of degrees between \(m_1\) and \(m_2\) is considered. It is shown that the algorithm that results with this choice has the same asymptotic running time as the original version and that the best upper limit for the interval coincides with the one for the original version. Experimental results are discussed and heuristic arguments are given for the Waterloo and Coppersmith variants of the algorithm with this new factor base.