# On thek-Error Linear Complexity of Binary Sequences Derived from the Discrete Logarithm in Finite Fields

Authors: Zhixiong Chen; Qiuyan Wang
Journal: Complexity
 (2019)

---

## Abstract

LetFq be the finite field with q=pr elements, where p is an odd prime. For the ordered elements ξ0,ξ1,…,ξq-1∈Fq, the binary sequence σ=(σ0,σ1,…,σq-1) with period q is defined over the finite field F2={0,1} as follows: σn=0,ifn=0,(1-χ(ξn))/2,if1≤n<q,σn+q=σn, where χ is the quadratic character of Fq. Obviously, σ is the Legendre sequence if r=1. In this paper, our first contribution is to prove a lower bound on the linear complexity of σ for r≥2, which improves some results of Meidl and Winterhof. Our second contribution is to study the distribution of the k-error linear complexity of σ for r=2. Unfortunately, the method presented in this paper seems not suitable for the case r>2 and we leave it open.


---

## Body

## 1. Introduction

Pseudorandom sequences play an important role in cryptography; for example, they are used as keys in private-key cryptosystems [1, 2]. One of the most remarkable cryptosystems is the one-time pad (also referred to as Vernam cipher), where the plaintext message is added bit by bit (or in general character by character) to a nonrepeating random sequence of the same length [1, 2]. The security of the one-time pad entirely relies on the key sequence with special cryptographic properties, such as the balance, small correlation, and high linear complexity [3]. There are many ways to design suitable sequences. Legendre sequence introduced below is a classic sequence defined using (multiplicative) character of finite fields.Letp be an odd prime; theLegendre sequencel=(l0,l1,…,lp-1) of period p is defined as(1)ln=0,ifn≡0modp,1-n/p2,otherwise,where ·/p is the Legendre symbol. Legendre sequence has a number of good properties; the reader is referred to [4–8] for details.It is natural to extend the Legendre symbol construction to the extension fieldFq of Fp, where q=pr. We define below an ordered set for Fq.For a fix basis{γ1=1,γ2,…,γr} of Fq over Fp, we define for 0≤n<q(2)ξn=n1γ1+n2γ2+⋯+nrγr,if(3)n=n1+n2p+⋯+nrpr-1,0≤ni<p,i=1,…,r.Then Fq={ξ0=0,ξ1=1,…,ξq-1}.Given a primitive elementα∈Fq and any β∈Fq∗=Fq∖{0}, thediscrete logarithm of β with respect to α is the integer k, 0≤k<q-1, satisfying the following.(4)β=αkWe write k=indα(β). The computation of discrete logarithms is of considerable importance in cryptography. The security of many public-key cryptosystems depends on the intractability of the discrete logarithm problem [9].Then the (d-ary) discrete logarithm sequence σ=(σ0,σ1,…,σq-1) of period q is derived for an integer d>1:(5)σn=0,ifn=0,indα,dξn,if1≤n<q,σn+q=σn,where ξn∈Fq∗ and indα,d(ξn)∈{0,1,…,d-1} denotes indα(ξn)modd. The autocorrelation of σ was analyzed in [10] and its linear complexity was studied in [11, 12].In cryptographic applications, attention has been focused on the binary sequences over the finite fieldF2, since arithmetic is much easier to implement, with respect to both software and hardware. Therefore in this work we consider the case of d=2. Then the binary sequence σ given by (5) can be defined equivalently as(6)σn=0,ifn=0,1-χξn2,if1≤n<q,σn+q=σn,where χ is the quadratic character of Fq and ξn∈Fq for 1≤n<q. Indeed, themultiplicative characters of the finite filed Fq [13] are given by(7)ψjαi=e2π-1ij/p-1,i=0,1,…,q-2,for a primitive element of α∈Fq∗ and the quadratic character χ=ψ(q-1)/2 satisfies(8)χβ=1,ifβisthesquareofanelementofFq∗,-1,otherwise.It is easy to see that σ is balanced ((q+1)/2 many 0’s and (q-1)/2 many 1’s) with least period q. The measures of pseudorandomness of the binary sequence σ were studied in [14] and some related problems were considered in [15–17]. It is noted that when r=1, the σ is just the Legendre sequence l introduced above. Its linear complexity has been determined in [6], and its k-error linear complexity over Fp has been calculated by Aly and Winterhof [18]. Therefore, it is natural to investigate the linear complexity of the binary sequence σ in (6) and its k-error linear complexity for r≥2.We organize our contributions as follows. The coming section contains the notions of the linear complexity andk-error linear complexity of periodic sequences. In Section 3, we give a lower bound on the linear complexity of σ in (6) for r≥2. In Section 4, we present k-error linear complexity of σ for r=2. It should be noted that the results are different from [18, 19], in which the binary sequence σ is treated over Fp. Finally in Section 5, we draw some conclusions and present some open problems.


