The Ergodic Matrices On F₂ And Their Applications In Cryptography

With the development of internet and electronic commerce, secure production has became more and more important. Encryption is the most useful method that ensures the safety of electronic commerce, and is widely used in Cryptography .On exchanging a message, the sender encodes the data, then sends it to the receiver, the receiver decodes the data, then he gets the original message. Encryption includes two elements: arithmetic and key. The arithmetic is used to combine plain-text whit some numbers (key) to create cryptograph that no one will understand. The key is used to encode and decode message. The arithmetic is the kernel of Encryption. A good arithmetic will speed up the development of Encryption.We can use Encryption to the safety of internet communication. In recent years, the burst of computer hardware has a great impact on cryptograph. So we should be devoted to the researching of Encryption. In this paper, We discussed the matrix of GF(2) which is called "ergodic matrix". The "ergodic matrix" means an n*n regular matrix in GF(2). The "ergodic matrix"'s period is 2n -1. Following the matrix addition and multiplication under GF(2), (m)={m, m2, ? , m2n-1=E} constructs a finite field of order 2n(GF(2)),that is, one column (row) of {m, m2, ? , m2n-1=E} is just ergodic over from 1 to 2n -1.We can find that the "ergodic matrix" has a number of good features that can be applied to cryptography, such as randomicity and ergodicity. An n*n "ergodic matrix" only costs space(n2),yet it can express the same thing as the sequence can do which cost space(2n),thus "ergodic matrix" reduces both time and space. It will benefit Cryptography. In order to find out prime group, we introduce "ergodic matrix". Prime group must be cyclic group. So it is widely used in Cryptography. The representative prime group are the addition group which is constructed by {0,1,2,…,p-1} that mould p(p is a prime number).But these kinds of prime groups are easy to attack. So we often use multiplication group that is constructed by Z*p＝{1,2,3,…,p－1} which mould p(p is a prime number) instead. When use such kinds of groups, we should try to avoid using small prime gene. According to Galois's theory, a definite field's degree must be pn (p this a prime number, n is a integer).And for any p and n, there exists a unique definite field GF(pn) whose degree is pn under the isomorphic circumstance. And we know, there are pn-1 non-zero elements of GF(pn) which constructs cyclic group following matrix multiplication under GF(2). That means if pn-1 is prime, we can get prime groups (GF(pn)-{0}). When n>1, pn-1 is prime iff p=2. So for any prime number p＝(2n-1),we can get prime groups (GF(2n)-{0}) which degree is p if we can construct GF(2n). To construct GF(2n) is equal to find a n-degree irreducible polynomial factor under prime field F2. But there is not any good method to find n-degree irreducible polynomial factors given an integer n and a prime p. So the key point is to do some work to find n-degree irreducible polynomial factors under prime field F2. In this paper, we have done the following work:1.We bring up an arithmetic to find n-degree irreducible polynomial factors under prime field F2. When n<32, by using this arithmetic , we can find a n-degree irreducible polynomial factor rapidly. This arithmetic costs space O(n2).2.When n>32 the arithmetic above is out of service. So we define "ergodic matrix". We can use "ergodic matrix" to optimize the work of finding a n-degree irreducible polynomial factor. We introduce a recursion using cycle-segment and give a searching algorithm, by which one can generate an n*n "ergodic matrix" only by a n-bit binary number g. So we can use a n-bit number to express a n2-bit "ergodic matrix". Thereby saving the storage and bandwidth.3.we give some theories about "ergodic matrix", such as ergodicity, the determinant of "ergodic matrix", the number of "ergodic matrix" and so on, we also give particular proofs about the theory above.4.We discuss how...