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

本文讨论有限自动机显表出定义函数ｆ的线性本原圈积分解问题．在该圈积分解之下，函数ｆ被表成线性外函数因子ｆＬ与线性本原内函数因子ｆＮ的圈积，这里函数ｆＬ定义了一个线性弱可逆有限自动机ＭｆＬ，而函数ｆＮ定义了一个非线性有限自动机ＭｆＮ且其不能再分解成一非平凡的线性外函数与一非线性内函数的圈积．本文证明了一函数ｆ的任两线性本原内因子互为对方的线性本原内因子，从而证明了函数ｆ的线性本原圈积分解的唯一性．本文所给出的函数ｆ的线性本原圈积分解比此前已有的ｆ的相对（ｔ０，Ｔ）圈积分解能进一步降低求ｆ定义的有限自动机Ｍｆ的弱逆Ｍ＊ｆ的复杂性，其可应用于有限自动机公钥密码体制的密码分析中．