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

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.