SEVERAL SPECIFIC FACTORIZATIONS OF MATRIX POLYNOMIALS
Tao Ren · Chinese Journal of Computers · 1999
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.