Skip to main content
added 32 characters in body
Source Link
Dilip Sarwate
  • 20.9k
  • 4
  • 50
  • 99

Printed tables of irreducible polynomials of large degrees are usually incomplete because there are so many of them! What one can do is use various tricks of the trade to figure out a set of $68 = 2\times 34$ consecutive bits of one m-sequence from the other m-sequence (with known generator polynomial as taken from the Peterson and Weldon table) and then run the Berlekamp-Massey algorithm on these consecutive bits to get the shortest shift register that generates the   desired m-sequence.

If ${\bf s} = s_0, s_1, s_2, \ldots $ is one of the m-sequences, then the other m-sequence ${\bf t} = t_0, t_1, t_2, \ldots $ is related to ${\bf s}$ via $t_i = s_{qi}$ where $q = 2^{16}+1 = 65,537$. See the paper "Cross-correlation properties of pseudorandom and related sequences," Proc. IEEE, vol.68, pp.593-619, May 1980 (unfortunately behind IEEE's paywall, but copies can be found in the Internet) if you are unfamiliar with this idea. So, we crank up the LFSR that generates ${\bf s}$ and run it to produce the sequence ${\bf s}$, recording $$t_0 = s_0, ~~t_1 = s_{65537},~~ t_2 = s_{131074},~~ \cdots, t_{67} = s_{4390979}.$$ Once upon a time, cranking out 4 million+ bits would have taken some effort, but these days, it's no big deal.

What next? Well, the Berlekamp-Massey algorithm can be viewed as a shift-register synthesis algorithm: it finds the shortest LFSR that can generate any given sequence. Thus, applying the Berlekamp-Massey algorithm to the first $68$ bits of $\bf t$ which we have just found gives us the LFSR that generates the m-sequence $\bf t$, and away we go!!

Printed tables of irreducible polynomials of large degrees are usually incomplete because there are so many of them! What one can do is use various tricks of the trade to figure out a set of $68 = 2\times 34$ consecutive bits of one m-sequence from the other m-sequence (with known generator polynomial as taken from the Peterson and Weldon table) and then run the Berlekamp-Massey algorithm on these consecutive bits to get the shortest shift register that generates the  m-sequence.

If ${\bf s} = s_0, s_1, s_2, \ldots $ is one of the m-sequences, then the other m-sequence ${\bf t} = t_0, t_1, t_2, \ldots $ is related to ${\bf s}$ via $t_i = s_{qi}$ where $q = 2^{16}+1 = 65,537$. See the paper "Cross-correlation properties of pseudorandom and related sequences," Proc. IEEE, vol.68, pp.593-619, May 1980 (unfortunately behind IEEE's paywall, but copies can be found in the Internet) if you are unfamiliar with this idea. So, we crank up the LFSR that generates ${\bf s}$ and run it to produce the sequence ${\bf s}$, recording $$t_0 = s_0, ~~t_1 = s_{65537},~~ t_2 = s_{131074},~~ \cdots, t_{67} = s_{4390979}.$$ Once upon a time, cranking out 4 million+ bits would have taken some effort, but these days, it's no big deal.

What next? Well, the Berlekamp-Massey algorithm can be viewed as a shift-register synthesis algorithm: it finds the shortest LFSR that can generate any given sequence. Thus, applying the Berlekamp-Massey algorithm to the first $68$ bits of $\bf t$ gives us the LFSR that generates the m-sequence $\bf t$, and away we go!!

Printed tables of irreducible polynomials of large degrees are usually incomplete because there are so many of them! What one can do is use various tricks of the trade to figure out a set of $68 = 2\times 34$ consecutive bits of one m-sequence from the other m-sequence (with known generator polynomial as taken from the Peterson and Weldon table) and then run the Berlekamp-Massey algorithm on these consecutive bits to get the shortest shift register that generates the desired m-sequence.

If ${\bf s} = s_0, s_1, s_2, \ldots $ is one of the m-sequences, then the other m-sequence ${\bf t} = t_0, t_1, t_2, \ldots $ is related to ${\bf s}$ via $t_i = s_{qi}$ where $q = 2^{16}+1 = 65,537$. See the paper "Cross-correlation properties of pseudorandom and related sequences," Proc. IEEE, vol.68, pp.593-619, May 1980 (unfortunately behind IEEE's paywall, but copies can be found in the Internet) if you are unfamiliar with this idea. So, we crank up the LFSR that generates ${\bf s}$ and run it to produce the sequence ${\bf s}$, recording $$t_0 = s_0, ~~t_1 = s_{65537},~~ t_2 = s_{131074},~~ \cdots, t_{67} = s_{4390979}.$$ Once upon a time, cranking out 4 million+ bits would have taken some effort, but these days, it's no big deal.

What next? Well, the Berlekamp-Massey algorithm can be viewed as a shift-register synthesis algorithm: it finds the shortest LFSR that can generate any given sequence. Thus, applying the Berlekamp-Massey algorithm to the first $68$ bits of $\bf t$ which we have just found gives us the LFSR that generates the m-sequence $\bf t$, and away we go!!

Source Link
Dilip Sarwate
  • 20.9k
  • 4
  • 50
  • 99

Printed tables of irreducible polynomials of large degrees are usually incomplete because there are so many of them! What one can do is use various tricks of the trade to figure out a set of $68 = 2\times 34$ consecutive bits of one m-sequence from the other m-sequence (with known generator polynomial as taken from the Peterson and Weldon table) and then run the Berlekamp-Massey algorithm on these consecutive bits to get the shortest shift register that generates the m-sequence.

If ${\bf s} = s_0, s_1, s_2, \ldots $ is one of the m-sequences, then the other m-sequence ${\bf t} = t_0, t_1, t_2, \ldots $ is related to ${\bf s}$ via $t_i = s_{qi}$ where $q = 2^{16}+1 = 65,537$. See the paper "Cross-correlation properties of pseudorandom and related sequences," Proc. IEEE, vol.68, pp.593-619, May 1980 (unfortunately behind IEEE's paywall, but copies can be found in the Internet) if you are unfamiliar with this idea. So, we crank up the LFSR that generates ${\bf s}$ and run it to produce the sequence ${\bf s}$, recording $$t_0 = s_0, ~~t_1 = s_{65537},~~ t_2 = s_{131074},~~ \cdots, t_{67} = s_{4390979}.$$ Once upon a time, cranking out 4 million+ bits would have taken some effort, but these days, it's no big deal.

What next? Well, the Berlekamp-Massey algorithm can be viewed as a shift-register synthesis algorithm: it finds the shortest LFSR that can generate any given sequence. Thus, applying the Berlekamp-Massey algorithm to the first $68$ bits of $\bf t$ gives us the LFSR that generates the m-sequence $\bf t$, and away we go!!