New results on quasi-subfield polynomials (Q1979951)

Quasi-subfield polynomials have been introduced recently in the context of the discrete logarithm problem for elliptic curves over an extension field~\(\mathbb F_{q^n}\). They generalize subfield polynomials \(X^{q^m} \!-\! X\), whose roots form the subfield~\(\mathbb F_{q^m}\) if \(m \mid n\), to polynomials of the form \(X^{q^m} \!-\! \lambda\) with~\(\lambda\) a polynomial of low degree, such that it splits (almost) completely over~\(\mathbb F_{q^n}\) even if \(m \nmid n\). The zero set of such a polynomial has been proposed for an index calculus factor base, as an alternative to a subfield or a vector space as in previous algorithms. The paper at hand investigates properties and constructions of quasi-subfield polynomials further. For~\(p\) a prime, it is shown that for any polynomial \(X^{p^m} \!-\! \lambda\) that completely splits over~\(\mathbb F_{p^n}\) and has a linearized polynomial~\(\lambda\), there holds \(\beta \mathrel {\mathop :} = \frac {\ell n} {m^2} \ge \frac 3 4\) where \(\ell \mathrel {\mathop :} = \log_p \deg \lambda\), a bound that is matched e.g.\ by \(X\smash{^{p^2}} \!+\! X^p \!+\! X\) over~\(\mathbb F_{p^3}\). The proof proceeds by examining (conjugated) powers of certain companion matrices. Furthermore, new families of quasi-subfield polynomials are constructed whose roots form either an additive or a multiplicative subgroup. Finally, the impact of quasi-subfield polynomials with parameter~\(\beta\) on the elliptic curve discrete logarithm problem is discussed. The analysis suggests that, unless algorithmic improvements for solving sparse polynomial systems occur, the proposed approach beats generic algorithms only if \(\beta < 0.103\), which is out of reach by current construction methods.