
On the Number of NonEquivalent Linear Transducers
Ivone Amorim, António Machiavelo, Rogério Reis
DCC & FCUP, Centro de Matemática da Universidade do Porto
R. Campo Alegre 687, 4169007 Porto, Portugal
email: ivone.amorim@dcc.fc.up.pt,ajmachia@fc.up.pt,rvr@dcc.fc.up.pt
March 2014
Abstract
The notion of Linear finite transducer (LFT) play a crucial role in a
family of cryptosystems introduced in the 80?s and 90?s. However, as
far as we know, no study was conducted towards the counting and
enumeration of these transducers, which is essential to verify if the
size of the key space, of the aforementioned systems, is large enough
to prevent a exhaustive search attack. In this paper, we determine
the cardinal of the equivalence classes on the set of the LFTs with a
given size. This result is sufficient to get an approximate value, by
random sampling, for the number of nonequivalent injective LFTs, and
subsequently for the size of the key space. We introduce a notion of
canonical LFT, give begin by giving a method to verify if two LFTs
are equivalent, and prove that every LFT has exactly one equivalent
canonical transducer. We then show how this canonical LFT allows us
to calculate the size of each equivalence class on the set of the
LFTs with the same number of states, and deduce a recurrence relation
to count the number of equivalence classes.
