Construction of polinomials irreducible over a~finite field with linearly independent roots

I. A. Semaev

Sbornik. Mathematics, Tome 63 (1989) no. 2, pp. 507-519

Résumé

For any $t\geqslant1$ the author gives a method of constructing a matrix $X$ – the multiplication table for a certain normal basis of the finite field $F_{q^t}$ over $F_q$, where $q$ is a power of a prime $p$. The characteristic polynomial of $X$ is an irreducible polynomial of degree $t$ with coefficients in $F_q$, whose roots are linearly independent over $F_q$. In order to construct the matrix $X$, and thus an irreducible polynomial with linearly independent roots, one needs to perform no more than $O(\max(t^4,r^7\ln t/\ln r))$ additions and multiplications in $F_q$ (where $r$ is the greatest prime divisor of $t$). Bibliography: 3 titles.