Coding Theory using Linear Complexity of Finite Sequences
Tovohery Randrianarisoa

Impact of the malicious input data modification on the efficiency of 
quantum spatial search
    [
    
============================================================================================




We define a metric on ^n using the linear complexity of finite sequences. We will then develop a coding theory for this metric. We will give a Singleton-like bound and we will give constructions of subspaces of ^n achieving this bound. We will compute the size of balls with respect to this metric. In other words we will count how many finite sequences have linear complexity bounded by some integer r. The paper is motivated in part by the desire to design new code based cryptographic systems.




§ MOTIVATION


As we will explain in this section, the notion of weight of vectors are closely related to notion of linear complexity of the sequence. This motivates us to study the linear complexity of sequences as a new metric. For us to see this relation, let us first recall some notion from linear coding theory using the Hamming metric. 

In most part of this work, unless otherwise specified, we will always work with a finite field  of size q. 


Let = (x_1,⋯,x_n)∈^n. We define the weight ω() of  to be the number of non-zero entries of . If  and  are two elements of ^n, then we define the distance between 𝐚 and 𝐛 as (̣,)=ω(-).



A linear code  of length n over  is a subspace of ^n paired with the distance $̣ as in the previous definition. The minimum distance of a linear code is the smallest value ofd(,)for any two distinct codewords of.

The most important parameters for a linear codeare the size of the base field, the length, the dimension and its minimum distance. One has to optimize the choice of these parameters for applications. For example, one wants to construct codes with large dimension and large minimum distance at the same time and the base field should preferably be as small as possible (binary field for example). This is not an easy task as the minimum distance behaves in opposite to the dimension for example. This is explained by the following Singleton bound.

Let  be a linear code of length n and dimension k as subspace of ^n. Suppose that d is the minimum distance of . Then,

    d≤ n-k+1.


Due to this, we want to have codes which maximize both the dimension and the minimum distance of the code. Thus we want to have codes for which the inequality in the above definition is an equality. Such codes are defined as follows.


A linear code  which attains the Singleton bound i.e if  is of dimension k, d is its minimum distance and d=n-k+1, is called a maximum distance separable (MDS) code. 

Maximum distance separable codes exist. One easy construction is given by the following. Letn=q-1and let= (_1,⋯,_n)be a vector where its elements are the non-zero elements of. We define the evaluation map as

    ev_: [x]    →^n 
    
    f(x)    ↦(f(_1),⋯,f(_n))


Let[x]_< kbe the vector space of all polynomials of degree at mostk-1. Then the image= ev_([x]_< k)is an MDS code. This comes from the fact that a polynomial of degree at mostk-1can have at mostk-1roots. The code we described is called Reed-Solomon code. 

It is this relation between the property of the roots of polynomial which is interesting for us. Let us see the following theorem of König-Rados. For a proof of this theorem, one can have a look at Chapter 6 of <cit.>.

Let f(x)=a_0 +a_1 x + ⋯ + a_q-2x^q-2 be a polynomial over . Define the following matrix 

    = 
    [   a_0   a_1       a_q-2;   a_1     ⋰     ⋰   a_0;     ⋮     ⋰     ⋰     ⋮; a_q-2   a_0       a_q-3 ].

Suppose that the rank of  is equal to r. Then the number of roots of f(x) in ^* is given by q-1-r.


The matrixin the above theorem is a circulant matrix. It is easy to see that if its rank is equal tor, then the firstrrows ofare linearly independent and the other rows are linear combination of them. Furthermore, this tells us that the coefficients off(x)satisfy the following property.

    a_i+r = ∑_j=0^r-1 c_j a_i+j,  ∀ i∈.

Note that the coefficientsa_0,⋯,a_q-2satisfy a recurrence relation of orderr. Using the definitions which we will see in Section <ref>, we say that the coefficients of the polynomialsf(x)can be generated by a linear-feedback shift register (LFSR) of lengthrand this is the minimum possible forr. We say that(a_0,⋯,a_q-2)has linear complexityr. Moreover, our sequence gives a periodic sequence with periodq-1. To summarize, we have the following theorem, which is a direct consequence of the theorem of König-Rados.


Let f(x) = a_0 +a_1 x + ⋯ + a_q-2x^q-2 be a polynomial over . If f(x) has q-1-r roots, then (a_0,⋯,a_q-2) has linear complexity r and the evaluation  (f(_1),⋯,f(_n)) has weight r.


Through Theorem <ref>, we can relate the linear complexity of a periodic sequence with the weight of a vector. However, we have only periodic sequences. This raises the following question: What happens if we study any type of sequence i.e. we don't require the LFSR to be a periodic sequence with fixed period. We will answer this question in the next sections. First, in Section <ref>, we will introduce the notion of linear-feedback shift register. In Section <ref>, we will give a coding theory for finite sequences. We will use Section <ref> for a separate study on the number of finite sequences which can be generated by an LFSR of given length. Finally, we will conclude with Section <ref> and give some future work.



§ LINEAR-FEEDBACK SHIFT REGISTER

Letbe a finite field withqelements.


Left  be a field. A linear feedback shift register (LFSR) of order l over  is an infinite
sequence  over  such that, there are fixed c_j∈ 
with,

    a_i+l = ∑_j=0^l-1 c_j a_i+j,  ∀ i∈.

The feedback polynomial associated to  is

    f(z) = z^l - ∑_j=0^l-1 c_j z^j.

Let  be a LFSR over . The generating function A(z) associated to 
 is the formal power series

    A(z) = ∑_i=0^∞ a_i z^i.


One can show (Chapter 8 <cit.>) that for some polynomialg(z)of degreel-1at most, we have

    A(z) = g(z)/f^*(z),

wheref^*is the reciprocal polynomial given by

    f^*(z) = z^l f(1/z).

Given a non-zero finite sequence = (a_0,⋯,a_n-1)∈^n, the linear complexity  Ł(a_i) of the sequence is the smallest l such that

    a_i+l = ∑_j=0^l-1 c_j a_i+j,  ∀ i,   0≤ i≤ n-1,

for some fixed c_j∈. 

For a zero sequence, we set the linear complexity to be equal to zero.


Given a finite sequence, we can compute the shortest LFSR 
producing this sequence. This can be done using the Berlekamp-Massey algorithm inØ(n^2)field operations in(Chapter 8 of <cit.>). Furthermore if the linear complexity isn/2, thennsuccessive terms of the sequence are enough to uniquely find the shortest shift register. We present the algorithm in Algorithm <ref>. On input, we have a sequences_0,⋯,s_n-1of lengthn. On output, the algorithm generates the order and the feedback polynomialf(z)of the shortest LFSR generatings_0,⋯,s_n-1.


Let = (a_0,⋯,a_n-1) be a finite sequence of length n. Then Ł≤ n. Furthermore the only sequences attaining the bound upper bound n are of the form (0,⋯,0,a), with a∈^*.

We can just use a LFSR with  as initial state so that the maximum linear complexity is at most n. It is obvious that (0,⋯,0,a) has linear complexity n. Finally, if = (a_0,⋯,a_n-1) is such that a_j ≠ 0 for some j with 0≤ j≤ n-2. By taking c_i = 0 except when i = j, where c_j = a_n-1/a_j, we prove that a_n-1 = ∑_j=0^n-2 c_j a_j so that the linear complexity is at least n-1.


The key property of the linear complexity of sequences which will be used later is the following.

Let  and  be two finite sequences. If =  +, then

    Ł≤Ł + Ł.

Suppose that the generating function of the LFSR generating  and  are respectively

    g_a(z)/f_a^*(z),   and g_b(z)/f_b^*(z).

Then the generating function of the LFSR generating  is

    g_a(z)f_b^*(z)+g_b(z)f_a^*(z)/f_a^*(z)f_b^*(z).

And therefore,  can be generated by a LFSR with feedback 
polynomial f_a(z)f_b(z). Therefore the linear complexity is at most Ł +Ł.


§ A CODING THEORY FOR FINITE SEQUENCES USING THE LINEAR COMPLEXITY

Letbe a finite field and letnbe a positive integer. We will consider sets of lengthn.


Let = (a_0,⋯,a_n-1)∈^n and = (b_0,⋯,b_n-1)∈^n be two finite sequences of n elements of  each. Then we define a distance on ^n by the following,

    (̣,) = Ł( - ),

where Ł(0) = 0.


This map defines indeed a distance:

  *  By definition (̣,) = 0 ⇔ =.

  *  By definition of Ł, Ł≥ 0.

  * (̣,) = (̣,).

  *  For the triangular inequality,

    (̣,)    = Ł( - ) 
        = Ł( - + - ) 
       ≤Ł( -) + Ł( - ),  by Theorem <ref>
        = (̣,) + (̣,).


Like in coding theory, we can define a subset of^nand define the metric$̣ on this set. We will derive basic coding results for this context.
 



Let S be a subset of ^n. The minimum distance d of S is the minimum 
of (̣,) for distinct ,∈ S. We will describe the parameters 
of S as [n,♯ S,d]. In case S is a k-dimensional subspace of ^n, 
then, by additivity, d is the minimum linear complexity of the non-zero sequences in S and we 
will write [n,k,d].




For the next steps we want to have a look at the bounds on a  [n,♯ S,d]-subset of ^n.

Let  be a finite field of size q. Let S⊂^n be a set of finite sequence over  of length n, with minimum distance d. Then ♯ S≤ q^n-d+1.


Let us define the following linear map P as

    P:^n   →^n-d+1
    
    (a_0,⋯,a_n-1)   →[ 1   1 ][   a_0       a_n-d;     ⋮     ⋱     ⋮; a_d-1       a_n-1 ]

The restriction of this map must be injective on S. Otherwise if two sequences
 and  are mapped to the same image, then - is mapped to zero.
But this would imply that Ł(-)≤ d-1. This is in
contradiction with the minimum distance of S. 
By the injectivity, we must have that ♯ S≤♯(^n-d+1).


Note that in this proof, instead of using [ 1   1 ], we can use any vector with 1 as last entry. These operations are equivalent to the puncturing operation on codes. Namely using [ 0   0 1 ] is just puncturing at the first d-1 positions.

In case S is linear of dimension k over , then k≤ n-d+1.



We call a set of sequences S optimal if the minimum distance of S reaches the bound of the previous theorem i.e. if S has elements of length n and minimum distance d and ♯ S = q^n-d+1.



Let S be the set of sequences of length n over a finite field  defined by 

    S = { (0,⋯,0,a_1,⋯,a_k): a_i∈}.

Then, S is an optimal set of linear sequences of dimension k. That is because the sequences cannot be generated by a LFSR of length smaller than n-k+1 except when it is the zero sequence.


The nice property of using the set of sequences with the linear complexity as metric is that, in opposite to maximum distance separable codes, we can have optimal set of sequences for any parameters. We can make the construction, even for the binary field.



 §.§ Decoding of OSS

The decoding of OSS given in Example <ref> is straightforward. First let us look at the unique decoding property.


Suppose that S is an [n,M,d] set of sequences. Suppose that ∈ is equal to +, where ∈ S and Ł()<d/2. Then, the decomposition + is unique.


If = _1+_1 = _2+_2, then _1-_2 = _2-_1. Therefore d(x_1,x_2) = Ł(_2-_1). By Theorem <ref>, d(x_1,x_2)≤Ł(_2)+Ł(_1)<d. This is in contradiction with the minimum distance of S.



Let S, of dimension k, be the OSS in Example <ref>. Suppose that we know = + with ∈ S and Ł()<n-k+1/2. 
By Proposition <ref>, we know that  is unique. Since the n-k first entries of  are equal to zero. Then we know the first n-k entries of . Now, since Ł()<n-k+1/2, then we can uniquely recover the LFSR generating  by using the Berlekamp-Massey algorithm on the first n-k entries of e. We are therefore able to produce the whole  and then we compute = -.


We can modify the above decoding algorithm to get a decoding algorithm for the Reed-Solomon code in Section <ref>. The extra step is just that we need to interpolate a received codewords first to get a polynomial f(x) of degree q-2 at most. After this we apply the decoding algorithm for the OSS we gave above on the coefficients of this polynomial f(x). Notice that the Berlekamp-Massey in this case is applied to the last coefficients of the polynomial f(x).







§ NUMBER OF FINITE SEQUENCES GENERATED BY A LFSR WITH FIXED LENGTH


LFSR already has applications in cryptography. For instance, it is used when one wants to generate random keys. As we have seen, one can compute the linear complexity of a sequence using the Berlekamp-Massey algorithm. Thus, if a sequence has small linear complexity, one can easily find a LFSR generating this sequence. Due to this fact, we usually want to have sequences with large linear complexity. Therefore, one important question is to know how many finite sequences  have large linear complexity. Another motivation for this section is also that knowing the number of sequences with a given linear complexity is important for the security aspect of a code-based cryptosystem using linear complexity as metric.


Let  be an infinite sequence. If  can be generated by a LFSR of length n, then  can be generated by a LFSR of length i, for any i≥ n.


For a proof of this, if c_1,⋯,c_n-1 are the coefficients of the LFSR of length n, then 0,⋯,0,c_1,⋯,c_n-1 are the larger LFSRs.


By Lemma <ref>, we can just study the number of sequences which can be generated by a LFSRs of length n to know the number of sequences which has linear complexity smaller or equal to n. Studying sequences which can be generated by a LFSRs of length n can be in turn translated to studying some matrix  of the form

    = [     a_0     a_1                 a_n-r-1;     a_1       ⋰       ⋰ a_n-r-1   a_n-r;       ⋮       ⋰       ⋰       ⋰       ⋮;     a_r   a_r+1                   a_n-1 ]

We just need the condition that the last row is a linear combination of the previous rows. The matrices with the form of  are called are called Hankel matrices when they are square matrices. In <cit.>, Daykin called the general rectangular matrices persymmetric matrices. To go further with our counting, we will need the following reduction method as used by Daykin in <cit.>.

Fix and integer u such that 0≤ u< min(r,n-r-1). We define the following set

    𝒜_u = {(0,⋯,0,a_u,⋯,a_n-1): a_u≠ 0}.

Then for ∈𝒜_u, we recursively define θ_i, i=0,⋯, n-u-1 by

    a_uθ_0 = 1 
    ∑_l=0^i  a_u+lθ_i-l = 0
    .


Now define the following matrices
 

    = [ θ_0   0   0       0; θ_1 θ_0   0   ⋱   ⋮;   ⋮   ⋱   ⋱   ⋱   0;   ⋮   ⋱   ⋱   ⋱   0; θ_r         θ_1 θ_0 ],   = [     θ_0     θ_1                 θ_n-r-1;       0     θ_0     θ_1       ⋱       ⋮;       0       ⋱       ⋱       ⋱       ⋮;       ⋮       ⋱       ⋱       ⋱     θ_1;       0               0       0     θ_0 ]


    = [   0       0   0 θ_0;   ⋮   ⋰   0 θ_0 θ_1;   0   ⋰   ⋰   ⋰   ⋮;   0 θ_0   ⋰   ⋰   ⋮; θ_0 θ_1         θ_u;     ],   = [   θ_u+2   θ_u+3                   θ_n-r;   θ_u+3       ⋰       ⋰ θ_n-r-1 θ_n-r+1;       ⋮       ⋰       ⋰       ⋰       ⋮;       ⋮   θ_r+1       ⋰       ⋰ θ_n-u-2;   θ_r+1   θ_r+2         θ_n-u-2 θ_n-u-1 ]


For a fixed u with 0≤ u< min(r,n-r-1), there is a bijection between 𝒜_u and the set { (θ_0,⋯,θ_n-u-1): θ_0∈^*, θ_i∈ , 1≤ i≤ n-u-1} given by 

    = [    ;   - ]



First let us show that

    = [    ;   - ],

First, we know that _i,k = a_i+k for 0≤ i≤ r and 0≤ k≤ n-r-1. For the matrix , _j,k = 0 if j<k and _j,k = θ_k-j if k≤ j. And for the matrix , _i,k = 0 if k>i and _i,k = θ_i-k if k≤ i. 
Thus 

    ()_i,j = ∑_k=0^iθ_i-k[∑_l=0^j a_k+lθ_j-l],    0≤ i≤ r, 0≤ j≤ n-r-1.



We are now going to look at three different cases:


  * Suppose that i≤ u, Since a_0 = a_1 = ⋯ =a_u-1 = 0, then

    ()_i,j = ∑_k=0^iθ_i-k[∑_l=u-k^j a_k+lθ_j-l],    0≤ i≤ r, 0≤ j≤ n-r-1.

After a change of variable

    ()_i,j = ∑_k=0^iθ_i-k[∑_l=0^j-u+k a_u+lθ_j-u+k-l],    0≤ i≤ r, 0≤ j≤ n-r-1.

By the recurrence relation on the θ_i's, we know that

    ∑_l=0^j-u+k a_u+lθ_j-u+k-l =
    
     1,     if   j-u+k = 0
    
    0,     otherwise

And thus

    ()_i,j =
    θ_i+j-u ,     if  0≤ u-j≤ i 
    
    0,     otherwise


  * Now, suppose that i>u and j≤ u. Since, j≤ u, then we can use the expression

    ()_i,j = ∑_l=0^j θ_j-l[∑_k=0^i a_k+lθ_i-k],    0≤ i≤ r, 0≤ j≤ n-r-1.

We use the same transformation as before to get

    ()_i,j = ∑_l=0^jθ_j-l[∑_k=0^i-u+l a_u+kθ_i-u+l-k],    0≤ i≤ r, 0≤ j≤ n-r-1.

and

    ∑_k=0^i-u+l a_u+kθ_i-u+l-k =
    
     1,     if   i-u+l = 0
    
    0,     otherwise

Since u < i, then the first case is never possible, therefore ()_i,j is always zero.

  * Finally, suppose that If i>u and j> u. We have 

    ()_i,j    = ∑_l=0^j θ_j-l[∑_k=0^i a_k+lθ_i-k] 
        = ()_i,u + ∑_l=u+1^j θ_j-l[∑_k=0^i  a_k+lθ_i-k] 
        = ∑_l=u+1^j θ_j-l[∑_k=u-l^i  a_k+lθ_i-k -∑_k=u-l^-1  a_k+lθ_i-k]

The last equality contains the subtraction because by starting k with u-l, we have some negative value for the index k, so we have to remove them. 
Finally, we have

    ()_i,j   = -∑_l=u+1^j θ_j-l∑_k=u-l^-1  a_k+lθ_i-k
        = -∑_k=u-j^-1θ_i-k∑_l=u-k^j a_k+lθ_j-l
        = -∑_k=u-j^-1θ_i-k∑_l=0^j-u+k a_u+lθ_j-u+k-l

By the recurrence relation on the θ_i's, we have

    ()_i,j = -θ_i+j-u.



For the bijection, suppose that  and ' both give the same θ_i's, then = ', but since  and  are invertible, then = '. We have an injection between two sets of the same size, therefore it is a bijection. 



Suppose that  is the matrix corresponding to the sequence ∈𝒜_u, and it corresponds to the ,,,, then the last row of  is a linear combination of its other rows if and only if the last row of  is a linear combination of its other rows.


We know that 

    =  ^-1[    ;   - ]

Thus if (ł_0,⋯,ł_r-1,1) =, then 

    (ł_0,⋯,ł_r-1,1)^-1[    ;   - ] =

Therefore, there is some non-zero μ_r with,

    (μ_0,⋯,μ_r-1,μ_r)[    ;   - ] = .

Since μ_r≠ 0, then the last row of  is a linear combination of its previous row. The converse can be proven by going backward.



Define B(n,r,u) to be the set of non-zero sequences  of length n with linear complexity r at most such that u is the smallest index i such that a_i is non-zero. We also define B(n,r) to be the set of all sequences  of length n with linear complexity at most r. Therefore B(n,r) = (∪_u=0^n-1 B(n,r,u))∪{}. We set b(n,r,u) = ♯ B(n,r,u) and b(n,r) = ♯ B(n,r).


Now, suppose that r+1≤ n-r. If u<r, then we use the above method for reduction. Otherwise if u≥ r, then the first r elements of  are 0 an therefore we can only get the zero sequence. 

Next, if n-r≤ r, then again we use the above reduction method for u<n-r-1. If r>u≥ n-r-1, then for any choice of the remaining coefficients a_u+1,⋯, a_n-1, it is always possible to generate it using a LFSR of length r. If u≥ r, then there is no LFSR of order at most r which can generate the sequence.

These, together with Lemmas <ref> and <ref> allow us to get the next theorem.


 


  *  If r+1≤ n-r and u≥ r, then b(n,r,u) = 0.

  *  If n-r≤ r and r>u≥ n-r-1, then b(n,r,u) = q^n-u-1(q-1).

  * If n-r≤ r and u≥ r, then b(n,r,u) = 0.

  *  If r+1≤ n-r and u<r, or n-r≤ r and u<n-r-1 then b(n,r,u) = 
q^u+1(q-1)b(n-2u-2,r-u-1).



Lemma <ref> tells us all elements of B(n,r) can be generated by a LFSR of order r. Hence, we study only matrices in the form of . For (<ref>), one can just write down the matrix  and see that it has a triangular shape where the last row is never a linear combination of the previous row. For (<ref>), we again look at the form of the matrix , we will see that some first non-zero rows of  make an invertible matrix and thus the last row is always a linear combination of the rows of that invertible matrix whatever the choice of the coefficients we choose after a_u. For (<ref>), looking at the form of the matrix will also give the result. For (<ref>), we use the bijection in Lemma <ref> and Lemma <ref>.


Summing all the possibilities in Theorem <ref>, we get the following corollaries.


Given two integers r≤ n, the number of finite sequence of length n with linear complexity at most r is equal to 


  * If r=0, b(n,0) = 1.

  * If r+1≤ n-r,

    b(n,r) = 1+∑_u=0^r-1 q^u+1(q-1)b(n-2u-2,r-u-1).


  * If n-r≤ r,

    b(n,r) = 1+∑_u=0^n-r-2 q^u+1(q-1)b(n-2u-2,r-u-1)+∑_u=n-r-1^r-1(q-1)q^n-u-1.





Given two integers r≤ n, the number of finite sequences of length n with linear complexity at most r is equal to 1 if r=0 and if 0<r≤ n,

    b(n,r) = 1-q+ q^2 b(n-2,r-1).



Suppose that r+1≤ n-r. Then,

    b(n,r)    = 1+∑_u=0^r-1 q^u+1(q-1)b(n-2u-2,r-u-1)
       = 1 + q(q-1) b(n-2,r-1) + ∑_u=1^r-1 q^u+1(q-1)b(n-2u-2,r-u-1)
       = 1 + q(q-1) b(n-2,r-1) + q ∑_u=0^r-2 q^u+1(q-1)b(n-2u-4,r-u-2)
       = 1 + q(q-1) b(n-2,r-1) + q b(n-2,r-1) -q
       = 1-q+ q^2 b(n-2,r-1)


Now suppose that n-r≤ r. Then,


    b(n,r)    = 1 +∑_u=n-r-1^r-1(q-1)q^n-u-1
          + ∑_u=0^n-r-2 q^u+1(q-1)b(n-2u-2,r-u-1)
       = 1 + ∑_u=n-r-1^r-1(q-1)q^n-u-1 + q(q-1)b(n-2,r-1) 
          + q∑_u=1^n-r-2 q^u(q-1)b(n-2u-2,r-u-1)
       = 1 + ∑_u=n-r-1^r-1(q-1)q^n-u-1 + q(q-1)b(n-2,r-1) 
          + q∑_u=0^n-r-3 q^u+1(q-1)b(n-2u-4,r-u-2)
       = 1 + ∑_u=n-r-1^r-1(q-1)q^n-u-1 + q(q-1)b(n-2,r-1)
          + q[ b(n-2,r-1)-1-∑_u=n-r-2^r-2(q-1)q^n-u-3]
       = 1-q +q^2b(n-2,r-1)+∑_u=n-r-1^r-1(q-1)q^n-u-1
          -q∑_u=n-r-2^r-2(q-1)q^n-u-3
       =  1-q +q^2b(n-2,r-1) 
          + (q-1)[ ∑_u=n-r-1^r-1q^n-u-1 -∑_u=n-r-2^r-2q^n-u-2]
       = 1-q +q^2b(n-2,r-1)  
          +(q-1) [ ∑_u=n-r-1^r-1q^n-u-1 -∑_u=n-r-1^r-1q^n-u-1]
       = 1-q +q^2b(n-2,r-1)



As a consequence of the corollaries, we get the following theorem.


Given two integers r≤ n, the number of finite sequences of length n with linear complexity at most r is


  * If r=0, b(n,0) = 1.

  * If r+1≤ n-r,

    b(n,r) = q^2r+1+1/q+1


  * If n-r≤ r,

    b(n,r) = 1-q^2(n-r)/1+q+q^n.




Suppose that r+1≤ n-r. From the previous corollary,

    ∑_i=0^r-1 q^2i b(n-2i,r-i) = (1-q)∑_i=0^r-1 q^2i + ∑_i=0^r-1 q^2(i+1)b(n-2(i+1),r-(i+1)).

Thus

    ∑_i=0^r-1 q^2i b(n-2i,r-i) = (1-q)∑_i=0^r-1 q^2i +∑_i=1^rq^2i b(n-2i,r-i)

Therefore,

    b(n,r) = (1-q)∑_i=0^r-1 q^2i+q^2r = q^2r+1-q^2r/1+q

And we get the result.

If n-r≤ r, then r≥n/2. So using this,


    ∑_i=0^n-r-1 q^2i b(n-2i,r-i) = (1-q)∑_i=0^n-r-1 q^2i + ∑_i=0^n-r-1 q^2(i+1)b(n-2(i+1),r-(i+1))

Therefore

    b(n,r) =(1-q)∑_i=0^n-r-1 q^2i + q^2(n-r)b(2r-n,2r-n),

Since B(2r-n,2r-n) = ^2r-n, then

    b(n,r) =(1-q)1-q^2(n-r)/1-q^2 + q^n

And we get our result.



Using the previous theorem, we can compute the number of finite sequence with a fixed linear complexity.


Let r≤ n be positive integers. Then, the number of sequences of length n and linear complexity r over a finite field  of size q is 

    1     if  r=0,
    
    q^2r-1(q-1)      if  r≤⌊n/2⌋ ,
    
    q^2(n-r)(q-1)     if  r>  ⌊n/2⌋.



The case r=0 is clear. For r=1, we get that the number of sequences of length n and linear complexity r over a finite field  of size q is

    q^3-q/q+1 = q(q-1).


Now, suppose that r=⌈n/2⌉. Then the number we want is given by

    q^n-q^2(n-r)+q^2r-1/q+1 =
    q^2r-1(q-1)    if  n  is even
    
    q^2(n-r)(q-1)    if  n  is odd

It is easy to check that if r≤⌈n/2⌉ -1, then the number is

    q^2r-1(q-1),

and if ⌈n/2⌉ +1, the number is

    q^2(n-r)(q-1).

Furthermore { r≤⌈n/2⌉ -1} and { r=⌈n/2⌉, n  even} are the same as { r≤⌊n/2⌋. Finally { r≥⌈n/2⌉ +1} and { r=⌈n/2⌉, n  odd} are the same as { r> ⌊n/2⌋.


Since we also know the size of balls with respect to the linear complexity from Theorem <ref>, we can give a formula for the Sphere packing bound.


Let S be a set of sequences of length n and with minimum distance d. Then

    ♯ S≤q^n(q+1)/q^2⌊d-1/2⌋+1   if  2⌊d-1/2⌋≤ n-1, 
    q^n(q+1)/1-q^2(n-⌊d-1/2⌋)+(1+q)q^n   if  2⌊d-1/2⌋> n-1.



This is a direct consequence of Theorem <ref> and using the fact that the union of the spheres of radius ⌊d-1/2⌋ centered at the sequences in S is a disjoint union.




§ CONCLUSION AND FUTURE WORK

We have seen how the notion of weight of vectors can be extended to the notion of linear complexity of finite sequences. Using the new metric defined by the linear complexity, we developed a coding theory for finite sequences. We gave the Singleton bound and we presented a construction for an optimal set of sequences reaching this bound. Then we computed an exact formula for the number of finite sequences which can be generated by a LFSR of a fixed order. 

LFSR have been extensively studied <cit.>. It is widely used in the generation of random secret key in symmetric cryptography. Our main goal however is to use the LFSR and linear complexity to get a new protocols for asymmetric public key cryptography. 

In 1978, McEliece proposed a new cryptosystem using linear codes (Goppa codes) and Hamming metric <cit.>. After 40 years of cryptanalysis, the cryptosystem is still considered to be generally secure. However, the cryptosystem requires the use of public keys with large size. This makes it impractical for daily use. The advantage of using linear codes is that cryptosystem based on them are in general safe against the quantum computers. Namely, there is no general algorithm which can decode a random linear code in polynomial time.

The strength of the McEliece cryptosystem is that the Goppa codes look like random linear codes and it is considered to be a difficult problem to decode a random linear code. 
To solve the problem with the key size, it was suggested to use different family of linear codes. For instance, Niederreiter proposed a new cryptosystem using Reed-Solomon codes <cit.>. However, cryptosystems using Reed-Solomon codes were proven to be insecure <cit.>. Several types of codes were suggested to get a secure cryptosystem. Another suggestion was that, instead of using the classical Hamming metric on the linear code, one use the rank metric. For instance, a new cryptosystem based on the Gabidulin codes were proposed <cit.>. This system was still proven to be insecure <cit.>. 

Recently, this increased the interest in the search of linear codes with good properties which can be used in cryptography both in Hamming and rank metric. There is another cryptosystem which are also using a set and a metric on the set. The lattice based cryptosystem  is the scheme where the metric is the Euclidean distance <cit.>. This particular cryptosystem is also resistant against attacks from quantum computers.

Motivated by all of this, we may think of a cryptosystem using the linear complexity as metric. We are working in this direction using the metric from linear complexity and this will be part of a future publication. Finally we all know what Hamming metric codes are good for error correcting in a q-ary symmetric channel. For rank metric codes, they have good application in network coding <cit.>. It is our hope that the presented coding framework will also be of use for some particular channel.
 


§ AKNOWLEDGEMENT


I would like to thank Prof. Joachim Rosenthal for his valuable comments and suggestions on this work. 
 







