RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Mat. Sb.: Year: Volume: Issue: Page: Find

 Mat. Sb. (N.S.), 1988, Volume 135(177), Number 4, Pages 520–532 (Mi msb1722)

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.

Full text: PDF file (674 kB)
References: PDF file   HTML file

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

Bibliographic databases:

UDC: 512
MSC: Primary 12E20, 11T30; Secondary 11T06
Received: 14.12.1985 and 03.09.1987

Citation: I. A. Semaev, “Construction of polinomials irreducible over a finite field with linearly independent roots”, Mat. Sb. (N.S.), 135(177):4 (1988), 520–532; Math. USSR-Sb., 63:2 (1989), 507–519

Citation in format AMSBIB
\Bibitem{Sem88} \by I.~A.~Semaev \paper Construction of polinomials irreducible over a~finite field with linearly independent roots \jour Mat. Sb. (N.S.) \yr 1988 \vol 135(177) \issue 4 \pages 520--532 \mathnet{http://mi.mathnet.ru/msb1722} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=942137} \zmath{https://zbmath.org/?q=an:0665.12017} \transl \jour Math. USSR-Sb. \yr 1989 \vol 63 \issue 2 \pages 507--519 \crossref{https://doi.org/10.1070/SM1989v063n02ABEH003288} 

• http://mi.mathnet.ru/eng/msb1722
• http://mi.mathnet.ru/eng/msb/v177/i4/p520

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. I. E. Shparlinski, “On primitive elements in finite fields and on elliptic curves”, Math. USSR-Sb., 71:1 (1992), 41–50
2. Joachim von zur Gathen, Mark Giesbrecht, “Constructing normal bases in finite fields”, Journal of Symbolic Computation, 10:6 (1990), 547
3. I. E. Shparlinski, “On some problems in the theory of finite fields”, Russian Math. Surveys, 46:1 (1991), 199–240
4. Shoup V., “Searching for Primitive Roots in Finite-Fields”, Math. Comput., 58:197 (1992), 369–380
5. Shparlinski I., “Finding Irreducible and Primitive Polynomials”, Appl. Algebr. Eng. Commun. Comput., 4:4 (1993), 263–268
6. Schlickewei H., Stepanov S., “Algorithms to Construct Normal Bases of Cyclic Number-Fields”, J. Number Theory, 44:1 (1993), 30–40
7. Ian F Blake, Shuhong Gao, Ronald C Mullin, “Specific irreducible polynomials with linearly independent roots over finite fields”, Linear Algebra and its Applications, 253:1-3 (1997), 227
8. A. A. Bolotov, S. B. Gashkov, “On fast multiplication in normal bases of finite fields”, Discrete Math. Appl., 11:4 (2001), 327–356
9. Melsik K Kyuregyan, “Iterated constructions of irreducible polynomials over finite fields with linearly independent roots”, Finite Fields and Their Applications, 10:3 (2004), 323
10. Melsik K. Kyuregyan, “Recursive constructions of -polynomials over”, Discrete Applied Mathematics, 156:9 (2008), 1554
11. ERIK JARL PICKETT, “CONSTRUCTION OF SELF-DUAL INTEGRAL NORMAL BASES IN ABELIAN EXTENSIONS OF FINITE AND LOCAL FIELDS”, Int. J. Number Theory, 06:07 (2010), 1565
12. Aixian Zhang, Keqin Feng, “A new criterion on normal bases of finite field extensions”, Finite Fields and Their Applications, 31 (2015), 25
•  Number of views: This page: 1440 Full text: 396 References: 45 First page: 1