## 2. Preliminaries

In this section, we recall the notions of linear complexity andk-error linear complexity of periodic sequences over the finite field F2.Lets=(s0,s1,…,sN-1) be a binary sequence over F2 of period N. Thelinear complexity of s, denoted by L(s), is the smallest positive integer l satisfying the following linear recurrence relation(9)si+l=cl-1si+l-1+…+c1si+1+c0sifori≥0,where c0,c1,…,cl-1∈F2. From the viewpoint of engineers, the linear complexity (also called linear span) of a sequence s is the shortest length of a linear feedback shift register (LFSR) that produces s. Hence the linear complexity provides information on predictability and thus unsuitability for cryptography and plays an important role in the analysis of stream ciphers.Letc(x)=1+cl-1x+cl-2x2+⋯+c0xl, which is called acharacteristic polynomial of s. A characteristic polynomial with the smallest degree is called aminimal polynomial of s [1]. Let s(x)=s0+s1x+⋯+sN-1xN-1∈F2[x], which is called thegenerating polynomial of s. Then the following lemma gives a way to determine the linear complexity and minimal polynomial of periodic sequences.Lemma 1 (see [13]).
Lets be a binary sequence over F2 of period N. Then the minimal polynomial m(x) of s is(10)mx=xN-1gcd⁡xN-1,sx,and the linear complexity L(s) of s is given by(11)N-deg⁡gcd⁡xN-1,sx,where s(x) is the generating polynomial of s.Not only should periodic sequences used as key-streams have a large linear complexity, but also altering a few bits should not cause a significant decrease of the linear complexity. Hence we have the following notion.Definition 2 (see [20]).
Lets be a binary sequence over F2 of period N. For k≥1, the k-error linear complexity Lk(s) of s is the smallest linear complexity of a sequence s′ obtained from s by altering at most k elements among si(0≤i≤N-1) and continuing these changes periodically with the period N.The concept ofk-error linear complexity (the sphere complexity, a similar notion ofk-error linear complexity, was defined even earlier, please see [1] for details) is very useful in the study of the security of stream ciphers for cryptographic applications. A necessary condition for a key-stream generator is that sequences produced by it should possess high linear complexity and k-linear complexity. An efficient algorithm for determining the k-error linear complexity of binary sequences of period 2n was designed by Stamp and Martin in [20], and it was generalized to pn-periodic sequences over the finite field Fpm, where p is an odd prime [21].


## 3. A Lower Bound on Linear Complexity

