# On the Polynomial Basis ofGF(2n) Having a Small Number of Trace-One Elements

Authors: Jiantao Wang; Dong Zheng; Zheng Huang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

In the Galois fieldsGF(2n), a polynomial basis with a small number of trace-one elements is desirable for its convenience in computing. To find new irreducible polynomials g(x) over GF(2) with this property, we research into the auxiliary polynomial f(x)=(x+1)g(x) with roots {1,α1,α2,…,αn}, such that the symmetric polynomials sk=1+α1k+α2k+⋯+αnk are relative to the symmetric polynomials of g(x). We introduce a new class of polynomials with the number “1” occupying most of the values in its sk. This indicates that the number “0” occupies most of the values of the traces of the elements {α1,α2,…,αn}. This new class of polynomial gives us an indirect way to find irreducible polynomials having a small number of trace-one elements in their polynomial bases.


---

## Body

## 1. Introduction

LetGF(2n) denote the finite field with 2n elements. Let α be a root of an irreducible polynomial g(x) of degree n over GF(2). The set {1,α,α2,…,αn-1} forms a basis of GF(2n), called a polynomial basis. An element β∈GF(2n) can be represented as (1)β=a0+a1α+a2α2+⋯+an-1αn-1.The trace of β is defined as (2)tr⁡β=β+β2+⋯+β2n-1,which is the linear combination of the traces of elements of the polynomial basis; that is, (3)tr⁡β=a0tr⁡1+a1tr⁡α+a2tr⁡α2+⋯+an-1tr⁡αn-1.If the number of basis elements αk for which tr⁡(αk)=1 is small, the computation of tr⁡(β) in software and the implementation in hardware are faster. It is benefit for halving a point on an elliptic curve over GF(2n) [1, 2] or generating pseudo random sequences using elliptic curves [3]. Thus it is of interest to find irreducible polynomials having a small number of trace-one elements in their polynomial bases. As the value of tr⁡(αk) equals the symmetric polynomial ∑t=0n-1(α2t)k, the authors in [4] got the conditions for trinomials and pentanomials to have this property using the Newton function for symmetric polynomials [5, 6].We presented an indirect strategy that is different from the above one, which is inspired by extending the work of [7] in [8]. We still use the Newton function to investigate the polynomial f(x) with the following two properties. First, the polynomial f(x) should have the factorization f(x)=(x+1)g(x) with g(x) irreducible. Second, let β0=1,β1,β2,…,βn be the roots of f(x), the number of different values of the symmetric polynomials, sk=∑t=0nβtk equaling one should be as many as possible. With these two properties, we can identify g(x) as having less trace-one elements in its polynomial basis. A class of polynomials f(x) suiting our demands is introduced, and we showed their existence by numerical experiments.The paper is organized as follows. In Section2 we give some basic definitions which are needed for our result. The new class of polynomials is introduced in Section 3. Section 4 draws the conclusion of our work.


## 2. Preliminaries

Letg(x) be a polynomial over GF(2) of degree n whose roots are α1,α2,…,αn. The elementary symmetric polynomials a1,a2,…,an are the coefficients of g(x): (4)gx=x-α1x-α2⋯x-αn=xn-a1xn-1+a2xn-2-⋯+-1n-1an-1x+-1nan.Another particular kind of symmetric polynomial is defined as(5)sk=skα1,α2,…,αn=α1k+α2k+⋯+αnk,where k is an integer.The Newton function is a relation betweensk and the coefficients of the polynomial; it is defined as follows [5, p.12]: (6)sk-sk-1a1+⋯+-1isk-iai+⋯+-1k-1s1ak-i+-1kkak=0,aj=0forj>n.It is widely known that ifg(x) is irreducible, then the traces of αk equal the value of sk.Letf(x)=(x+1)g(x); the roots of f(x) are β0=1,β1=α1,β2=α2,…,βn=αn. We have(7)skβ0,β1,β2,…,βn=β0k+β1k+β2k+⋯+βnk=1+skα1,α2,…,αn=1+tr⁡αk.So when more ones appeared in the set of the values of sk(β0,β1,…,βn), more zeros appeared in the traces of elements of the polynomial basis of g(x).


## 3. The Three Piece Polynomials

We first introduce a class of polynomialsf(x) with roots α1,α2,…,αn over GF(2) fitting the conditions that the value set of sk(α1,α2,…,αn) has plenty of ones and then search for the polynomials with the decomposition f(x)=(x+1)g(x) where g(x) is irreducible.


### 3.1. The Three Piece Polynomials

