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
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Wilfried Meidl / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 94A55 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 94A60 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 93B15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 93B20 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 15A54 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5902694 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Berlekamp-Massey algorithm | |||
Property / zbMATH Keywords: Berlekamp-Massey algorithm / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
multisequences | |||
Property / zbMATH Keywords: multisequences / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
matrix sequences | |||
Property / zbMATH Keywords: matrix sequences / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
minimal partial realization | |||
Property / zbMATH Keywords: minimal partial realization / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
lattices | |||
Property / zbMATH Keywords: lattices / rank | |||
Normal rank |
Revision as of 10:57, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On minimal polynomials over \(\mathbb F_{q^m}\) and over \(\mathbb F_q\) of a finite-length sequence over \(\mathbb F_{q^m}\) |
scientific article |
Statements
On minimal polynomials over \(\mathbb F_{q^m}\) and over \(\mathbb F_q\) of a finite-length sequence over \(\mathbb F_{q^m}\) (English)
0 references
31 May 2011
0 references
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.
0 references
Berlekamp-Massey algorithm
0 references
multisequences
0 references
matrix sequences
0 references
minimal partial realization
0 references
lattices
0 references