In this section, we prove a lower bound on the linear complexity of the binary sequenceσ defined by (6) for r≥2. A bound also has been given in [11, 12], but the result in Theorem 4 improves that in [11, 12] greatly.Letordm(2) denote theorder of 2 modulo m; i.e., ordm(2) is the smallest positive integer d such that 2d≡1(modm).Lemma 3.
Letλ=ordp(2) with 1<λ<p. For r≥2, if 2p-1≢1(modp2), we have(12)ordpr2=λpr-1.Proof.
Supposeμ=ordpr(2). By 2λ≡1(modp), we have 2λ=1+ap for some integer a. It is easy to verify that (13)2λpr-1=1+appr-1=1+apr+…,2λpr-1≡1modpr.This implies that μ is a divisor of λpr-1. Since 2p-1≢1(modp2), we see that a≢0(modp).
The assumption2p-1≢1(modp2) implies that μ≥p. Then we write μ=λpw for some positive integer w and w≤r-1. Supposing w<r-1, we have(14)2λpw=1+appw=1+apw+1+…,which contradicts the fact that 2μ=2λpw and 2λpw≡1(modpr). Hence w=r-1 and μ=λpr-1. This completes the proof of this lemma.Theorem 4.
Let symbols be the same as before. If2p-1≢1modp2, then the linear complexity of σ in (6) with period q=pr(r≥2) satisfies(15)Lσ≥λpr-1,where λ is the order of 2 modulo p and 1<λ<p.Proof.
By the definition ofσ, we know that the least period of σ is q=pr. Let(16)Φrx=1+xpr-1+x2pr-1+…+xp-1pr-1∈F2x.Then xpr-1=(xpr-1-1)·Φ(r)(x) and Φ(r)(x) has exactly pr-pr-1 roots, which are pr-th primitive elements in the algebraic closure of F2. By Lemma 3, the polynomial Φ(r)(x) can be written as the product of (p-1)/λ irreducible polynomials of degree λpr-1, i.e.,(17)Φrx=φ1rxφ2rx⋯φp-1/λrx.In the sequel, we will show that there exists i0 (1≤i0≤(p-1)/λ) such that φi0(r)(x)∤s(x), where s(x) is the generating polynomial of σ.
SupposeΦ(r)(x)∣s(x); then s(x)=H(x)·Φ(r)(x) for some polynomial H(x)=h0+h1x+…+hpr-1-1xpr-1-1∈F2[x] of degree <pr-1. By the product of two polynomials, we obtain(18)σi=σi+pr-1=…=σi+p-1pr-1=0,ifhi=0,1,ifhi=1,for 0≤i<pr-1, which implies σn=σn+pr-1 for any integer n and hence the period of σ equals pr-1. This contradicts the fact that σ is a pr-periodic sequence. Hence there exists at least one φi0(r)(x) such that φi0(r)(x)∤s(x) and then Φ(r)(x)∤s(x). By Lemma 1, we have(19)Lσ≥deg⁡φi0rx=λpr-1.The bound is much better than that of [11, Thms. 1 and 2] and [12]. Some examples are listed in Table 1. The bound is tight for certain q; see, for example, q=25 in the table. It should emphasized that Theorem 4 is indeed a general result for any pr-periodic binary sequences over F2.Table 1
Comparison of bounds onL(σ).
q=pr exact value ofL(σ) our bound Meidl and Winterhof’s bound q  =  5 2 20 20 1 (by [11, Thm. 2])  q  =  5 3 124 100 6 (by [11, Thm. 1])  q  =  5 4 620 500 2 (by [12, Coro. 1])  q  =  5 5 3124 2500 10 (by [11, Thm. 1])  q  =  5 6 15620 12500 3 (by [12, Coro. 1])  q  =  7 3 340 147 9 (by [11, Thm. 1])  q  =  7 4 2394 1029 2 (by [12, Coro. 1])Prop. 2 in [22] indicates that the linear complexity of pr-periodic sequences over Fpm is at least pr-1+1. Theorem 4 is a similar statement to that in [22] for binary sequences. We remark that Theorem 4 covers almost all primes. It is shown that primes satisfying 2p-1≡1(modp2) are very rare. Up to 6×1017, there are only two such primes (a prime p satisfying 2p-1≡1modp2 is called a Wieferich prime), 1093 and 3511 [23].


## 4.k-Error Linear Complexity

