Weak invertibility of linear finite automata over rings -- Classification and enumeration

摘要

The weak invertibility problem of finite automata (FAs) has received continuous considerations. The weak invertibility theory has applications in cryptography, both conventional cryptosystems and public key cryptosystems. Given a finite commutative ring R with identity, it is known that the weak invertibility of a linear finite automaton (LFA) over R depends only on its transfer function matrix. Let H be the set of all possible transfer function matrices which weakly invertible LFAs over R can have.Our main goal of this work is to give a clear description of the structure of H. Firstly we note that the set H is nothing else than the set of all possible regular matrices with entries in a proper localization R[z]_s of the polynomial ring R[z], hencewe converte the problem on LFAs to a pure algebraic one (Theorem 3). Secondly, we reduce the problem further to the same one when R is a finite field by making a decomposition and a reduction on H (Theorems 4 and 5), Then we introduce a trasformation group G acting on H to classify H (Theorem 6). Next, based on the classification and a further reduction the problem of enumerating the infinite set H is reduced to that of enumerating elements in each reduced equivalence class which is finite (Theorems 7-9). Finally, we succeed to give a standard factorization of every element in each reduced ckss, and thus realize a parametrized enumeration of H (Theorem 10).