On linear finite automata and cryptography

• Tipo: Relatório Técnico
• Data: 2011

Autores

Ivone Amorim (Autor) FCUP; António Machiavelo (Autor) FCUP; Rogério Reis (Autor) FCUP

Classificação Científica

FOS: Ciências exactas e naturais > Matemática

Outras Informações

Abstract (EN): 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 t. 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 t of an invertible linear finite automata.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Referência: Technical Report DCC-2011-11