In this section we letq=p2. The proof of Theorem 4 helps us to give a lower bound on the k-error linear complexity of σ in (6). We choose {1,γ} as a basis of Fp2 over Fp. Then for n=n1+n2p with 0≤n1,n2<p, we write ξn=n1+n2γ∈Fp2.We first prove some lemmas.Lemma 5.
For0≤i<p, let Ti={i+jγ:0≤j<p}⊆Fp2. Then we have(20)i·T1=i1+jγ:0≤j<p=Ti.Proof.
For each1≤i<p, when j runs through the set {0,1,…,p-1}, so does [ij], where [ij] denotes ijmodp. Then, for 0≤j1,j2<p, we have (21)i1+jγ=i+ijγ∈Ti,i1+j1γ≠i1+j2γ,if j1≠j2. The proof is finished.Lemma 6.
For the binary sequenceσ in (6), let vi=(σi,σi+p,…,σi+(p-1)p)∈F2p and wt(vi) denotes the weight of the vector vi. Then we have the following:(1)
for1≤i<p, wt(v0)=p-1 and wt(vi)=(p-1)/2 if χ(γ)=-1;(2)
for1≤i<p, wt(v0)=0 and wt(vi)=(p+1)/2 if χ(γ)=1.Proof.
Firstly, we showχ(i)=1 for any i∈{1,2,…,p-1}⊆Fp2. Since χ is the quadratic character of Fp2, χ can be written as χ=η(p2-1)/2, where η is a character of order p2-1 of Fp2. From i(p2-1)/2=(ip-1)(p+1)/2=1+ap for some integer a, we have(22)χi=ηip2-1/2=η1=1.Consequently, for 1≤j<p, we obtain χ(ξjp)=χ(jγ)=χ(j)χ(γ)=χ(γ). Then we derive(23)wtv0=p-1,ifχγ=-1,0,otherwise.
Secondly, by (6), we see that χ(ξn)=(-1)σn for any 0≠ξn∈Fp2. Hence by Lemma 5, wt(vi)=wt(vj) for 1≤i≠j<p. Since there are (p2-1)/2 many ξn∈Fp2 such that χ(ξn)=1, we have(24)∑0≤i<pwtvi=p2-12.Hence, for 1≤i<p(25)wtvi=p-12,ifχγ=-1,p+12,otherwise.For the binary sequenceσ defined in (6) with q=p2, let(26)Vix=∑j=0p-1σi+jpxi+jp,0≤i<p.Then the generating polynomial of σ is s(x)=∑i=0p-1Vi(x).Theorem 7.
Let symbols be the same as before. If2p-1≢1(modp2), then the k-error linear complexity of σ in (6) with period p2 satisfies(27)Lkσ≥λp,where λ(1<λ<p) is the order of 2 modulo p and(28)0≤k<p-122,ifχγ=1,1+p-122,ifχγ=-1.Proof.
By Lemma3, Φ(2)(x)=1+xp+x2p+…+x(p-1)p∈F2[x] is the product of (p-1)/λ many irreducible polynomials of degree λp; i.e.,(29)Φ2x=φ12xφ22x⋯φp-1/λ2x.
Letsk(x) be a polynomial of degree smaller than p2 over F2, and sk(x) has k many different terms from s(x), the generating polynomial of σ. Then we have(30)skx=sx+ex∈F2x,where e(x) is a polynomial of degree smaller than p2 and has exactly k many monomials. In the sequel, we will find an e(x) with the smallest k such that Φ(2)(x)∣sk(x).
Suppose(31)skx=sx+ex=hxΦ2x,where h(x)=h0+h1x+…+hp-1xp-1∈F2[x] and the deg(h(x)) is smaller than p. Then(32)ex=∑0≤i<phiXiΦ2x-Vix.Clearly, e(x) contains a summation Vi(x) if hi=0 and xiΦ(2)(x)-Vi(x) otherwise.
Ifχ(γ)=1, by Lemma 6 we have V0(x)=0 and each Vi(x) (1≤i<p) has (p+1)/2 many terms. It can be easily verified that e(x) in (32) is the polynomial with the smallest k=(p-1)2/2 terms such that Φ(2)(x)∣sk(x). The argument implies that if k<(p-1)2/2, there is no e(x) with k terms such that Φ(2)(x)∣sk(x). Among φ1(2)(x),…,φ(p-1)/λ(2)(x), there exists at least one φi(2)(x) such that φi(2)(x)∤sk(x), where k<(p-1)2/2. By Lemma 1, we have Lk(σ)≥λp.
Ifχ(γ)=-1, let(33)ex=Φ2x-V0x+∑1≤i<pVix=1+∑1≤i<pVix.By Lemma 6, e(x) is the polynomial with the smallest k=1+(p-1)2/2 terms such that Φ(2)(x)∣sk(x). Using the same method above, we have Lk(σ)≥λp if k<1+(p-1)2/2.
This completes the proof of this theorem.Next we consider the case that2 is primitive modulo p2 and the following lemma is required.Lemma 8.
For0≤i<p, let Vi(x)=∑0≤j<pσi+jpxi+jp∈F2[x]. Then we have(34)V0x≡0modxp-1andVix≡wximodxp-1,where(35)w=p+12,ifχγ=1,p-12,ifχγ=-1.Proof.
The proof can be derived directly from Lemma6.Theorem 9.
Let symbols be the same as before. Ifχ(γ)=1 and 2 is primitive modulo p2, then the k-error linear complexity of σ in (6) with period p2 satisfies the following:
( 1 ) When p≡5(mod8), we have(36)Lkσ=p2-1,ifk=0,p2-p+1,if1≤k<p-1,p2-p,ifp-1≤k<p-122,p-1,ifk=p-122,0,ifk≥p2-12.
( 2 ) When p≡3(mod8), we have(37)Lkσ=p2-p,if0≤k<p-122,p-1,ifk=p-122,0,ifk≥p2-12.Proof.
Since2 is primitive modulo p2, the two polynomials Φ(2)(x)=1+xp+…+x(p-1)p and 1+x+…+xp-1 are irreducible over F2.
For anye(x) with k<(p-1)2/2 many terms, from the proof of Theorem 7 we have Φ(2)(x)∤s(x) and Φ(2)(x)∤sk(x) for sk(x)=s(x)+e(x), where s(x) is the generating polynomial of σ. This means that Lk(σ)≥p2-p for k<(p-1)2/2.
Now we considers(x) modulo (xp-1). By Lemma 8, we have(38)sx≡p+12x+x2+…+xp-1modxp-1≡x+x2+…+xp-1,ifp≡5mod8,0,ifp≡3mod8.For the case p≡5mod8, from (38) we obtain the following: (1)
s(1)=0 and gcd⁡(s(x),(xp2-1)/(x-1))=1, then we have L0(σ)=p2-1.(2)
s(x)+1≡1+x+…+xp-1mod(xp-1), which indicates that L1(σ)=p2-p+1.(3)
s(x)+x+…+xp-1≡0mod(xp-1), which indicates that Lp-1(σ)=p2-p.
Putting everything together, the first statement of Theorem9 is proved. For the case p≡3mod8, it can be easily verified that L0(σ)=p2-p and the second statement of this theorem can be similarly proved.Theorem 10.
Let symbols be the same as before. Ifχ(γ)=-1 and 2 is primitive modulo p2, then the k-error linear complexity of σ in (6) with period p2 satisfies the following:
( 1 ) When p≡5(mod8), we have(39)Lkσ=p2-p,if0≤k<1+p-122,p,ifk=1+p-122,0,ifk≥p2-12.
( 2 ) When p≡3(mod8), we have(40)Lkσ=p2-1,ifk=0,p2-p+1,if1≤k<p-1,p2-p,ifp-1≤k<1+p-122,p,ifk=1+p-122,0,ifk≥p2-12.Proof.
The proof of Theorem10 is similar to that of Theorem 9 and we omit it.Theorems9 and 10 indicate that σ defined in (6) has good stability, or, in other words, the linear complexity is not significantly decreased by changing only a few (but not many) terms.