Definition 1.
Let(8)fx=a0xn+a1xn-1+a2xn-2+⋯+an-1x+anbe a polynomial over GF(2) with nonzero constant term. If (a0,a1,…,an)=(ones(n1),zeros(n2),ones(n3)) where ones(k) and zeros(k) mean k consecutive bits of ones and zeros, respectively, we call f(x) three-piece polynomial over GF(2) and denote it by its coefficients as (n1,n2,n3)TP.Lemma 2.
Letf(x)=a0xn+a1xn-1+a2xn-2+⋯+an-1x+an be a three-piece polynomial with coefficients (n1,n2,n3)TP over GF(2). Let α1,α2,…,αn be the roots of f(x); if n1≥2, then (9)skα1,α2,…,αn=1,0<k<n1.Proof.
Ifn1≥2, then a0=a1=⋯=an1-1=1, and the Newton formula tells us that s1=a1=1 and s2=s1a1+2a2=1. Suppose sk=1 is true for 1≤k≤n1-2; then ak+1=1 and (10)sk=a1sk-1+a2sk-2+⋯+ak-1s1+kak=k-1·1+k=1.We have (11)sk+1=a1sk+a2sk-1+⋯+aks1+k+1ak+1=k·1+k+1=1.We mainly divide our theorems into two parts according to the parity ofn1. First, let us consider the condition that n1 is even.Theorem 3.
Letf(x) be denoted as above. If both n1 and n2 are even, then the values of functions sk(α1,α2,…,αn), 0≤k≤n-1 all equal one.Proof.
From Lemma2, we know that sk=1 for 1≤k≤n1-1. We have (12)sn1=a1sn1-1+a2sn1-2+⋯+an1-1s1+n1an1=n1-1·1+0=1,as n1 is even and an1=0. Suppose sn1+k=1 is true for 0≤k≤n2-2; then (13)sn1+k+1=a1sn1+k+a2sn1+k-1+⋯+an1-1sk+2+an1sk+1+⋯+an1+ks1+n1+k+1an1+k+1=n1-1·1+0=1,as an1+k+1=0. Here we come to the next even number n1+n2 with an1+n2=1, (14)sn1+n2=a1sn1+n2-1+a2sn1+n2-2+⋯+an1+n2-1s1+n1+n2an1+n2=n1-1·1+0=1.Suppose sn1+n2+k=1 is true for 0≤k≤n3-2; then (15)sn1+n2+k+1=a1sn1+n2+k+a2sn1+n2+k-1+⋯+an1-1sn2+k+2+an1sn2+k+1+⋯+an1+n2+ks1+n1+n2+k+1an1+n2+k+1=n1-1·1+k+1·1+n1+n2+k+1=1,as an1+n2=an1+n2+1=⋯=an1+n2+n3-1=1.In the following proofs, we still focus on the changes of the value in the summations of the symmetric polynomialsk. To simplify narration, we will divide the summations in sk into four parts {D1,D2,D3,D4} according to the subscript of ai. That is, the summations aisk-i with 1≤i<n1 are contained in D1, the summation aisk-i with n1≤i<n1+n2 comprises D2, the summations aisk-i in D3 are with n1+n2≤i<n, and the ending part D4=kak.Theorem 4.
Letf(x) be denoted as above. If n1 is even, n2 is odd, and n1+n2>n3, then the values of functions sk(α1,α2,…,αn), 0≤k≤n-1, are (16)skα1,α2,…,αn=1,if1≤k≤n1+n2-1,0,ifk≥n1+n2,k-n1-n2≡0mod⁡n1,1,ifk≥n1+n2,k-n1-n2>0mod⁡n1.Proof.
The first case is contained in Theorem3.
For the remaining cases, we declare they are periodic. We first show one period in the following. That is, forn1+n2≤k≤n1+n2+n1 we have(17)sk=∑i≤n1-1aisk-i+∑n1=in1+n2-1aisk-i+∑i=n1+n2k-1aisk-i+kak=∑i≤n1-1sk-i+∑i=n1n1+n2-10·sk-i+∑i=n1+n2k-1sk-i+k=D1+D2+D3+D4.
By the assumptionn1+n2>n3, we get sk-i=1 for n1+n2≤i≤k-1<n1+n2+n1 and D2+D3+D4=0+k-n1-n2+k=1; these simplify the above equation to sk=D1+1.
For the value ofsn1+n2+1, as sn1+n2 appears in the D1 of sn1+n2+1 and its value is “0” we have sn1+n2+1=1.
We go on our proof by induction. Supposest=1 holds for all t satisfying n1+n2<t<k<n1+n2+n1; only the summation with sn1+n2 equals zero in D1 of sk, so sk=n1-2+1=1.
Forsn1+n2+n1, as sn1+n2 goes into the summation in D2, the value of the summation D1 turns back to n1-1 and we have sn1+n2+n1=0. Now, we finished computing the value of sk in one period in our declaration, which is n1+n2<k≤n1+n2+n1.
The conditionn1+n2>n3 guarantees the subsequent computations can still use sk=D1+1 for (17), as sk-i=1 and D2+D3+D4=0+k-n1-n2+k=1 still holds. So the above method will work for the next periods, and our declaration holds.Next we will deal with the situation thatn1 is odd, which is more complicated. It has been proved that sk=1 for k≤n1-1 in Lemma 2.Lemma 5.
Letf(x) be denoted as above. If n1 is odd, then the values of functions sk(α1,α2,…,αn), n1≤k≤n1+n2-1, are(18)skα1,α2,…,αn=0,k-n1≡0mod⁡n1,1,k-n1>0mod⁡n1.Proof.
We follow the idea in the proof of Theorem4. For n1≤k≤n1+n2-1, let(19)sk=∑i≤n1-1aisk-i+∑i=n1k-1aisk-i+kak=∑i≤n1-1sk-i+∑i=n1k-10·sk-i+k·0=D1.
We havesn1=n1-1=0 and it fixes the value of D1 in st for n1<t≤n1+n1-1 to be n1-2 which makes st=1. If n1<n2 then sn1+n1=n1-1=0 and the next period starts; otherwise the equation holds within one period.In the following, we will deal withsk with k≥n1+n2; remember that n1 is odd. We define a comparative sequence here to simplify the narration. Let bi be the coefficient of a polynomial m(x) with (20)bi=ai,1≤i<n1+n2,0,n1+n2≤i,and then sk of m(x), which is denoted by tk, follows the period shown in Lemma 5. That is,(21)tk=D1=0,k-n1≡0mod⁡n1,1,k-n1>0mod⁡n1.Theorem 6.
Letf(x) and m(x) be denoted as above. If n1 is odd, n2 is even, and n1+n2>n3, then the values of functions sk(α1,α2,…,αn), n1+n2≤k≤n1+n2+n3-1 have two cases. (22)skα1,α2,…,αn=1-tk,k-n1-n2≡0mod⁡2n1,tk,k-n1-n2>0mod⁡2n1.Proof.
Forn1+n2≤k≤n1+n2+n1, we have(23)sk=∑i≤n1-1aisk-i+∑i=n1n1+n2-1aisk-i+∑i=n1+n2k-1aisk-i+kak=D1+D2+D3+D4=D1+k-n1-n2+k=D1+1.
Forn1+n2+n1≤k<n1+n2+2n1, we have D3=k-1-n1-n2 as sn1=0 enters the summations of D3, so sk=D1. By induction, we have(24)sk=D1+1,0≤k-n1-n2mod⁡2n1<n1,D1,n1≤k-n1-n2mod⁡2n1<2n1.
The value ofsk for k-n1-n2≡0(mod2n1) is opposite to the corresponding tk.
We havesk=tk for 0<k-n1-n2(mod2n1)<n1 as the value of sn1+n2 is changed in the D1 of sk.
As all the summations insk and tk are the same for n1≤k-n1-n2(mod⁡2n1)<2n1, we get sk=tk and our claim follows.Using the same method, we can also prove the following theorem.Theorem 7.
Letf(x) and g(x) be denoted as above. If n1 is odd, n2 is odd, and n1+n2>n3, then the values of functions sk(α1,α2,…,αn), n1+n2≤k≤n1+n2+n3-1 have two cases. (25)skα1,α2,…,αn=1-tk,k-2n1-n2≡0mod⁡2n1,tk,k-2n1-n2>0mod⁡2n1,That is, the changed value appears at the positionk where k-n1-n2≡n1(mod⁡2n1).Corollary 8.
Letf(x) and g(x) be denoted as above. If n1=1 and n1+n2>n3, then the values of function sk(α1,α2,…,αn), 1≤k≤n1+n2+n3-1 are (26)skα1,α2,…,αn=0,if1≤k≤n1+n2-1,n2+1mod⁡2,ifk≥n1+n2,k≡n2+1mod⁡2,n2mod⁡2,ifk≥n1+n2,k≡n2mod⁡2.Proof.
As all the coefficientsak, 1≤k≤n1+n2-1 equal zero, the first case is straightforward. For n1+n2≤k≤n1+n2+n3-1, we have sk=D1+D2+D3+D4=D4=k and the corollary follows.We have discussed the four cases concerning the three-piece polynomials overGF(2). The condition n1+n2>n3 guarantees that the above cases cover all the possible kinds of three-piece polynomials. The number “1” does occupy a great proportion of the values of sk(α1,α2,…,αn), as the examples shown in Table 1.Table 1
Examples of three piece polynomials(6,12,15)TP, (6,13,14)TP, (5,12,15)TP, and (5,13,14)TP with their coefficients ai and the value of symmetric polynomials sk.
Polynomial ( a 0 , a 1 , … , a n ) 111111000000000000111111111111111 6,12,15 T P 111111000000000000011111111111111 6,13,14 T P 11111000000000000111111111111111 5,12,15 T P 11111000000000000011111111111111 5,13,14 T P  ( s 1 , s 2 , … , s n - 1 ) 1111111111111111111111111111111 6,12,15 T P 1111111111111111110111110111110 6,13,14 T P 111101111011110101101111010110 5,12,15 T P 111101111011110111101101011110 5,13,14 T P


### 3.2. Experiment Results

Next, we search for the three-piece polynomialf(x) whose decomposition is f(x)=(x+1)g(x) with g(x) irreducible. As there exists a trinomial or pentanomial basis for GF(2n) having at most four elements of trace one for each n∈[2,10000] [4], the polynomial g(x) with less number of trace-one elements that appeared in its polynomial basis is acceptable.With the formulatr⁡(1)≡nmod⁡2, we choose the number of trace-one elements to be at most four, and the result showed that the three-piece polynomials fitting these requirements exist for a great number of n, and we guess they exist for n≥40. The proof for this conjecture is difficult as it remains open to prove the existence of irreducible polynomials when almost all coefficients of them are prescribed [9].If we want to get a polynomial basis with less than two trace-one elements from a three-piece polynomial, then almost every odd degree will upset us. These two results are illustrated in Tables2 and 3.Table 2
Three piece polynomialsf(x)=(x+1)g(x) with f(x) irreducible. The number of trace-one elements in the polynomial basis formed by g(x) is no more than four.
D e g r e e n 1 , n 2 , n 3 T P/none 20 ( 7,5 , 9 ) 21 ( 7,12,3 ) 22 ( 2,17,4 ) 23 ( 5,10,9 ) 24 ( 7,9 , 9 ) 25 ( 7,16,3 ) 26 ( 9,7 , 11 ) 27 ( 9,6 , 13 ) 28 ( 12,15,2 ) 29 None 30 ( 2,25,4 ) 31 ( 11,18,3 ) 32 ( 2,23,8 ) 33 ( 13,4 , 17 ) 34 ( 8,17,10 ) 35 ( 9,22,5 ) 36 ( 2,31,4 ) 37 ( 7,28,3 ) 38 None 39 None 40 ( 4,31,6 ) 41 ( 13,20,9 ) 42 ( 4,25,14 ) 43 ( 9,18,17 ) 44 ( 6,19,20 ) 45 ( 13,12,21 ) 46 ( 4,29,14 ) 47 ( 13,14,21 ) 48 ( 6,27,16 ) 49 ( 15,16,19 ) 50 ( 12,25,14 ) 51 ( 15,18,19 ) 52 ( 4,35,14 ) 53 ( 13,16,25 ) 54 ( 8,21,26 ) 55 ( 17,30,9 ) 56 ( 15,25,17 ) 57 ( 17,12,29 ) 58 ( 6,45,8 ) 59 ( 13,26,21 ) 60 ( 4,43,14 ) 61 ( 15,40,7 ) 62 ( 4,53,6 ) 63 ( 19,34,11 ) 64 ( 8,47,10 ) 65 ( 19,40,7 ) 66 ( 6,45,16 ) 67 ( 19,26,23 ) 68 ( 12,31,26 ) 69 ( 19,36,15 ) 70 ( 12,45,14 ) 71 ( 29,34,9 ) 72 ( 2,63,8 ) 73 ( 19,32,23 ) 74 ( 14,29,32 ) 75 ( 17,34,25 ) 76 ( 16,31,30 ) 77 ( 21,20,37 ) 78 ( 8,57,14 ) 79 ( 21,42,17 ) 80 ( 6,67,8 ) 81 ( 21,48,13 ) 82 ( 12,57,14 ) 83 ( 23,22,39 ) 84 ( 14,39,12 ) 85 ( 21,40,25 ) 86 ( 4,73,10 ) 87 ( 25,54,9 ) 88 ( 6,75,8 ) 89 ( 33,52,5 ) 90 ( 14,61,16 ) 91 ( 23,26,43 ) 92 ( 10,59,24 ) 93 ( 23,68,3 ) 94 ( 2,89,4 ) 95 ( 17,34,45 ) 96 ( 16,63,18 ) 97 ( 25,40,33 ) 98 ( 2,89,8 ) 99 ( 25,66,9 ) 100 ( 18,51,32 ) 101 ( 31,64,7 )Table 3
Three piece polynomialsf(x)=(x+1)g(x) with g(x) irreducible. The number of trace-one elements in the polynomial basis formed by g(x) is no more than two.
D e g r e e n 1 , n 2 , n 3 T P/none 20 None 21 None 22 ( 2,17,4 ) 23 None 24 ( 8,7 , 10 ) 25 None 26 None 27 ( 13,6 , 9 ) 28 ( 12,15,2 ) 29 None 30 ( 2,25,4 ) 31 None 32 ( 8,23,2 ) 33 None 34 ( 8,17,10 ) 35 None 36 ( 2,31,4 ) 37 None 38 None 39 None 40 ( 4,31,6 ) 41 None 42 ( 14,25,4 ) 43 ( 13,26,5 ) 44 ( 10,23,12 ) 45 None 46 ( 12,21,14 ) 47 None 48 ( 8,31,10 ) 49 None 50 ( 12,25,14 ) 51 None 52 ( 12,39,2 ) 53 None 54 ( 18,17,20 ) 55 None 56 None 57 None 58 ( 6,45,8 ) 59 None 60 ( 14,43,4 ) 61 None 62 ( 4,53,6 ) 63 None 64 ( 8,47,10 ) 65 None 66 ( 16,45,6 ) 67 ( 33,6 , 29 ) 68 ( 20,47,2 ) 69 None 70 ( 12,45,14 ) 71 None 72 ( 8,63,2 ) 73 None 74 ( 30,29,16 ) 75 ( 37,18,21 ) 76 ( 30,31,16 ) 77 None 78 ( 14,57,8 ) 79 None 80 ( 6,67,8 ) 81 None 82 ( 12,57,14 ) 83 None 84 ( 18,63,4 ) 85 None 86 ( 10,73,4 ) 87 None 88 ( 6,75,8 ) 89 None 90 ( 14,61,16 ) 91 None 92 ( 12,79,2 ) 93 None 94 ( 2,89,4 ) 95 ( 29,58,9 ) 96 ( 16,63,18 ) 97 None 98 ( 8,89,2 ) 99 None 100 ( 32,51,18 ) 101 NoneFor example, we taken=88 in Table 2 to see how it works. The three-piece polynomial is (6,75,8)TP representing the polynomial f(x)=x88+x87+x86+x85+x84+x83+x7+x6+x5+x4+x3+x2+x+1. The value set of sk of f(x) is (27)1⋯1︸80ones0111110.We decompose f(x) as f(x)=(x+1)g(x)=(x+1)(x87+x85+x83+x6+x4+x2+1) with g(x) irreducible, and the value set of sk of g(x) is (28)0⋯0︸80zeros100000.Combining with the fact thattr⁡(1)=87mod⁡2≡1, we know the polynomial basis of g(x) has two trace-one elements.


