高级检索
    王鸿吉. 分解弱可逆有限自动机的两个结果[J]. 计算机研究与发展, 2005, 42(4): 690-696.
    引用本文: 王鸿吉. 分解弱可逆有限自动机的两个结果[J]. 计算机研究与发展, 2005, 42(4): 690-696.
    Wang Hongji. Two Results of Decomposing Weakly Invertible Finite Automata[J]. Journal of Computer Research and Development, 2005, 42(4): 690-696.
    Citation: Wang Hongji. Two Results of Decomposing Weakly Invertible Finite Automata[J]. Journal of Computer Research and Development, 2005, 42(4): 690-696.

    分解弱可逆有限自动机的两个结果

    Two Results of Decomposing Weakly Invertible Finite Automata

    • 摘要: 研究弱可逆有限自动机的分解可以为分析有限自动机公开钥密码体制的安全性提供一种重要途径.从输出权的角度研究了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 Shihu a in 1985. This paper deals with this topic. For an n-ary weakly invertible fini te automaton (WIFA, for short) M with delay τ, a necessary and sufficient cond ition is obtained, that M can be decomposed into a WIFA with delay 0 and a so-ca lled τ-order delay unit, i.e., the τ-output weight of s is 1 for any state s i n M. Meanwhile, based on a class of weakly invertible finite automata that canno t be decomposed into a delay unit, an example is hereby constructed. Thus, a neg ative answer to an open question presented by Bao Feng in 1993 is given.

       

    /

    返回文章
    返回