Analyzing the structure of a class of linear automata over a ring $$ Z_{p^k } $$
- PDF / 180,669 Bytes
- 13 Pages / 595.276 x 793.701 pts Page_size
- 2 Downloads / 194 Views
ANALYZING THE STRUCTURE OF A CLASS OF LINEAR AUTOMATA OVER A RING Z pk UDC 510.5+681.3
V. V. Skobelev
Basic finite-automaton characteristics are established for the class of all linear automata and information-lossless automata over a ring. The complexities of solving problems of parametric identification and initial-state identification are analyzed. The sets of fixed points for mappings realized by initial automata are characterized. Canonical forms are proposed for linear automata over the ring. Keywords: linear automaton, finite ring, state equivalence, parametric identification, initial state identification, fixed point, canonical form. INTRODUCTION At the present time, in solving problems of information transformation, a systematic passage is performed from purely combinatorial constructions to constructions based on finite algebraic systems. In particular, fragments of the theory of finite fields are presented practically in all modern enciphering standards [1–4]. Moreover, practically all stream encryption schemes presented in the European (NESSIE) and Japanese (CRYPTREC) projects that are realized at the present time are based on the use of automata over a field GF( 2k ) ( k = 16,32) . As is well known, a field is a special case of a ring and, at the same time, the latter contains zero divisors and, hence, the investigation of classes of automata over a finite ring is of special interest [5]. In its simplest form, such a class consists of linear automata and is a natural generalization of linear automata over a finite field [6]. Moreover, owing to the presence of zero divisors in a ring, the passage from the structure of a vector space to the module of linear forms over a finite ring [7] takes place. Apparently, for this reason, the properties of linear automata over a finite ring are not systematically investigated till now. From the viewpoint of information transformation problems, an important subclass of any class of automata are IL-automata [8–10], i.e., automata that realize a biunique transformation of an input semigroup into an output one at each fixed initial state. Therefore, the problem of investigating the structure of the class of linear automata over a finite ring and characterization of properties of linear IL-automata is topical. The main objective of this work is the investigation of properties of a class of linear automata over a ring Z p k . The basic concepts and definitions are introduced in Sec. 1. The basic finite-automaton characteristics are investigated in Sec. 2, the problems of parametric identification and initial state identification are solved in Sec. 3, fixed points are characterized in Sec. 4, and canonical forms of Mealy and Moore automata over the ring Z p k are constructed in Sec. 5. The last section contains some conclusions. 1. BASIC CONCEPTS AND DEFINITIONS We fix a ring Z p k = ( Z p k , Å , o ) ( p is a prime number and the operations Å and o are specified by the equations a Å b = a + b ( mod p k ) and a o b = a × b ( mod p k )). An element a Î Z p k is invertible
Data Loading...