## 3.1. The Three Piece Polynomials

Definition 1.
Let(8)fx=a0xn+a1xn-1+a2xn-2+⋯+an-1x+anbe a polynomial over GF(2) with nonzero constant term. If (a0,a1,…,an)=(ones(n1),zeros(n2),ones(n3)) where ones(k) and zeros(k) mean k consecutive bits of ones and zeros, respectively, we call f(x) three-piece polynomial over GF(2) and denote it by its coefficients as (n1,n2,n3)TP.Lemma 2.
Letf(x)=a0xn+a1xn-1+a2xn-2+⋯+an-1x+an be a three-piece polynomial with coefficients (n1,n2,n3)TP over GF(2). Let α1,α2,…,αn be the roots of f(x); if n1≥2, then (9)skα1,α2,…,αn=1,0<k<n1.Proof.
Ifn1≥2, then a0=a1=⋯=an1-1=1, and the Newton formula tells us that s1=a1=1 and s2=s1a1+2a2=1. Suppose sk=1 is true for 1≤k≤n1-2; then ak+1=1 and (10)sk=a1sk-1+a2sk-2+⋯+ak-1s1+kak=k-1·1+k=1.We have (11)sk+1=a1sk+a2sk-1+⋯+aks1+k+1ak+1=k·1+k+1=1.We mainly divide our theorems into two parts according to the parity ofn1. First, let us consider the condition that n1 is even.Theorem 3.
Letf(x) be denoted as above. If both n1 and n2 are even, then the values of functions sk(α1,α2,…,αn), 0≤k≤n-1 all equal one.Proof.
From Lemma2, we know that sk=1 for 1≤k≤n1-1. We have (12)sn1=a1sn1-1+a2sn1-2+⋯+an1-1s1+n1an1=n1-1·1+0=1,as n1 is even and an1=0. Suppose sn1+k=1 is true for 0≤k≤n2-2; then (13)sn1+k+1=a1sn1+k+a2sn1+k-1+⋯+an1-1sk+2+an1sk+1+⋯+an1+ks1+n1+k+1an1+k+1=n1-1·1+0=1,as an1+k+1=0. Here we come to the next even number n1+n2 with an1+n2=1, (14)sn1+n2=a1sn1+n2-1+a2sn1+n2-2+⋯+an1+n2-1s1+n1+n2an1+n2=n1-1·1+0=1.Suppose sn1+n2+k=1 is true for 0≤k≤n3-2; then (15)sn1+n2+k+1=a1sn1+n2+k+a2sn1+n2+k-1+⋯+an1-1sn2+k+2+an1sn2+k+1+⋯+an1+n2+ks1+n1+n2+k+1an1+n2+k+1=n1-1·1+k+1·1+n1+n2+k+1=1,as an1+n2=an1+n2+1=⋯=an1+n2+n3-1=1.In the following proofs, we still focus on the changes of the value in the summations of the symmetric polynomialsk. To simplify narration, we will divide the summations in sk into four parts {D1,D2,D3,D4} according to the subscript of ai. That is, the summations aisk-i with 1≤i<n1 are contained in D1, the summation aisk-i with n1≤i<n1+n2 comprises D2, the summations aisk-i in D3 are with n1+n2≤i<n, and the ending part D4=kak.Theorem 4.
Letf(x) be denoted as above. If n1 is even, n2 is odd, and n1+n2>n3, then the values of functions sk(α1,α2,…,αn), 0≤k≤n-1, are (16)skα1,α2,…,αn=1,if1≤k≤n1+n2-1,0,ifk≥n1+n2,k-n1-n2≡0mod⁡n1,1,ifk≥n1+n2,k-n1-n2>0mod⁡n1.Proof.
The first case is contained in Theorem3.
For the remaining cases, we declare they are periodic. We first show one period in the following. That is, forn1+n2≤k≤n1+n2+n1 we have(17)sk=∑i≤n1-1aisk-i+∑n1=in1+n2-1aisk-i+∑i=n1+n2k-1aisk-i+kak=∑i≤n1-1sk-i+∑i=n1n1+n2-10·sk-i+∑i=n1+n2k-1sk-i+k=D1+D2+D3+D4.
By the assumptionn1+n2>n3, we get sk-i=1 for n1+n2≤i≤k-1<n1+n2+n1 and D2+D3+D4=0+k-n1-n2+k=1; these simplify the above equation to sk=D1+1.
For the value ofsn1+n2+1, as sn1+n2 appears in the D1 of sn1+n2+1 and its value is “0” we have sn1+n2+1=1.
We go on our proof by induction. Supposest=1 holds for all t satisfying n1+n2<t<k<n1+n2+n1; only the summation with sn1+n2 equals zero in D1 of sk, so sk=n1-2+1=1.
Forsn1+n2+n1, as sn1+n2 goes into the summation in D2, the value of the summation D1 turns back to n1-1 and we have sn1+n2+n1=0. Now, we finished computing the value of sk in one period in our declaration, which is n1+n2<k≤n1+n2+n1.
The conditionn1+n2>n3 guarantees the subsequent computations can still use sk=D1+1 for (17), as sk-i=1 and D2+D3+D4=0+k-n1-n2+k=1 still holds. So the above method will work for the next periods, and our declaration holds.Next we will deal with the situation thatn1 is odd, which is more complicated. It has been proved that sk=1 for k≤n1-1 in Lemma 2.Lemma 5.
Letf(x) be denoted as above. If n1 is odd, then the values of functions sk(α1,α2,…,αn), n1≤k≤n1+n2-1, are(18)skα1,α2,…,αn=0,k-n1≡0mod⁡n1,1,k-n1>0mod⁡n1.Proof.
We follow the idea in the proof of Theorem4. For n1≤k≤n1+n2-1, let(19)sk=∑i≤n1-1aisk-i+∑i=n1k-1aisk-i+kak=∑i≤n1-1sk-i+∑i=n1k-10·sk-i+k·0=D1.
We havesn1=n1-1=0 and it fixes the value of D1 in st for n1<t≤n1+n1-1 to be n1-2 which makes st=1. If n1<n2 then sn1+n1=n1-1=0 and the next period starts; otherwise the equation holds within one period.In the following, we will deal withsk with k≥n1+n2; remember that n1 is odd. We define a comparative sequence here to simplify the narration. Let bi be the coefficient of a polynomial m(x) with (20)bi=ai,1≤i<n1+n2,0,n1+n2≤i,and then sk of m(x), which is denoted by tk, follows the period shown in Lemma 5. That is,(21)tk=D1=0,k-n1≡0mod⁡n1,1,k-n1>0mod⁡n1.Theorem 6.
Letf(x) and m(x) be denoted as above. If n1 is odd, n2 is even, and n1+n2>n3, then the values of functions sk(α1,α2,…,αn), n1+n2≤k≤n1+n2+n3-1 have two cases. (22)skα1,α2,…,αn=1-tk,k-n1-n2≡0mod⁡2n1,tk,k-n1-n2>0mod⁡2n1.Proof.
Forn1+n2≤k≤n1+n2+n1, we have(23)sk=∑i≤n1-1aisk-i+∑i=n1n1+n2-1aisk-i+∑i=n1+n2k-1aisk-i+kak=D1+D2+D3+D4=D1+k-n1-n2+k=D1+1.
Forn1+n2+n1≤k<n1+n2+2n1, we have D3=k-1-n1-n2 as sn1=0 enters the summations of D3, so sk=D1. By induction, we have(24)sk=D1+1,0≤k-n1-n2mod⁡2n1<n1,D1,n1≤k-n1-n2mod⁡2n1<2n1.
The value ofsk for k-n1-n2≡0(mod2n1) is opposite to the corresponding tk.
We havesk=tk for 0<k-n1-n2(mod2n1)<n1 as the value of sn1+n2 is changed in the D1 of sk.
As all the summations insk and tk are the same for n1≤k-n1-n2(mod⁡2n1)<2n1, we get sk=tk and our claim follows.Using the same method, we can also prove the following theorem.Theorem 7.
Letf(x) and g(x) be denoted as above. If n1 is odd, n2 is odd, and n1+n2>n3, then the values of functions sk(α1,α2,…,αn), n1+n2≤k≤n1+n2+n3-1 have two cases. (25)skα1,α2,…,αn=1-tk,k-2n1-n2≡0mod⁡2n1,tk,k-2n1-n2>0mod⁡2n1,That is, the changed value appears at the positionk where k-n1-n2≡n1(mod⁡2n1).Corollary 8.
Letf(x) and g(x) be denoted as above. If n1=1 and n1+n2>n3, then the values of function sk(α1,α2,…,αn), 1≤k≤n1+n2+n3-1 are (26)skα1,α2,…,αn=0,if1≤k≤n1+n2-1,n2+1mod⁡2,ifk≥n1+n2,k≡n2+1mod⁡2,n2mod⁡2,ifk≥n1+n2,k≡n2mod⁡2.Proof.
As all the coefficientsak, 1≤k≤n1+n2-1 equal zero, the first case is straightforward. For n1+n2≤k≤n1+n2+n3-1, we have sk=D1+D2+D3+D4=D4=k and the corollary follows.We have discussed the four cases concerning the three-piece polynomials overGF(2). The condition n1+n2>n3 guarantees that the above cases cover all the possible kinds of three-piece polynomials. The number “1” does occupy a great proportion of the values of sk(α1,α2,…,αn), as the examples shown in Table 1.Table 1
Examples of three piece polynomials(6,12,15)TP, (6,13,14)TP, (5,12,15)TP, and (5,13,14)TP with their coefficients ai and the value of symmetric polynomials sk.
Polynomial ( a 0 , a 1 , … , a n ) 111111000000000000111111111111111 6,12,15 T P 111111000000000000011111111111111 6,13,14 T P 11111000000000000111111111111111 5,12,15 T P 11111000000000000011111111111111 5,13,14 T P  ( s 1 , s 2 , … , s n - 1 ) 1111111111111111111111111111111 6,12,15 T P 1111111111111111110111110111110 6,13,14 T P 111101111011110101101111010110 5,12,15 T P 111101111011110111101101011110 5,13,14 T P


