PRIMITIVE MATRICES AND GENERATORS OF PSEUDO RANDOM SEQUENCES OF GALOIS

Abstract

In theory and practice of information cryptographic protection one of the key problems is the forming a binary pseudo-random sequences (PRS) with a maximum length with acceptable statistical characteristics. PRS generators are usually implemented by linear shift register (LSR) of maximum period with linear feedback [1]. In this paper we extend the concept of LSR, assuming that each of its rank (memory cell) can be in one of the following condition. Let’s call such registers “generalized linear shift register.” The research goal is to develop algorithms for constructing Galois and Fibonacci generalized matrix of n-order over the field , which uniquely determined both the structure of corresponding generalized of n-order LSR maximal period, and formed on their basis Galois PRS generators of maximum length. Thus the article presents the questions of formation the primitive generalized Fibonacci and Galois arbitrary order matrix over the prime field . The synthesis of matrices is based on the use of irreducible polynomials of degree and primitive elements of the extended field generated by polynomial. The constructing methods of Galois and Fibonacci conjugated primitive matrices are suggested. The using possibilities of such matrices in solving the problem of constructing generalized generators of Galois pseudo-random sequences are discussed.

Keywords

• Galois fields
• Galois sequences generators
• irreducible polynomials
• linear shift registers
• primitive matrices