Skip to main content

Galois LSFRLFSR Subsequence Periodicity

I had the following questions -

  1. Concerning generating sequences of bits $\textbf{x} = ( x_{0},x_{1}, ... , x_{n-1})$ where the $x_{i} \in \{0,1\}$ are considered coefficients of a polynomial in $\gamma$ (i.e. a polynomial of form $x_{0} + x_{1}\gamma^{1} + ... + x_{n-a}\gamma^{n-1}$) where $\gamma$ is the root of a polynomial $ \Lambda(\gamma) = c_{0} + c_{1}\gamma + ... + c_{n}\gamma^{n} = 0$, $c_{i} \in \{0,1\}$ (i.e. $\textbf{x}$ is an element in a Galois extension), I understand that all the elements of this extension (i.e all possible n bit binary strings) can be generated through the relation $\textbf{x}_{j} = \gamma \textbf{x}_{j-1} \textbf{mod} \space \Lambda(\gamma)$ for correct choice of $\Lambda(\gamma)$, the "period" of this generator is $2^{n} - 1$ after which the recurrence relation "wraps around" the ring and generates the first element over. This is described on page 11 here. If we consider $k$ bit subsequences of this $n$ bit string, is it possible to derive the period for a such a subsequence?

  2. Is there a reference that concretely describes how to go from a construction above based on arithmetic in the field extension to the familiar Galois LSFRLFSR as described here?

Galois LSFR Subsequence Periodicity

I had the following questions -

  1. Concerning generating sequences of bits $\textbf{x} = ( x_{0},x_{1}, ... , x_{n-1})$ where the $x_{i} \in \{0,1\}$ are considered coefficients of a polynomial in $\gamma$ (i.e. a polynomial of form $x_{0} + x_{1}\gamma^{1} + ... + x_{n-a}\gamma^{n-1}$) where $\gamma$ is the root of a polynomial $ \Lambda(\gamma) = c_{0} + c_{1}\gamma + ... + c_{n}\gamma^{n} = 0$, $c_{i} \in \{0,1\}$ (i.e. $\textbf{x}$ is an element in a Galois extension), I understand that all the elements of this extension (i.e all possible n bit binary strings) can be generated through the relation $\textbf{x}_{j} = \gamma \textbf{x}_{j-1} \textbf{mod} \space \Lambda(\gamma)$ for correct choice of $\Lambda(\gamma)$, the "period" of this generator is $2^{n} - 1$ after which the recurrence relation "wraps around" the ring and generates the first element over. This is described on page 11 here. If we consider $k$ bit subsequences of this $n$ bit string, is it possible to derive the period for a such a subsequence?

  2. Is there a reference that concretely describes how to go from a construction above based on arithmetic in the field extension to the familiar Galois LSFR as described here?

Galois LFSR Subsequence Periodicity

I had the following questions -

  1. Concerning generating sequences of bits $\textbf{x} = ( x_{0},x_{1}, ... , x_{n-1})$ where the $x_{i} \in \{0,1\}$ are considered coefficients of a polynomial in $\gamma$ (i.e. a polynomial of form $x_{0} + x_{1}\gamma^{1} + ... + x_{n-a}\gamma^{n-1}$) where $\gamma$ is the root of a polynomial $ \Lambda(\gamma) = c_{0} + c_{1}\gamma + ... + c_{n}\gamma^{n} = 0$, $c_{i} \in \{0,1\}$ (i.e. $\textbf{x}$ is an element in a Galois extension), I understand that all the elements of this extension (i.e all possible n bit binary strings) can be generated through the relation $\textbf{x}_{j} = \gamma \textbf{x}_{j-1} \textbf{mod} \space \Lambda(\gamma)$ for correct choice of $\Lambda(\gamma)$, the "period" of this generator is $2^{n} - 1$ after which the recurrence relation "wraps around" the ring and generates the first element over. This is described on page 11 here. If we consider $k$ bit subsequences of this $n$ bit string, is it possible to derive the period for a such a subsequence?

  2. Is there a reference that concretely describes how to go from a construction above based on arithmetic in the field extension to the familiar Galois LFSR as described here?

Tweeted twitter.com/StackCrypto/status/848065340957491200
Bumped by Community user
added 7 characters in body
Source Link
Rohit Khera
  • 678
  • 4
  • 11

