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.