This article is cited in 19 papers

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

I. A. Semaev


Abstract: 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.

UDC: 512

MSC: Primary 12E20, 11T30; Secondary 11T06

Received: 14.12.1985 and 03.09.1987

 English version: Mathematics of the USSR-Sbornik, 1989, 63:2, 507–519

Bibliographic databases:

• 
•