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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers