Linear Feedback Shift Registers and Cyclic Codes in SAGE

Timothy Brian Brock 1


Date: April 24, 2006

Introduction

Thesis

This paper will discuss the history of linear feedback shift registers (LFSR) in cryptographic applications and will attempt to implement an algorithm in SAGE [11] and Python (www.python.org) to create a linear feedback shift register sequence (LFSR sequence) in cryptography. Also, this paper will attempt to implement the Berlekamp Iterative Algorithm in SAGE and Python. This algorithm will be able to use the Linear Feedback Shift Register sequence generated by the first algorithm to find the sequence's connection polynomial.

I will attempt to show that the connection polynomial of a given LFSR sequence is the reverse of a generator polynomial of the cyclic code of length $ p$, where $ p$ is also the period of the LFSR sequence. This will provide a connection between cyclic error-correcting codes and LFSR sequences.

Background on Linear Feedback Shift Registers

A linear feedback shift register can be easily implemented in hardware or software and is used to create a pseudo-random sequence of numbers for many different applications. These applications include uses in consumer electronics, such as cellphones and digital cable [2]; multiple access and polling techniques; secure and privacy communications; error detecting and correcting codes; and cryptographic systems [1].

In consumer electronics, a Linear Feedback Shift Register can be used as a counter [2]. When used in this manner, LFSRs are desirable because they perform the function with less resources and usually much faster than the conventional counters, such as binary counters or Gray Code counters. Though it goes against intuition, LFSRs can also be used to generate pseudo-noise which is used by such consumer electronics as cellphones and digital cable to increase the reliability of the signal [2]. LFSR can also be used in spread spectrum systems [2]. A spread spectrum system utilizes the entire bandwidth a signal may use to send information by spreading the data frequency over many frequencies in the bandwidth. The next frequency to be utilized is determined by the LFSR sequence. Other more common applications of a LFSR is the use in white noise machines (such as the one shown below) and music synthesizers.

\includegraphics[% scale=0.5]{180px-Digital-clock-radio-premium.eps}

Another application of LFSRs is the creation of pseudo-random sequences that can be used in cryptography. According to the Merriam-Webster Dictionary, cryptography is the enciphering and deciphering of messages in secret code or cipher. The LFSR sequence is a pseudo-random number sequence that can be applied to a message as a cipher, a cipher is the system used to create a secret message. Throughout this paper, the cipher will be a sequence of binary terms that is added to the binary message to provide the encoded message, also known as the ciphertext. The cipher encodes the message so that only someone with the key knows the proper way to decode the message and is then able to read the message, anyone without the key receives the ciphertext and reads only nonsense. The key is a piece of information that allows a user to determine the specific cipher used in encrypting the message. In digital communication, the enciphering of a message with a LFSR sequence is the same as adding in pseudo-random noise. The proper recipient with a key removes the noise from the message, but a third party without the key interprets the message only as noise.

How to Create a LFSR Sequence

A linear feedback shift register sequence is a pseudo-random sequence of numbers that is often created in a hardware implementation of a linear feedback shift register. A LFSR is ``an algorithm which yields a sequence of numbers which is eventually periodic'' [9]. When a LFSR is implemented in hardware, a LFSR sequence is recursively generated by taking the output from the last ``stage'' of a given LFSR to compute the next ``stage.'' An example of a LFSR implemented in hardware is included in Figure 1 (from Massey [4]). This LFSR is of length $ L$, and each state cell's current state is used as the input to the mod 2 adder. This adder is implemented in hardware with an exclusive-or function. Since this is a shift register, each iteration of the register causes the state of each state cell to shift to the next cell (in this case, to the right). We use the output of the last state cell to provide the next term of the sequence after each iteration.

\includegraphics[% scale=0.3]{Figure1.eps}

This hardware LFSR can be modeled mathematically to generate a LFSR sequence. In order to build this sequence, three pieces of information are needed. They are the key, the initial fill, and an algorithm to obtain the next term of the sequence. In the hardware implementation, the connections between the state cells and the mod 2 adder determines how the outputs of the cells are used as inputs to the mod 2 adder. In the same way, the key determines how the previous terms of the LFSR sequence are used to compute the next term in the sequence. The key may be represented as a vector $ \mathbf{c}=[c_{1},c_{2},...,c_{L}]$, but is more often defined by a polynomial, known as the connection polynomial

$\displaystyle C(x) = 1+c_{1}\cdot x+c_{2}\cdot x^{2}+...+c_{L}\cdot x^{L}.$ (1)

The coefficients $ c_{i}$'s can also be considered the key. In figure 1, the coefficients described which cells were used as inputs to the modulo 2 adder. The degree of the polynomial also describes how many cells (or bits) are needed to create the minimal linear feedback shift register that will generate the given LFSR sequence [3].

According to Massey [4], the initial fill is the initial values of the state cells, $ s_{0},s_{1},s_{2},...,s_{L-1}$ the initial contents of the $ L$ stages of Figure 1 above. In general, the LFSR sequence is defined by the following recursion relation

$\displaystyle s_{j}=\sum_{i=1}^{L}c_{i}\cdot s_{j-i}\mod 2,$ (2)

for $ j \geq L$.

Example 1   If we are given the key as a vector $ \mathbf{c}=[1,0,0,1]$ and the initial fill as a vector $ \mathbf{s}=[1,1,0,1]$ in the finite field $ GF(2)$, we can create the sequence $ 1,1,0,1,0,1,1,0,0,1,0,0,0,1,1,1,1,...$ Note that the first four terms of the sequence are the same as the terms given to us by the vector $ \mathbf{s}$ (namely $ s_{0}=1,s_{1}=1,s_{2}=0,s_{3}=1$). The next term ($ s_{4}$) is found by using the recursion function to give

$\displaystyle \begin{array}{ll} s_{4}=\sum_{i=1}^{4}c_{i}\cdot s_{4-i}&=c_{1}\c... ...dot s_{1}+c_{4}\cdot s_{0}\\ &=1\cdot1+0\cdot0+0\cdot1+1\cdot1=0. \end{array} $

We know that $ L=4$ since the length of vectors $ \mathbf{c}$ and $ \mathbf{s}$ is 4 and $ s_{4}=0$. This process can be easily automated and a function has been written for SAGE which will quickly generate terms of a LFSR sequence of any length defined by the user (see the appendix below). The inputs for this function are two vectors representing the key and the initial fill and an integer $ n > L$ representing the desired number of terms in the output.

Linear Feedback Shift Registers in Cryptography

Four Tenets of Security

Imagine that Alice and Bob are sending messages back and forth to one another. If the content of these messages was not very secret and Alice and Bob did not care if anyone else read the message, they would not bother with any kind of encryption. Then, if a third person, say Charlie, intercepts the message he can read it without any difficulty. If, on the other hand, Alice and Bob were exchanging information they wanted to keep secret, they would need to employ some kind of encryption system to encode their messages. Depending upon the type of encryption they employ, Alice and Bob would receive a certain level of security against the actions of third parties.

No matter what type of encryption Alice and Bob use, there will be several objectives that Alice and Bob want the encryption method to achieve. Out of a long list objectives, there are four that form a framework upon which all the others are built [5]. The four security objectives that would apply to this message include:

  1. Secrecy: This objective ensures that the information is available only to those people who are authorized to have it.
  2. Integrity: This ensures that no third party can make unauthorized alterations to the data.
  3. Authentication: Authentication is related to identification. Two parties that are communicating with each other need to be able to identify one another and the receiver can be sure that the person sending the information is who the receiver thinks it is.
  4. Non-repudiation: This prevents the sender of information from denying that they sent that information. This also allows the receiver to prove to a third party that the information was sent by the sender [5].
Sometimes, these four basic objectives are reduced to just three, Privacy, Signature, and Integrity [6]. Privacy is a synonym for secrecy and signature is the same as non-repudiation. This three objective list seems incomplete and we will continue to use the four objectives discussed earlier. The LFSR sequences that we will be studying can be applied to a message as a stream cipher that encrypts the message. This encryption method then tries to meet the above four security objectives.

A LFSR sequence stream cipher achieves secrecy by adding the sequence to the binary representation of the message. The sequence appears as added noise to the message and anyone who intercepts the message would be unable to read the information due to the added sequence. The problem with relying on LSFR sequences for secrecy is the minimal connection polynomial of the sequence is easily determined using the Berlekamp-Massey Algorithm, which is discussed later. The minimal connection polynomial is the key necessary to generate the LFSR sequence used as the stream cipher. With this key, Charlie can easily add the sequence to the ciphertext to retrieve the original message. One method Alice and Bob can use to have more secrecy in the stream cipher is by picking LFSR sequences with extremely long periods (i.e. period length $ p =10^50$). With long period lengths, Charlie needs a longer amount of time to find the minimal connection polynomial and he needs more terms of the sequence to determine the correct polynomial.

As presented in this paper, LFSR sequences combined with some error-correcting codes can provide a limited amount of integrity. While this would be most useful against the attacks of noise in the transmission lines, if Charlie was desperate enough to attempt to try to flip random bits in the hopes of changing the message, the error-correcting code may provide some protection against this by correcting the errors intentionally made to the message. The actual amount of protection provided by this, however, is almost negligible since the error-correcting codes can only correct a limited number of errors and a malicious attack would probably be able to overwhelm the capabilities of an error-correcting code very easily. On its own, a LFSR sequence provides very little integrity.

In order to provide for authentication, Alice and Bob could each create their own stream cipher using a different LFSR sequence. Alice would then send her key and initial fill to Bob and Bob would send his key and initial fill to Alice. Alice would then add together her sequence and Bob's sequence to obtain a new sequence. She would use this sequence as the stream cipher and encode her message to send to Bob. Bob would also add together the two sequences to obtain the same stream cipher. This would allow Alice and Bob to verify that they are talking with each other since they created their stream cipher by adding their own individual sequences.

Pseudo-random Binary Sequences

A stream cipher is a sequence of binary digits called a cryptographic bit-stream [7]. The stream cipher is then added to the message to create a ciphertext (encryption) and can be added to the ciphertext to obtain the original message (decryption). One type of stream cipher that is used to create ciphertexts is pseudo-random binary sequences. Linear feedback shift register sequences are one type of pseudo-random binary sequence that are easily generated by linear feedback shift registers.

Ideally, a sequence would have infinite length and could achieve complete randomness. The reality of practical application and construction techniques necessitates the use of only finite sequences. Since finite sequences can never be truly random, there are certain properties singled out that are associated with randomness. Golomb states these properties are:

  1. The number of 1's is approximately equal to the number of 0's.
  2. The runs of consecutive 1's or 0's frequently occur with short runs more frequent than long runs.
  3. The sequence possesses an auto-correlation function, which is peaked in the middle and tapering off rapidly at the ends. [1]
The auto-correlation function is a way to quantize how random a sequence is and is defined by

$\displaystyle AC(k) = \dfrac{1}{p}\sum_{i=1}^{p}x_i\cdot x_{i+k}$

where $ p$ is the period of the sequence $ \{x_i\}$and when $ 0<k<p$, $ AC(k)$ is close to zero (meaning there is very little correlation of the sequence with itself) and $ AC(k)=\dfrac{1}{2}$ when $ k=0$, indicating that the number of 1's is equal to the number of 0's.

Any sequence that has these three properties is considered to be pseudo-random. We find that linear feedback shift register sequences fulfill the above three properties and are pseudo-random. Linear Feedback Shift Registers are also easy to use as stream ciphers since adding the LFSR sequence to the message encodes it and adding the sequence again to the ciphertext returns the original message [9].

Example 2   I would now like to provide an example of how a message might be encrpypted for secrecy and then decrypted by the authorized receiver so that the information can be read. In order for Alice and Bob to send messages to each other using computers, they must convert the english syntax of the message into a binary form. For our purposes we will allow the following table define our alphabet.

$\displaystyle \begin{array}{llllll} SPACE &= &0000 &L &= &1111\\ A &= &0001 &!... ... &, &= &1100 \\ T &= &0110 &. &= &1101 \\ Y &= &0111 &Q &= &1110 \end{array} $

Suppose Alice wanted to send the message $ M =$``BEAT ARMY!'' to Bob, but she wanted to keep it secret. By converting ``BEAT ARMY!'' from english to binary, we have a string of binary bits

$\displaystyle M = 0010001100010110000000010101010001111000$

In order to generate a stream cipher that only Alice and Bob know, each person will generate a pseudo-random sequence of sufficient length. Alice will send her sequence to Bob and Bob will send his sequence to Alice. The two people will then add their sequences together bit-wise to produce a common stream cipher. For our purposes, suppose the resultant sequence from the two individual sequences is

$\displaystyle C = 1101011001000111101011001000111101011001$

Alice now has a message in binary format and a cipher to encode the message. Adding the cipher to the message, Alice gets the encrypted message or ciphertext, $ E$.

$\displaystyle \begin{array}{llll} & 0010001100010110000000010101010001111000 & ... ... + &\underline{C}\\ & 1111010101010001101011011101101100100001 & &E\end{array}$

If a third party, Charlie, were to intercept the ciphertext and tried to read it, knowing that the computers used the above table to talk to one another, he would decrypt the ciphertext as ``LRRA?..;BA''. Notice that both `A's in the original message where changed to two different letters (`R' the first time and `.' the second time) and that `E' and `A' both are changed to `R' and `T' and `!' are both changed to `A'. This helps prevent a cryptanalyst from breaking the code by mapping each character to something different everytime. The mapping appears random since the stream cipher used was a pseudo-random sequence.

When Bob receives the ciphertext, however, he is able to decrypt it since he has the stream cipher that he and Alice created earlier. By adding the stream cipher to the ciphertext, he will uncover the original message.

$\displaystyle \begin{array}{llll} & 1111010101010001101011011101101100100001 & ... ...+ &\underline{C} \\ & 0010001100010110000000010101010001111000 & &M\end{array}$

Now Bob can use the table to decode the message from binary into english and receives ``BEAT ARMY!'' from Alice.

Connection With Cyclic Codes

Background

We recall some background definitions from McGowan [12]

Definition 1   A linear code $ C$ of length $ n$ is a cyclic code if whenever $ \mathbf{c}=(c_1,...,c_n)$ is a codeword then so is its cyclic shift $ \mathbf{c'}=(c_2,...,c_n,c_1)$.

Cyclic codewords are conveniently represented as polynomials modulo $ x^n-1$. In fact, if $ \mathbf{c}=(c_1,...,c_n)$ then let

$\displaystyle c(x)=c_1+c_2x+...+c_nx^{n-1} $

denote the associated codeword polynomial. In this notation the cyclic shift $ \mathbf{c'}=(c_2,...,c_n,c_1)$ of $ \mathbf{c}$ corresponds to the polynomial $ xc(x)\pmod{x^n-1}$. In other words cyclic shifts correspond to multiplication by $ x$. Since cyclic shifts leave cyclic codes invariant, multiplication by any power of $ x$ modulo $ x^n-1$ corresponds to a codeword in $ C$. Since $ C$ is a linear code, the sum of any two such codeword polynomials is another codeword polynomial. Therefore, in fact, the product of any codeword polynomial times any polynomial in $ x$ modulo $ x^n-1$ is another codeword polynomial.

Denote by $ R_n$ the ring of polynomials with coefficients in $ \mathbb{F}$ modulo $ x^n-1$:

$\displaystyle R_n=\mathbb{F}[x]/(x^n-1).$ (3)

Define an ideal $ I$ of $ R_n$ to be any subset of $ R_n$ closed under addition and multiplication by an arbitrary element of $ R_n$: In other words an ideal in $ R_n$ is simply a subset closed under addition and multiplication by an arbitrary polynomial modulo $ x^n-1$. In particular, the collection of codeword polynomials associated to a cyclic code is an ideal of $ R_n$.

Lemma 1   There is natural one-to-one correspondence between cyclic codes of length $ n$ over $ \mathbb{F}$ and ideals of $ R_n$.

This can be found in any book on coding theory, for example MacWilliams and Sloane [13].

In fact GUAVA allows you to easily pass back and forth between codewords as vectors and codewords as polynomials.

In order to define the generator polynomial of a cyclic code we need the following mathematical fact.

Lemma 2   Every ideal $ I$ of $ R_n$ is of the form $ g(x)R_n$. In other words every element of $ I$ is a multiple of $ g(x)$ for some polynomial $ g(x)$ in $ R_n$.

Ideals which are of the form $ I=g(x)R_n$ are called principal ideals and $ g(x)$ is called a generator of the ideal $ I$.

proof: Suppose not. Let $ s(x)$ be a non-zero element in $ I$ of smallest degree. Pick an arbitrary non-zero element $ f(x)$ in $ I$. By the division algorithm, we can write $ f(x)=q(x)s(x)+r(x)$ where $ q$ and $ r$ are polynomials and the degree of $ r(x)$ is strictly less than the degree of $ s(x)$. Notice that $ r(x)=f(x)-q(x)s(x)$ belongs to $ I$ by definition. This contradicts the assumption that $ s(x)$ has smallest degree unless $ r(x)=0$. Therefore every element of $ I$ is a multiple of $ s(x)$. Take $ g(x)=s(x)$. $ \Box$

Definition 2   Let $ C$ be a cyclic code of length $ n$. Let $ I$ be the ideal corresponding to $ C$ by Lemma 1. We call $ g(x)$ a generator polynomial of $ C$ if it is a generator of $ I$.

It is also necessary to define what the check polynomial of a cyclic code is.

Definition 3   Let $ C$ be a cyclic code of length $ n$ and $ g(x)$ be the generator polynomial of $ C$. The check polynomial is some $ h(x)$ such that

$\displaystyle x^n-1=g(x)\cdot h(x)$

.

The check polynomial is used to determine whether or not a codeword belongs to $ C$.

Connection Polynomial and Generator Polynomial

In section 1.3, it was shown that LFSR sequences can be described with two vectors and a recursive relation. Another way to describe the LFSR sequence is using a polynomial. The connection polynomial, $ C(x)=1+c_{1}\cdot x+c_{2}\cdot x^{2}+...+c_{L}\cdot x^{L}$, describes the LFSR sequence

As recalled above, a cyclic code can also be described by a polynomial, namely the generator polynomial. In practice, a cyclic code can be generated by a shift register for actual application in communication and computers [8]. This statement implies that LFSR sequences are in some way connected to cyclic codes. Before I show the connection with cyclic codes, however, I will define the reverse of a polynomial.

Definition 4   Let $ f(x) = f_1+f_2\cdot x +...+f_n\cdot x^{n-1}$ be a polynomial such that $ f_1,f_2,...,f_n\in GF(2)$. The reverse of $ f(x)$ is $ f^*(x) = f_n + f_{n-1}\cdot x +...+f_1\cdot x^{n-1}$.

Proposition 1   The connection polynomial defining a LFSR sequence is the reverse of a check polynomial for a cyclic code of length $ p$, where $ p$ is the period of the LFSR sequence.

proof: Let $ A$ be a cyclic $ [n,k]$ code over $ \mathbb{F}=GF(q)$. Let $ g(x)=g_0+g_1\cdot x+...+g_{n-k}\cdot x^{n-k}$ be the generator polynomial and $ h(x)=h_0+h_1\cdot x+...+h_k\cdot x^k$ be the check polynomial. The code $ A$ has check matrix:

\begin{displaymath}H = \left( \begin{array}{ccccccc} h_k & h_{k-1} & ... & h_0 ... ...\\ 0 & ... & 0 & h_k & h_{k-1} & ... & h_0 \end{array}\right) \end{displaymath}

This is an $ (n-k)\times n$ matrix. Assume $ h_0 = 1$. If $ \mathbf{a}=(a_1,...,a_n)\in A$ then $ H\cdot \mathbf{a} = \mathbf{0}$. So $ \mathbf{a}\cdot\mathbf{H_1} = 0$ ( $ \mathbf{H_1}=$ top row of $ H$). This means

$\displaystyle a_1\cdot h_k + a_2\cdot h_{k-1}+...+a_{k+1}\cdot h_0 +a_{k+2}\cdot 0 +...+a_n\cdot 0 = 0$

So

$\displaystyle a_{k+1} = -a_1\cdot h_k - a_2\cdot h_{k-1} -...-c_k\cdot h_1$ (4)

Let $ (a_1,...,a_k)$ denote the ``information bits'' or ``message coordinates'' to be encoded. To find the ``check bits'' $ a_{k+1},...,a_n$, use 4 to get $ a_{k+1}$, use $ a_{k+2}=-a_2\cdot h_k -...-a_{k+1}\cdot h_1$, which is the second row of $ H$, to find $ a_{k+2}$, use $ a_{k+i}=-a_i\cdot h_k -...- a_{k+i-1}\cdot h_i, 1\leq i \leq n-k$, the $ i^{th}$ row of $ H$, to find $ a_{k+i}$. In general, $ a_{k+1},a_{k+2},...,a_{k+i}=s_1,s_2,...,s_i$. Then, the recursive relation

$\displaystyle s_{n+1}=-s_n\cdot h_1 -s_{n-1}\cdot h_2 -...-s_{n-k+1}\cdot h_k$

defines a LFSR sequence. From the definitions 1, 2, 4, it follows $ C(x) = -h^*(x)$, where $ h$ is the above check polynomial. Since we are over $ GF(2)$, this is the same as $ C(x) = h^*(x)$, as claimed. $ \Box$

Rational Functions

The basic idea behind decoding a LFSR sequence is to find the key. The generator function of the LFSR sequence $ \{ s_{i}\}$ is a power series

$\displaystyle g(x)=\sum_{i=0}^{\infty}s_{i}\cdot x^{i}$

Since $ \{ s_{i}\}$ is a periodic sequence, this power series is actually a rational function. This subsection explains this fact in more detail.

It is a well known theorem that a real number is rational if and only if its sequence of decimal digits is eventually periodic [10]. The analog for this theorem for a power series is the following result.

Lemma 3   Let $ a_{i}\in GF(q)$ for $ i\geq0$. The series

$\displaystyle f(x)=\sum_{i=0}^{\infty}a_{i}\cdot x^{i}$

is rational if and only if the sequence of coefficients is eventually periodic.

proof: Suppose that $ a_{i+P}=a_{i}$ for $ i>i_{0}$. Then

$\displaystyle \sum_{i=i_{0}+1}^{\infty}a_{i}\cdot x^{i}=x^{i_{0}+1}\cdot\sum_{j... ...t\sum_{j=0}^{\infty}x^{j\cdot P}\sum_{i=0}^{P-1}a_{i_{0}+i+j\cdot P}\cdot x^{i}$

By geometric series, this is a rational function $ \Box$.

This lemma immediately implies the following result.

Proposition 2   If $ \{s_i\}$ is a LFSR sequence then its connection polynomial is a rational function.

How to Find the Connection Polynomial

Recovering the Connection Polynomial from a LFSR Sequence

In some cases, it is necessary to recover the connection polynomial of a LFSR sequence from the sequence. This is true when attempting to do cryptanalysis on a piece of intercepted code. When a part of the stream cipher is intercepted, the connection polynomial can be recovered even if the number of terms of the cipher is less than the period of the sequence. Once this polynomial is known, the entire cipher can be generated and any messages that are encrypted using that particular sequence as a stream cipher can be decrypted and read by the third party.

Berlekamp-Massey Algorithm

An algorithm exists that readily provides a connection polynomial given only a few terms of a LFSR sequence. This algorithm is known as the Berlekamp-Massey algorithm. In my studies, I have been able to determine the connection polynomial of a LFSR sequence of period 15 with only 8 terms of the sequence. This can be generalized since if we know that a sequence has a minimal connection polynomial with degree $ \leq L$, then only $ 2\cdot L$ terms of the sequence need to be known in order to determine the correct connection polynomial. We can determine $ L$ if we know the period length of the sequence, since the period $ p=2^L-1$ [14]. This is an extremely powerful tool for cryptanalysts trying to break stream ciphers generated from LFSRs, since only a relatively small sample of a long period sequence is needed to break the cipher. The algorithm as it is described by James Massey is presented below [4]:

Input: a LFSR sequence of length $ n$, where $ n$ is even.

Output: a connection polynomial $ C(x)$ of the minimal LFSR.

  1. Initialize the algorithm by setting $ C(x)=1$, $ B(x)=1$, $ m=1$, $ b=1$, $ L=0$, and, $ N=0$.
  2. If $ N=n$, then terminate, otherwise calculate the discrepancy

    $\displaystyle d=s_{N}+\sum_{i=1}^{L}c_{i}\cdot s_{N-i}$

  3. If $ d=0$, then $ m=m+1$, go to step 6.
  4. If $ d\not=0$ and $ 2\cdot L>N$, then calculate $ C(x)=C(x)-d\cdot b^{-1}\cdot x^{m}\cdot B(x)$, $ m=m+1$, go to step 6.
  5. If $ d\not=0$ and $ 2\cdot L\leq N$, then set $ T(x)=C(x)$, calculate $ C(x)=C(x)-d\cdot b^{-1}\cdot x^{m}\cdot B(x)$, $ L=N+1-L$, and set $ m=1$ and $ b=d$, go to step 6.
  6. Calculate $ N=N+1$ and repeat steps 2 through 6.
This algorithm determines whether or not the current connection polynomial $ C(x)$ can correctly produce the next term of the given sequence. If it can, the discrepancy $ d=0$ and the algorithm leaves $ C(x)$ unchanged and iterates to the next step. If $ C(x)$ does not provide the next term of the sequence, the discrepancy $ d\not=0$ and a new $ C(x)$ is calculated as in steps 4 and 5 above.

Though an implementation of this algorithm already exists in SAGE and Python, we believe that it is possible to implement this algorithm more efficiently. It is hoped that a faster implementation will be created for SAGE and Python for this algorithm in this project. This algorithm is analyzed further in [3].

Example 3   The LFSR sequence used in this example: $ 110101100100011$. We take the algorithm all the way out to the termination when $ N=n$. Though this sequence is length $ n=15$, we arrive at the correct connection polynomial $ C(x)$ after only 8 iterations of the algorithm. Iterations 9 through 15 return a discrepancy $ d=0$ which causes the algorithm to return the connection polynomial calculated in the previous iteration.

  1. Step 1: $ C(x)=1,$$ B(x)=1,$ $ m=1,$ $ b=1,$ $ L=0,$ $ N=0\not=15=n$.Step 2: find the discrepancy

    $\displaystyle d=s_{0}+\sum_{i=1}^{0}c_{i}\cdot s_{0-i}=s_{0}=1$

    since $ d\not=0$, we compare $ 2\cdot L$ to $ N$

    $\displaystyle 2\cdot L=2\cdot0=0\leq0=N$

    go to step 5. Step 5: calculate $ C(x)$

    $\displaystyle T(x)=C(x)=1$

    $\displaystyle C(x)=C(x)-d\cdot b^{-1}\cdot x^{m}\cdot B(x)=1-1\cdot1^{-1}\cdot x^{1}\cdot1=1-x$

    $\displaystyle L=N+1-L=0+1-0=1$

    $\displaystyle B(x)=T(x)=1$

    $\displaystyle b=d=1$

    $\displaystyle m=1$

    go to step 6.Step 6: increase $ N$

    $\displaystyle N=N+1=0+1=1$

  2. Step 1: $ C(x)=1-x,$ $ B(x)=1,$ $ m=1,$ $ b=1,$ $ L=1,$ $ N=1\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{1}+\sum_{i=1}^{1}c_{i}\cdot s_{1-i}=s_{1}+c_{1}\cdot s_{0}=1+1\cdot1=0$

    Step 3: since $ d=0$, $ m=m+1=1+1=2$, and we skip to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=1+1=2$

  3. Step 1: $ C(x)=1-x,$ $ B(x)=1,$ $ m=2,$ $ b=1,$ $ L=1,$ $ N=2\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{2}+\sum_{i=1}^{1}c_{i}\cdot s_{2-i}=s_{2}+c_{1}\cdot s_{1}=0+1\cdot1=1$

    since $ d\not=0$, we compare $ 2\cdot L$ and $ N$

    $\displaystyle 2\cdot L=2\cdot1=2\leq2=N$

    go to step 5. Step 5: calculate $ C(x)$

    $\displaystyle T(x)=C(x)=1-x$

    $\displaystyle C(x)=C(x)-d\cdot b^{-1}\cdot x^{m}\cdot B(x)=(1-x)-1\cdot1^{-1}\cdot x^{2}\cdot1=1-x-x^{2}$

    $\displaystyle L=N+1-L=2+1-1=2$

    $\displaystyle B(x)=T(x)=1-x$

    $\displaystyle b=d=1$

    $\displaystyle m=1$

    go to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=2+1=3$

  4. Step 1: $ C(x)=1-x-x^{2},$ $ B(x)=1-x,$ $ m=1,$ $ b=1,$ $ L=2,$ $ N=3\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{3}+\sum_{i=1}^{2}c_{i}\cdot s_{3-i}=s_{3}+c_{1}\cdot s_{2}+c_{2}\cdot s_{1}=1+1\cdot0+1\cdot1=0$

    since $ d=0$, $ m=m+1=1+1=2$, and we skip to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=3+1=4$

  5. Step 1: $ C(x)=1-x-x^{2},$ $ B(x)=1-x,$ $ m=2,$ $ b=1,$ $ L=2,$ $ N=4\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{4}+\sum_{i=1}^{2}c_{i}\cdot s_{4-1}=s_{4}+c_{1}\cdot s_{3}+c_{2}\cdot s_{2}=0+1\cdot1+1\cdot0=1$

    Step 3: since $ d\not=0$, we compare $ 2\cdot L$ and $ N$

    $\displaystyle 2\cdot L=2\cdot2=4\leq4=N$

    go to step 5. Step 5: calculate $ C(x)$

    $\displaystyle T(x)=C(x)=1-x-x^{2}$

    $\displaystyle C(x)=C(x)-d\cdot b^{-1}\cdot x^{m}\cdot B(x)=(1-x-x^{2})-1\cdot1^{-1}\cdot x^{2}\cdot(1-x)=1-x-x^{3}$

    $\displaystyle L=N+1-L=4+1-2=3$

    $\displaystyle B(x)=T(x)=1-x-x^{2}$

    $\displaystyle b=d=1$

    $\displaystyle m=1$

    go to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=4+1=5$

  6. Step 1: $ C(x)=1-x-x^{3},$ $ B(x)=1-x-x^{2},$ $ m=1,$ $ b=1,$ $ L=3,$ $ N=5\not\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{5}+\sum_{i=1}^{3}c_{i}\cdot s_{5-i}=s_{5}+c_{1}\cdot s_{4}+c_{2}\cdot s_{3}+c_{3}\cdot s_{2}=1+1\cdot0+0\cdot1+1\cdot0=1$

    since $ d\not=0$ we compare $ 2\cdot L$ and $ N$

    $\displaystyle 2\cdot L=2\cdot3=6>5=N$

    go to step 4. Step 4: calculate $ C(x)$

    $\displaystyle C(x)=C(x)-d\cdot b^{-1}\cdot x^{m}\cdot B(x)=(1-x-x^{3})-1\cdot1^{-1}\cdot x^{1}\cdot(1-x-x^{2})=1+x^{2}$

    $\displaystyle m=m+1=1+1=2$

    go to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=5+1=6$

  7. Step 1: $ C(x)=1+x^{2},$ $ B(x)=1-x-x^{2}, m=2, b=1, L=3, N=6\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{6}+\sum_{i=1}^{3}c_{i}\cdot s_{6-i}=s_{6}+c_{1}\cdot s_{5}+c_{2}\cdot s_{4}+c_{3}\cdot s_{3}=1+0\cdot1+1\cdot0+0\cdot1=1$

    since $ d\not=0$ we compare $ 2\cdot L$ and $ N$

    $\displaystyle 2\cdot L=2\cdot3=6\leq6=N$

    go to step 5. Step 5: calculate $ C(x)$

    $\displaystyle T(x)=C(x)=1+x^{2}$

    $\displaystyle C(x)=C(x)-d\cdot b^{-1}\cdot x^{m}\cdot B(x)=(1+x^{2})-1\cdot1^{-1}\cdot x^{2}\cdot(1-x-x^{2})=1+x^{3}+x^{4}$

    $\displaystyle L=N+1-L=6+1-3=4$

    $\displaystyle B(x)=T(x)=1+x^{2}$

    $\displaystyle b=d=1$

    $\displaystyle m=1$

    go to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=6+1=7$

  8. Step 1: $ C(x)=1+x^{3}+x^{4}, B(x)=1+x^{2}, m=1, b=1, L=4, N=7\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{7}+\sum_{i=1}^{4}c_{i}\cdot s_{7-i}=s_{7}+c_{1}\cdot s_{6}+c... ...dot s_{5}+c_{3}\cdot s_{4}+c_{4}\cdot s_{3}=0+0\cdot1+0\cdot1+1\cdot0+1\cdot1=1$

    since $ d\not=0$ we compare $ 2\cdot L$ and $ N$

    $\displaystyle 2\cdot L=2\cdot4=6>7=N$

    go to step 4. Step 4: calculate $ C(x)$

    $\displaystyle C(x)=C(x)-d\cdot b^{-1}\cdot x^{m}\cdot B(x)=(1+x^{3}+x^{4})-1\cdot1^{-1}\cdot x^{1}\cdot(1+x^{2})=1-x+x^{4}$

    $\displaystyle m=m+1=1+1=2$

    go to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=7+1=8$

  9. Step 1: $ C(x)=1-x+x^{4},$ $ B(x)=1+x^{2},$ $ m=2,$ $ b=1,$ $ L=4,$ $ N=8\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{8}+\sum_{i=1}^{4}c_{i}\cdot s_{8-i}=s_{8}+c_{1}\cdot s_{7}+c... ...dot s_{6}+c_{3}\cdot s_{5}+c_{4}\cdot s_{4}=0+1\cdot0+0\cdot1+0\cdot1+1\cdot0=0$

    Step 3: since $ d=0$, $ m=m+1=2+1=3$, and we skip to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=8+1=9$

  10. Step 1: $ C(x)=1-x+x^{4},$ $ B(x)=1+x^{2},$ $ m=3,$ $ b=1,$ $ L=4,$ $ N=9\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{9}+\sum_{i=1}^{4}c_{i}\cdot s_{9-i}=s_{9}+c_{1}\cdot s_{8}+c... ...dot s_{7}+c_{3}\cdot s_{6}+c_{4}\cdot s_{5}=1+1\cdot0+0\cdot0+0\cdot1+1\cdot1=0$

    Step 3: since $ d=0$, $ m=m+1=3+1=4$, and we skip to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=9+1=10$

  11. Step 1: $ C(x)=1-x+x^{4},$ $ B(x)=1+x^{2},$ $ m=4,$ $ b=1,$ $ L=4,$ $ N=10\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{10}+\sum_{i=1}^{4}c_{i}\cdot s_{10-i}=s_{10}+c_{1}\cdot s_{9... ...dot s_{8}+c_{3}\cdot s_{7}+c_{4}\cdot s_{6}=0+1\cdot1+0\cdot0+0\cdot0+1\cdot1=0$

    Step 3: since $ d=0$, $ m=m+1=4+1=5$, and we skip to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=10+1=11$

  12. Step 1: $ C(x)=1-x+x^{4},$ $ B(x)=1+x^{2},$ $ m=5,$ $ b=1,$ $ L=4,$ $ N=11\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{11}+\sum_{i=1}^{4}c_{i}\cdot s_{11-i}=s_{11}+c_{1}\cdot s_{1... ...dot s_{9}+c_{3}\cdot s_{8}+c_{4}\cdot s_{7}=0+1\cdot0+0\cdot1+0\cdot0+1\cdot0=0$

    Step 3: since $ d=0$, $ m=m+1=5+1=6$, and we skip to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=11+1=12$

  13. Step 1: $ C(x)=1-x+x^{4},$ $ B(x)=1+x^{2},$ $ m=6,$ $ b=1,$ $ L=4,$ $ N=12\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{12}+\sum_{i=1}^{4}c_{i}\cdot s_{12-i}=s_{12}+c_{1}\cdot s_{1... ...ot s_{10}+c_{3}\cdot s_{9}+c_{4}\cdot s_{8}=0+1\cdot0+0\cdot0+0\cdot1+1\cdot0=0$

    Step 3: since $ d=0$, $ m=m+1=6+1=7$, and we skip to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=12+1=13$

  14. Step 1: $ C(x)=1-x+x^{4},$ $ B(x)=1+x^{2},$ $ m=7,$ $ b=1,$ $ L=4,$ $ N=13\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{13}+\sum_{i=1}^{4}c_{i}\cdot s_{13-i}=s_{13}+c_{1}\cdot s_{1... ...t s_{11}+c_{3}\cdot s_{10}+c_{4}\cdot s_{9}=1+1\cdot0+0\cdot0+0\cdot0+1\cdot1=0$

    Step 3: since $ d=0$, $ m=m+1=7+1=8$, and we skip to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=13+1=14$

  15. Step 1: $ C(x)=1-x+x^{4},$ $ B(x)=1+x^{2},$ $ m=8,$ $ b=1,$ $ L=4,$ $ N=14\not=15=n$. Step 2: find the discrepancy

    $\displaystyle d=s_{14}+\sum_{i=1}^{4}c_{i}\cdot s_{14-i}=s_{14}+c_{1}\cdot s_{1... ... s_{12}+c_{3}\cdot s_{11}+c_{4}\cdot s_{10}=1+1\cdot1+0\cdot0+0\cdot0+1\cdot0=0$

    Step 3: since $ d=0$, $ m=m+1=8+1=9$, and we skip to step 6. Step 6: increase $ N$

    $\displaystyle N=N+1=14+1=15$

  16. Step 1: $ C(x)=1-x+x^{4},$ $ B(x)=1+x^{2},$ $ m=9,$ $ b=1,$ $ L=4,$ $ N=15=n$. terminate the algorithm
At this point the algorithm outputs the last value of $ L$ and $ C(x)$ which are $ L=4$ and $ C(x)=1-x+x^{4}$ . The algorithm terminates since $ N=n$. Figure 2 (from Massey [4]) depicts the minimal LFSR found in this example. Since the coefficients $ (c_{1},c_{2},c_{3},c_{4})$ of the connection polynomial $ C(x)=1-x+x^{4}$are $ (1,0,0,1)$ we know that the inputs for the mod 2 adder are taken off the first and forth registers. Since $ L=4$, we know that the LFSR must have a minimum of four registers.

\includegraphics[% scale=0.3]{Figure2.eps}

Of course, when performing cryptanalytic work on an intercepted enciphered message, one may not always have all the information available about the stream cipher to make breaking the code as easy as I have just shown. Prior to beginning the example, it was mentioned that for a LFSR sequence of known period length $ p$, one can easily determine how many terms of the sequence were necessary to find the minimal connection polynomial. Further research will look at what to do when the full period length of the sequence is unkown.

Appendix

LFSR Sequence Generator Function in SAGE 

"""
Linear feedback shift register (LFSR) sequence commands


Stream ciphers have been used for 
a long time as a source of pseudo-random number generators.

S. Golomb [G] gives a list of three
statistical properties a 
sequence of numbers ${\bf a}=\{a_n\}_{n=1}^\infty$,
$a_n\in \{0,1\}$, should display to be considered
``random''. Define the {\bf autocorrelation} of
${\bf a}$ to be
\[
C(k)=C(k,{\bf a})=\lim_{N\rightarrow \infty}
{1\over N}\sum_{n=1}^N (-1)^{a_n+a_{n+k}}.
\]
In the case where ${\bf a}$ is periodic with
period $P$ then this reduces to
\[
C(k)={1\over P}\sum_{n=1}^P (-1)^{a_n+a_{n+k}}.
\]
Assume ${\bf a}$ is periodic with period $P$.
\begin{itemize}
\item[] {\bf balance}: $|\sum_{n=1}^P(-1)^{a_n}|\leq 1$.
\item[] {\bf low autocorrelation}: 
\[
C(k)=
\left\{
\begin{array}{cc}
1,& k=0,\\
\epsilon, & k\not= 0.
\end{array}
\right.
\]
(For sequences satisfying these first two properties,
it is known that $\epsilon=-1/P$ must hold.)
\item[] {\bf proportional runs property}:
In each period, half the runs have length $1$,
one-fourth have length $2$, etc. Moveover, there
are as many runs of $1$'s as there are of
$0$'s. 
\end{itemize}

A {\bf general feedback shift register} is a map
$f:{\bf F}_q^d\rightarrow {\bf F}_q^d$
of the form
\[
\begin{array}{c}
f(x_0,...,x_{n-1})=(x_1,x_2,...,x_n),\\
x_n=C(x_0,...,x_{n-1}),
\end{array}
\]
where $C:{\bf F}_q^d\rightarrow {\bf F}_q$ is a given
function. When $C$ is of the form
\[
C(x_0,...,x_{n-1})=a_0x_0+...+a_{n-1}x_{n-1},
\]
for some given constants $a_i\in {\bf F}_q$, the 
map is called a {\bf linear feedback shift register
(LFSR)}. 

{\bf Example of a LFSR} Let
\[
f(x)=a_{{0}}+a_{{1}}x+...+a_{{n}}{x}^n+...,
\]
\[
g(x)=b_{{0}}+b_{{1}}x+...+b_{{n}}{x}^n+...,
\]
be given polynomials in ${\bf F}_2[x]$ and let
\[
h(x)={f(x)\over g(x)}=c_0+c_1x+...+c_nx^n+... \ .
\]
We can compute a recursion formula which allows us to rapidly compute
the coefficients of $h(x)$ (take $f(x)=1$):
\[
c_{n}=\sum_{i=1}^n {{-b_i\over b_0}c_{n-i}}.
\]

The coefficients of $h(x)$ can, under certain conditions on
$f(x)$ and $g(x)$, be considered ``random'' from certain statistical 
points of view.

{\bf Example}:
For instance, if
\[
f(x)=1,\ \ \ \ g(x)=x^4+x+1,
\]
then
\[
h(x)=1+x+x^2+x^3+x^5+x^7+x^8+...\ .
\]
The coefficients of $h$ are 
\[
\begin{array}{c}
1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, \\
1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, ...\ .
\end{array}
\] 
The sequence of $0,1$'s is periodic with period 
$P=2^4-1=15$ and satisfies Golomb's three 
randomness conditions.
However, this sequence of period 15 can be ``cracked''
(i.e., a procedure to reproduce $g(x)$)
by knowing only 8 terms! This is the function of the
Berlekamp-Massey algorithm [M], implemented as
\code{berlekamp_massey.py}.

[G] Solomon Golomb, {\bf Shift register sequences},
Aegean Park Press, Laguna Hills, Ca,
1967

[M] James L. Massey, ``Shift-Register Synthesis and BCH Decoding.''
IEEE Trans. on Information Theory, vol. 15(1), pp. 122-127, Jan 1969.

AUTHOR:
    -- Timothy Brock

Created 11-24-2005 by wdj. Last updated 12-02-2005.
"""

###########################################################################
#  Copyright (C) 2006 Timothy Brock
#  and William Stein <wstein@ucsd.edu>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#                  http://www.gnu.org/licenses/
###########################################################################

import copy

from sage.structure.all import Sequence
from sage.rings.all import is_FiniteField

def lfsr_sequence(key, fill, n):
    r"""
    This function creates an lfsr sequence.

    INPUT:
        key -- a list of finite field elements, [c_0,c_1,...,c_k].
        fill -- the list of the initial terms of the lfsr sequence, 
                [x_0,x_1,...,x_k].
        n -- number of terms of the sequence that the
             function returns.

    OUTPUT:
        The lfsr sequence defined by $x_{n+1} = c_kx_n+...+c_0x_{n-k}$,
        for $n \leq k$.

    EXAMPLES:
        sage: F = GF(2); l = F(1); o = F(0)
        sage: F = GF(2); S = LaurentSeriesRing(F,'x'); x = S.gen()
        sage: fill = [l,l,o,l]; key = [l,o,o,l]; n = 20
        sage: L = lfsr_sequence(key,fill,20); L
        [1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0]
        sage: g = berlekamp_massey(L); g
        x^4 + x^3 + 1
        sage: (1)/(g.reverse()+O(x^20))
        1 + x + x^2 + x^3 + x^5 + x^7 + x^8 + x^11 + x^15 + x^16 + 
	    x^17 + x^18 + O(x^20)
        sage: (1+x^2)/(g.reverse()+O(x^20))
        1 + x + x^4 + x^8 + x^9 + x^10 + x^11 + x^13 + x^15 + 
	    x^16 + x^19 + O(x^20)
        sage: (1+x^2+x^3)/(g.reverse()+O(x^20))
        1 + x + x^3 + x^5 + x^6 + x^9 + x^13 + x^14 + x^15 + 
	    x^16 + x^18 + O(x^20)
        sage: fill = [l,l,o,l]; key = [l,o,o,o]; n = 20
        sage: L = lfsr_sequence(key,fill,20); L
        [1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1]
        sage: g = berlekamp_massey(L); g
        x^4 + 1
        sage: (1+x)/(g.reverse()+O(x^20))
        1 + x + x^4 + x^5 + x^8 + x^9 + x^12 + x^13 + x^16 + x^17 + O(x^20)
        sage: (1+x+x^3)/(g.reverse()+O(x^20))
        1 + x + x^3 + x^4 + x^5 + x^7 + x^8 + x^9 + x^11 + 
	    x^12 + x^13 + x^15 + x^16 + x^17 + x^19 + O(x^20)

    AUTHOR:
        -- Timothy Brock (11-2005, with code modified from Python Cookbook,
            \url{http://aspn.activestate.com/ASPN/Python/Cookbook/}
    """
    if not isinstance(key, list):
        raise TypeError, "key must be a list"
    key = Sequence(key)
    F = key.universe()
    if not is_FiniteField(F):
        raise TypeError, "universe of sequence must be a finite field"

    s = fill
    k = len(fill)
    L = []
    for i in range(n):
        s0 = copy.copy(s)
        L.append(s[0])
        s = s[1:k]
        s.append(sum([key[i]*s0[i] for i in range(k)]))
    return L

Autocorrelation Function for Sequences in SAGE 

import copy

def autocorrelation(L,p,k):
    """
    INPUT:
        L -- is a periodic sequence of elements of ZZ or GF(2).  L must have length >= p
        p -- the period of L
        k -- k is an integer (0 < k < p)
        
    OUTPUT:
        autocorrelation sequence of L

    EXAMPLES:



    AUTHOR: Timothy Brock (February 2006)
    """
    L0 = copy.copy(L)[:int(p)]
    L0=L0+L0[:int(k)]
    L1 = [int(L0[i])*int(L0[i+int(k)])/p for i in range(p)]
    return sum(L1)

Berlekamp-Massey Algorithm implemented in SAGE 

def massey(s):
    """
    INPUT:
        s -- a sequence of elements of a finite field (F) of even length
    OUTPUT:
        C(x) -- the connection polynomial of the minimal LFSR.

    This implements the algorithm in section 3 of J. L. Massey's article [M]. 

    EXAMPLE:
       	sage: F = GF(2)
	sage: F
	Finite Field of size 2
	sage: o = F(0); l = F(1)
        sage: key = [l,o,o,l]; fill = [l,l,o,l]; n = 20
        sage: s = lfsr_sequence(key,fill,n); s
        [1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0]
        sage: massey(s)
        x^4 + x + 1

    AUTHOR: Timothy Brock (24 Mar 2006)

    REFERENCES:
        [M] J. L. Massey, "Shift-register synthesis and BCH decoding," 
            IEEE Trans. Inform. Theory, vol. IT-15, pp. 122--127, Jan. 19    69.
    """

    FF = s[0].base_ring()	
    R = PolynomialRing(FF, "x")
    x = R.gen()
    C = R(1); B = R(1); m = 1; b = FF(1); L = 0; N = 0
    ##The above was initializing steps
    while N < len(s):
        if L > 0:
            r = min(L+1,C.degree()+1)
            d = s[int(N)] + sum([(C.list())[int(i)]*s[int(N-i)] for i in range(1,r)])
        if L == 0:
            d = s[int(N)]
        if d == 0:
            m += 1
            N += 1
        if d > 0:
            if 2*L > N:
                C = C - d*b**(-1)*x**m*B
                m += 1
                N += 1
            else:
                T = C
                C = C - d*b**(-1)*x**m*B
                L = N + 1 - L
                m = 1
                b = d
                B = T
                N += 1
    return C

Bibliography

1
S. W. Golomb. Shift Register Sequences. Aegean Park Press Laguna Hills, CA, USA 1981.

2
R. Paddock, ``A Guide to Online Information About: Noise/Chaos/Random Numbers and Linear Feedback Shift Registers.'' Circuit Cellar Online: The Magazine for Computer Applications. http://www.designer-iii.com/cco/noise/c89r4.htm, last modified April 17, 2005.

3
T. Brock and R. Rivas, ``Linear Feedback Shift Register Sequences and the Berlekamp Iterative Algorithm.'' http://web.usna.navy.mil/%7Ewdj/teach/sm463/brock-rivas_berlekamp-massey.pdf

4
J. L. Massey, ``Shift-Register Synthesis and BCH Decoding.'' IEEE Trans. on Information Theory, vol. 15(1), pp. 122-127, Jan 1969.

5
A. Menezes, P. van Oorschot, and S. Vanstone. Handbook of Applied Cryptography. CRC Press, Inc.; 1997 pp1-4.

6
H. van Tilborg. ``Coding Theory at Work in Cryptology and Vice Versa.'' Handbook of Coding Theory, vol. 2. Ed. by V.S. Pless and W.C. Huffman. Elsevier Science B.V., 1998. pp. 1195-1226.

7
S. Matyas and C. Meyer. Cryptography: A New Dimension in Computer Data Security-A Guide for the Design and Implementation of Secure Systems. John Wiley & Sons, Inc. 1982. pp. 53.

8
R. Hill. A First Course in Coding Theory. Oxford University Press,1986. pp. 141-163.

9
M. Lucas. Linear Feedback Shift Register Systems. United States Naval Academy, 1990.

10
G. Hardy and E. Wright. The Theory of Numbers. Oxford University Press, 1956.

11
William Stein, David Joyner, SAGE: System for Algebra and Geometry Experimentation, Comm. Computer Algebra 39(2005)61-64. http://sage.scipy.org

12
J. McGowan, ``Implementing Generalized Reed-Solomon Codes and a Cyclic Code Decoder in GUAVA.'' http://cadigweb.ew.usna.edu/%7Ewdj/mcgowan.

13
F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-correcting Codes. North-Holland, 1983.

14
R. Lidl and H. Niederreiter. Introduction to Finite Fields and Their Applications Revised Edition. Cambridge University Press, Cambridge; 1994 pp235-239.

About this document ...

Linear Feedback Shift Registers and Cyclic Codes in SAGE

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -t 'T. Brock Math Honors Thesis 2005-2006' -split 0 brock-honorsthesis.tex

The translation was initiated by David Joyner on 2006-04-24

Footnotes

... Brock1
Mathematics Department USNA Honors 2005-2006 Advisor: Professor Joyner
David Joyner 2006-04-24