有限自动机定义函数的线性本原圈积分解

本文讨论有限自动机显表出定义函数ｆ的线性本原圈积分解问题。在该圈积分解之下，函数ｆ被表成线性外函数因子ｆＬ与线性本原内涵数因子ｆＮ的圈积，这里函数ｆＬ定义了一个线性弱可逆有限自动机ＭｆＬ，而函数ｆＮ定义了一个非线性有限自动机ＭｆＮ且其不能再分解成一非平凡的线性外函数与一非线性内函数的圈积。本文证明了一函数ｆ的任两线性本原内因子互为对方的线性本原内因子，从而证明了函数ｆ的线性本原圈积分解的唯一性。本

LINEAR PRIMITIVE FACTORIZATION TO THE LOOP PRODUCT OF THE AUTOMATON-DIFINING FUNCTION

This paper discusses the linear primitive factorization to a loop product of the automaton defining function f . Under this factorization function f is factorized as the loop product of a linear out function divisor f L and a linear primitive inner function divisor f N , where f L defines a linear weakly invertible finite automaton M f L and f N defines a nonlinear finite automaton M f N and f N can not be factorized as a loop product of a nontrivial linear out function and a nonlinear inner function. The paper proves that any two linear primitive inner function divisors of function f are a linear primitive inner function divisor of each other. So the factorization to a loop product given by the paper has uniqueness. Also this paper proves the linear primitive factorization to loop product of function f can more reduce the complexity for finding a weak inverse of M f which is defined by function f than the factorization to a loop product relative to (t 0, T) (DAI et al , Communications Security, No.2,1996, 45 51). This can be effectively applied to the cryptanalysis on the finite automaton key cryptosystems.