Technical Report: DCC-2011-11

On Linear Finite Automata and Cryptography

Ivone Amorim, António Machiavelo, Rogério Reis

CMUP & FC, Universidade do Porto
e-mail: ivonefamorim@gmail.com, ajmachia@fc.up.pt, rvr@dcc.fc.up.pt

August 2011

Abstract

Finite automata public-key cryptosystems rely upon characterizations of some types of invertible finite automata, and methods of obtain them as well as their respective inverses. In this paper we provide a much needed clarification of Tao?s formalization and basic results on the subject, as well as a new condition for a linear finite automata with memory to be weakly invertible with delay ?. This last result, employing an approach with formal series, uses the Smith?s normal form of a polynomial matrix. The proof of the results presented here provides a new way to construct an inverse with delay ? of an invertible linear finite automata.