On minimal polynomials over \(\mathbb F_{q^m}\) and over \(\mathbb F_q\) of a finite-length sequence over \(\mathbb F_{q^m}\) (Q539903): Difference between revisions

Let \(B = \{1,\zeta,\dots,\zeta^{m-1}\}\) be a polynomial basis of \(\mathbb F_{q^m}\) over \(\mathbb F_q\), and \(\rho = p_0+p_1\zeta+\cdots+p_{m-1}\zeta^{m-1}\), \(\xi = r_0+r_1\zeta+\cdots+r_{m-1}\zeta^{m-1}\) be two elements of \(\mathbb F_{q^m}\). Then \[ \rho\xi = \sum_{i=0}^{m-1}\;\sum_{\substack{ j+l\equiv i \bmod m\\ 0\leq j,\;l\leq m-1}} p_jr_l\zeta^i, \] defining an \(m\times m\) matrix \(A_\rho\) over \(\mathbb F_q\) corresponding to \(\rho \in \mathbb F_{q^m}\) for which \((\rho\xi)_B = A_\rho(\xi)_B\), where \((\gamma)_B \in \mathbb F_q^m\) is the coordinate vector of \(\gamma\in\mathbb F_{q^m}\) relative to the basis \(B\) (the appearance of the matrix changes if a different isomorphism between \(\mathbb F_{q^m}\) and \(\mathbb F_q^m\) is considered). A finite sequence \(S=(s_1,s_2,\dots,s_N)\) over \(\mathbb F_{q^m}\) can by this be transformed into a finite sequence of \(m\times m\) matrices over \(\mathbb F_q\). The author shows how to obtain a minimal polynomial over \(\mathbb F_{q^m}\) for \(S\) from a minimal polynomial column vector for the corresponding matrix sequence, which can be obtained by the lattice basis reduction method, analysed in several earlier papers by the author (see [\textit{L.-P. Wang, Y. Zhu} and \textit{D. Pei}, IEEE Trans. Inf. Theory 50, No.~11, 2905--2910 (2004; Zbl 1178.94181); \textit{L.-P. Wang}, Cryptogr. Commun. 3, No.~1, 29--42 (2011)]). On this basis she presents two algorithms for calculating a minimal polynomial for a finite sequence. Finally it is shown how to obtain also a minimal polynomial over \(\mathbb F_q\) for \(S\), and a relationship between minimal polynomials over \(\mathbb F_{q^m}\) and over \(\mathbb F_q\) is deduced.