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

摘要

本文讨论有限自动机显表出定义函数f的线性本原圈积分解问题.在该圈积分解之下,函数f被表成线性外函数因子fL与线性本原内函数因子fN的圈积,这里函数fL定义了一个线性弱可逆有限自动机MfL,而函数fN定义了一个非线性有限自动机MfN且其不能再分解成一非平凡的线性外函数与一非线性内函数的圈积.本文证明了一函数f的任两线性本原内因子互为对方的线性本原内因子,从而证明了函数f的线性本原圈积分解的唯一性.本文所给出的函数f的线性本原圈积分解比此前已有的f的相对(t0,T)圈积分解能进一步降低求f定义的有限自动机Mf的弱逆M*f的复杂性,其可应用于有限自动机公钥密码体制的密码分析中.