Quasi-subfield polynomials and the elliptic curve discrete logarithm problem (Q2191201)

Let \(q\) be a prime and \(K = \mathbb F_q^n\) be a finite field with \(q^n\) elements. In this paper a new class of polynomials of \(K[X]\) is introduced, called {\em quasi-subfield polynomials.} They have the form \(X^{q^{n^{\prime}}}-\lambda(X)\) with \(\log_q(\deg \lambda) < n^{\prime}/2\) and divide \( X^{q^n} -X \). These polynomials are used for the construction of a polynomial system over the field \(K\) such that its zero set gives a relation for the index calculus method. By applying Rojas's algorithm to solve this polynomial system, precise complexity results for the index calculus algorithm are given. When \(\deg \lambda\) is small enough, it is shown that such polynomials could lead to faster algorithms for the elliptic curve discrete logarithm problem (ECDLP). The existence of these polynomials is investigated and a particular family is provided leading to an ECDLP algorithm more efficient than exhaustive search.