I had the following questions -

  1. Concerning generating sequences of bits $\textbf{x} = ( x_{0},x_{1}, ... , x_{n-1})$ where the $x_{i} \in \{0,1\}$ are considered coefficients of a polynomial in $\gamma$ (i.e. a polynomial of form $x_{0} + x_{1}\gamma^{1} + ... + x_{n-a}\gamma^{n-1}$) where $\gamma$ is the root of a polynomial $ \Lambda(\gamma) = c_{0} + c_{1}\gamma + ... + c_{n}\gamma^{n} = 0$, $c_{i} \in \{0,1\}$ (i.e. $\textbf{x}$ is an element in a Galois extension), I understand that all the elements of this extension (i.e all possible n bit binary strings) can be generated through the relation $\textbf{x}_{j} = \textbf{x}_{j-1} \textbf{mod} \space \Lambda(\gamma)$$\textbf{x}_{j} = \gamma \textbf{x}_{j-1} \textbf{mod} \space \Lambda(\gamma)$ for correct choice of $\Lambda(\gamma)$, the "period" of this generator is $2^{n} - 1$ after which the recurrence relation "wraps around" the ring and generates the first element over. This is described on page 11 here. If we consider $k$ bit subsequences of this $n$ bit string, is it possible to derive the period for a such a subsequence?

  2. Is there a reference that concretely describes how to go from a construction above based on arithmetic in the field extension to the familiar Galois LSFR as described here?

I had the following questions -

  1. Concerning generating sequences of bits $\textbf{x} = ( x_{0},x_{1}, ... , x_{n-1})$ where the $x_{i} \in \{0,1\}$ are considered coefficients of a polynomial in $\gamma$ (i.e. a polynomial of form $x_{0} + x_{1}\gamma^{1} + ... + x_{n-a}\gamma^{n-1}$) where $\gamma$ is the root of a polynomial $ \Lambda(\gamma) = c_{0} + c_{1}\gamma + ... + c_{n}\gamma^{n} = 0$, $c_{i} \in \{0,1\}$ (i.e. $\textbf{x}$ is an element in a Galois extension), I understand that all the elements of this extension (i.e all possible n bit binary strings) can be generated through the relation $\textbf{x}_{j} = \textbf{x}_{j-1} \textbf{mod} \space \Lambda(\gamma)$ for correct choice of $\Lambda(\gamma)$, the "period" of this generator is $2^{n} - 1$ after which the recurrence relation "wraps around" the ring and generates the first element over. This is described on page 11 here. If we consider $k$ bit subsequences of this $n$ bit string, is it possible to derive the period for a such a subsequence?

  2. Is there a reference that concretely describes how to go from a construction above based on arithmetic in the field extension to the familiar Galois LSFR as described here?

I had the following questions -

  1. Concerning generating sequences of bits $\textbf{x} = ( x_{0},x_{1}, ... , x_{n-1})$ where the $x_{i} \in \{0,1\}$ are considered coefficients of a polynomial in $\gamma$ (i.e. a polynomial of form $x_{0} + x_{1}\gamma^{1} + ... + x_{n-a}\gamma^{n-1}$) where $\gamma$ is the root of a polynomial $ \Lambda(\gamma) = c_{0} + c_{1}\gamma + ... + c_{n}\gamma^{n} = 0$, $c_{i} \in \{0,1\}$ (i.e. $\textbf{x}$ is an element in a Galois extension), I understand that all the elements of this extension (i.e all possible n bit binary strings) can be generated through the relation $\textbf{x}_{j} = \gamma \textbf{x}_{j-1} \textbf{mod} \space \Lambda(\gamma)$ for correct choice of $\Lambda(\gamma)$, the "period" of this generator is $2^{n} - 1$ after which the recurrence relation "wraps around" the ring and generates the first element over. This is described on page 11 here. If we consider $k$ bit subsequences of this $n$ bit string, is it possible to derive the period for a such a subsequence?

  2. Is there a reference that concretely describes how to go from a construction above based on arithmetic in the field extension to the familiar Galois LSFR as described here?

edited body
Source Link
e-sushi
  • 18.1k
  • 12
  • 85
  • 235
Loading
added 150 characters in body
Source Link
Rohit Khera
  • 678
  • 4
  • 11
Loading
Source Link
Rohit Khera
  • 678
  • 4
  • 11
Loading