矩阵多项式的几种特殊分解

SEVERAL SPECIFIC FACTORIZATIONS OF MATRIX POLYNOMIALS

在对有限自动机公开钥密码（ＦＡＰＫＣ）的分析中也提出了矩阵多项式的分解问题，本文研究几种特殊分解，即线性ＲａＲｂ变换导出的分解、化标准对角形导出的两种分解、线性本原分解和左本原分解．文中讨论了这些分解的关系，讨论了积Ｂ（λ）Ａ（λ）与Ａ（λ）的分解间的关系．最后，论述了这些结果在ＦＡＰＫＣ分析上的应用和意义．

Factorization of matrix polynomials over finite fields was encountered in analyzing the finite automaton public key cryptosystems (FAPKCs).In general,ones regard the factorizing problem for matrix polynomials over finite fields as an intractable problem.This paper deals with several specific factorizations of matrix polynomials over fields,namely,a derived factorization by R a R b transformations,two derived factorizations by the canonical diagonal form of the matrix polynomial (one was proposed by YE Ding Feng in 1995 and the other by TAO Ren Ji in 1997), the linear primitive factorization by QIN Zhong Ping et al. in 1998, and the left primitive factorization introduced in this paper. Two factorizations A(λ)=G(λ)H(λ) and A(λ)=G′(λ)H′(λ) of a matrix polynomial A(λ) are equivalent, if there is an invertible matrix polynomial R(λ) such that G′(λ)=G(λ)R(λ) -1 and H′(λ)=R(λ)H(λ) . This paper first generalizes a result of Ye Dingfeng on relation between the derived factorizations of type 1 by the canonical diagonal form of matrix polynomials B(λ)A(λ) and A(λ) , then another proof of uniqueness of the linear primitive factorization under equivalence by QIN Zhong Ping et al. in 1998 was given.Then proves that the derived factorizations by terminate R a R b transformations of a matrix polynomial A(λ), the left primitive factorizations of A(λ) and the derived factorizations of type 2 by the canonical diagonal form of A(λ) are unique under equivalence; relations between the three factorizations of matrix polynomials B(λ)A(λ) and A(λ) were also given. In final, the above results were used to the cryptanalysis of FAPKC. The author pointes out that keys for FAPKC3 which passed a R a R b test in key generator are secure against any attacks by above five factorizations of a matrix polynomial and reducing to delay step zero. Additionally, for the attacks by the derived factorizations by the canonical diagonal form of the matrix polynomial, there is no threat even if the component M 0 of the user key C′(M 1,M 0) for FAPKC3 is linear; some reasons were also mentioned.