【摘要】 研究弱可逆有限自动机的分解可以为分析有限自动机公开钥密码体制的安全性提供一种重要途径.从输出权的角度研究了n元延迟τ步弱可逆有限自动机M的分解问题,首先证明了其可分解为一个延迟0步弱可逆有限自动机和一个τ阶延迟元当且仅当M的所有状态的长τ输出权为1.其次,在获得一类不可分解出延迟元的弱可逆有限自动机的基础上,构造出一个反例,否定回答了鲍丰在1993年提出的一个公开问题.同时给出了二元严格延迟τ步强连通弱可逆有限自动机可分解为一个严格延迟τ-1步弱可逆有限自动机和一个严格延迟1步弱可逆有限自动机的一个充分条件.更多还原

【Abstract】 It is very important to investigate the decompositon of weakly invertible finite automata, since it could provide an approach to cryptanalyzing finite automaton public-key cryptosystem (FAPKC), which was proposed by Tao Renji and Chen Shihua in 1985. This paper deals with this topic. For an n-ary weakly invertible finite automaton (WIFA, for short) M with delay τ, a necessary and sufficient condition is obtained, that M can be decomposed into a WIFA with delay 0 and a so-called τ-order delay unit, i.e., the τ-output weight of s is 1 for any state s in M. Meanwhile, based on a class of weakly invertible finite automata that cannot be decomposed into a delay unit, an example is hereby constructed. Thus, a negative answer to an open question presented by Bao Feng in 1993 is given.更多还原