Irreducible polynomials and linear recurring arrays (Q678874)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Irreducible polynomials and linear recurring arrays |
scientific article |
Statements
Irreducible polynomials and linear recurring arrays (English)
0 references
12 June 1997
0 references
Let \(F_{q}\) be the finite field of order \(q\) and \(F_{q}(\alpha,\beta)\) be a finite extension of \(F_{q}\). An explicit formula for obtaining a generator \(\gamma\) such that \(F_{q}(\alpha,\beta)=F_{q}(\gamma)\) and an explicit formula for the minimal polynomial \(h_{\gamma}(x)\) of \(\gamma\) over \(F_{q}\) are given under the assumption that gcd\ (Ord\((\alpha)\), Ord\((\beta))=1\). Suppose \(f_{\alpha}(x)\) of degree \(m\) is the minimal polynomial of \(\alpha\) over \(F_{q}\) and \(g_{\beta}(x)= x^{n}+\sum d_{ij}\alpha^{i}x^{j} (d_{ij}\in F_{q}, i\) running from 0 to \(m-1,j\) running from 0 to \(n-1)\) is the minimal polynomial of \(\beta\) over \(F_{q}(\alpha)\). Let Ord\((\alpha)=r\), Ord\((\beta)=s\) and \(\bar f_{\alpha}(x)=f_{\alpha} (x^{s})\), \(\bar g_{\beta}(x)=x^{rn}+\sum d_{ij}x^{is+jr}\). If gcd\((r,s)=1\), then it is proved that \(h_{\gamma}(x)= \text{gcd}(\bar f_{\alpha}(x),\bar g_{\beta} (x))\). An application of this result to linear recurring arrays is also given.
0 references
irreducible polynomial
0 references
primitive polynomial
0 references
discrete logarithm problem
0 references
linear recurring arrays
0 references