## 3.2. Experiment Results

Next, we search for the three-piece polynomialf(x) whose decomposition is f(x)=(x+1)g(x) with g(x) irreducible. As there exists a trinomial or pentanomial basis for GF(2n) having at most four elements of trace one for each n∈[2,10000] [4], the polynomial g(x) with less number of trace-one elements that appeared in its polynomial basis is acceptable.With the formulatr⁡(1)≡nmod⁡2, we choose the number of trace-one elements to be at most four, and the result showed that the three-piece polynomials fitting these requirements exist for a great number of n, and we guess they exist for n≥40. The proof for this conjecture is difficult as it remains open to prove the existence of irreducible polynomials when almost all coefficients of them are prescribed [9].If we want to get a polynomial basis with less than two trace-one elements from a three-piece polynomial, then almost every odd degree will upset us. These two results are illustrated in Tables2 and 3.Table 2
Three piece polynomialsf(x)=(x+1)g(x) with f(x) irreducible. The number of trace-one elements in the polynomial basis formed by g(x) is no more than four.
D e g r e e n 1 , n 2 , n 3 T P/none 20 ( 7,5 , 9 ) 21 ( 7,12,3 ) 22 ( 2,17,4 ) 23 ( 5,10,9 ) 24 ( 7,9 , 9 ) 25 ( 7,16,3 ) 26 ( 9,7 , 11 ) 27 ( 9,6 , 13 ) 28 ( 12,15,2 ) 29 None 30 ( 2,25,4 ) 31 ( 11,18,3 ) 32 ( 2,23,8 ) 33 ( 13,4 , 17 ) 34 ( 8,17,10 ) 35 ( 9,22,5 ) 36 ( 2,31,4 ) 37 ( 7,28,3 ) 38 None 39 None 40 ( 4,31,6 ) 41 ( 13,20,9 ) 42 ( 4,25,14 ) 43 ( 9,18,17 ) 44 ( 6,19,20 ) 45 ( 13,12,21 ) 46 ( 4,29,14 ) 47 ( 13,14,21 ) 48 ( 6,27,16 ) 49 ( 15,16,19 ) 50 ( 12,25,14 ) 51 ( 15,18,19 ) 52 ( 4,35,14 ) 53 ( 13,16,25 ) 54 ( 8,21,26 ) 55 ( 17,30,9 ) 56 ( 15,25,17 ) 57 ( 17,12,29 ) 58 ( 6,45,8 ) 59 ( 13,26,21 ) 60 ( 4,43,14 ) 61 ( 15,40,7 ) 62 ( 4,53,6 ) 63 ( 19,34,11 ) 64 ( 8,47,10 ) 65 ( 19,40,7 ) 66 ( 6,45,16 ) 67 ( 19,26,23 ) 68 ( 12,31,26 ) 69 ( 19,36,15 ) 70 ( 12,45,14 ) 71 ( 29,34,9 ) 72 ( 2,63,8 ) 73 ( 19,32,23 ) 74 ( 14,29,32 ) 75 ( 17,34,25 ) 76 ( 16,31,30 ) 77 ( 21,20,37 ) 78 ( 8,57,14 ) 79 ( 21,42,17 ) 80 ( 6,67,8 ) 81 ( 21,48,13 ) 82 ( 12,57,14 ) 83 ( 23,22,39 ) 84 ( 14,39,12 ) 85 ( 21,40,25 ) 86 ( 4,73,10 ) 87 ( 25,54,9 ) 88 ( 6,75,8 ) 89 ( 33,52,5 ) 90 ( 14,61,16 ) 91 ( 23,26,43 ) 92 ( 10,59,24 ) 93 ( 23,68,3 ) 94 ( 2,89,4 ) 95 ( 17,34,45 ) 96 ( 16,63,18 ) 97 ( 25,40,33 ) 98 ( 2,89,8 ) 99 ( 25,66,9 ) 100 ( 18,51,32 ) 101 ( 31,64,7 )Table 3
Three piece polynomialsf(x)=(x+1)g(x) with g(x) irreducible. The number of trace-one elements in the polynomial basis formed by g(x) is no more than two.
D e g r e e n 1 , n 2 , n 3 T P/none 20 None 21 None 22 ( 2,17,4 ) 23 None 24 ( 8,7 , 10 ) 25 None 26 None 27 ( 13,6 , 9 ) 28 ( 12,15,2 ) 29 None 30 ( 2,25,4 ) 31 None 32 ( 8,23,2 ) 33 None 34 ( 8,17,10 ) 35 None 36 ( 2,31,4 ) 37 None 38 None 39 None 40 ( 4,31,6 ) 41 None 42 ( 14,25,4 ) 43 ( 13,26,5 ) 44 ( 10,23,12 ) 45 None 46 ( 12,21,14 ) 47 None 48 ( 8,31,10 ) 49 None 50 ( 12,25,14 ) 51 None 52 ( 12,39,2 ) 53 None 54 ( 18,17,20 ) 55 None 56 None 57 None 58 ( 6,45,8 ) 59 None 60 ( 14,43,4 ) 61 None 62 ( 4,53,6 ) 63 None 64 ( 8,47,10 ) 65 None 66 ( 16,45,6 ) 67 ( 33,6 , 29 ) 68 ( 20,47,2 ) 69 None 70 ( 12,45,14 ) 71 None 72 ( 8,63,2 ) 73 None 74 ( 30,29,16 ) 75 ( 37,18,21 ) 76 ( 30,31,16 ) 77 None 78 ( 14,57,8 ) 79 None 80 ( 6,67,8 ) 81 None 82 ( 12,57,14 ) 83 None 84 ( 18,63,4 ) 85 None 86 ( 10,73,4 ) 87 None 88 ( 6,75,8 ) 89 None 90 ( 14,61,16 ) 91 None 92 ( 12,79,2 ) 93 None 94 ( 2,89,4 ) 95 ( 29,58,9 ) 96 ( 16,63,18 ) 97 None 98 ( 8,89,2 ) 99 None 100 ( 32,51,18 ) 101 NoneFor example, we taken=88 in Table 2 to see how it works. The three-piece polynomial is (6,75,8)TP representing the polynomial f(x)=x88+x87+x86+x85+x84+x83+x7+x6+x5+x4+x3+x2+x+1. The value set of sk of f(x) is (27)1⋯1︸80ones0111110.We decompose f(x) as f(x)=(x+1)g(x)=(x+1)(x87+x85+x83+x6+x4+x2+1) with g(x) irreducible, and the value set of sk of g(x) is (28)0⋯0︸80zeros100000.Combining with the fact thattr⁡(1)=87mod⁡2≡1, we know the polynomial basis of g(x) has two trace-one elements.


## 4. Conclusion

We investigated the three-piece polynomials to get the polynomial basis with small number of trace-one elements. The regular pattern shown by the value ofsk of the three-piece polynomial is the reason to choose them. Our numerical experiments showed that the three-piece polynomial relative to polynomial basis with small number of trace-one elements exists for many degrees, but the proof of the existence remains unsolved.



---

*Source: 9149041-2016-12-05.xml*