## 5. Final Remarks

In this work, we have studied an extension of the Legendre sequence, which has been widely considered in the literature. More exactly, we have investigated the linear complexity andk-error linear complexity of a binary pr-periodic sequence derived from the discrete logarithm in finite fields. We only give a lower bound on the linear complexity for r≥2 and the distribution of the k-error linear complexity for r=2. Therefore, it is interesting to consider the k-error linear complexity for r>2; we describe an open problem as follows.Open Problem. Determine the k-error linear complexity of σ defined in (6) for the case when r>2.By Lemma6, we find that σ1=σ2=⋯=σp-1 and σp=σ2p=⋯=σ(p-1)p. This sacrifices the pseudorandomness of the sequence. Therefore, we can modify the construction of σ (with period p2) as follows: (41)-1σn=1,ifn=0,jp,ifn=jpand1≤j<p,ipχξn,ifn=i+jpand1≤i<p,0≤j<p.The method given in this work can be used to consider the linear complexity and k-error linear complexity.Finally it should be remarked that there is another way to order the elements inFq. Let α be a primitive element of Fq and Fq={0,1,α,α2,…,αq-2} is an ordered set. The sequence ρ=(ρ0,ρ1,…) is defined as(42)ρn=0,ifn=q-12,1-χαn-12,otherwise.The sequence ρ is referred to as ageneralized Sidelnikov sequence, and the k-error linear complexity of ρ was determined over Fp for r=1) [18]. It is interesting to consider the k-error linear complexity over F2 of ρ.



---

*Source: 8635209-2019-07-04.xml*