GF(2)本原多项式x^0项为0时LFSR序列反转相关问题咨询

问题背景 #

在探索用LFSR生成最大周期正向/反向序列时，发现选取的本原多项式表格中所有多项式的x⁰项（常数项）均为1，代码运行正常：

#include <cstdio>
#include <cstdint>

uint8_t rev (uint8_t xi)
{
  uint8_t xo ;

  for (auto n = 8 ; n ; -- n)
    {
      xo = xo << 1 | xi & 1 ;

      xi >>= 1 ;
    }

  return xo ;
}

int main (void)
{
  uint8_t const POLY_F = 0x85 ; // x^8 + x^7 + x^2 + 1 : Normal
  uint8_t const POLY_R = 0x43 ; // x^8 + x^6 + x   + 1 : Reversed

  uint8_t lfsr = 0xFF ;

  for (auto n = 1 ; n <= 5 ; ++ n)                    // 1 -> FF
    {                                                 // 2 -> 7B
      printf ("%u -> %02X\n" , n , lfsr) ;            // 3 -> F6
                                                      // 4 -> 69
      lfsr = - (lfsr >> 7) & POLY_F ^ lfsr << 1 ;     // 5 -> D2
    }

  printf ("\n") ;

  for (auto n = 5 ; n >= 1 ; -- n)                    // 5 -> D2
    {                                                 // 4 -> 69
      lfsr = rev (lfsr) ;                             // 3 -> F6
                                                      // 2 -> 7B
      lfsr = - (lfsr >> 7) & POLY_R ^ lfsr << 1 ;     // 1 -> FF

      lfsr = rev (lfsr) ;

      printf ("%u -> %02X\n" , n ,lfsr) ;
    }
}

但使用工具生成GF(2)最大长度多项式时，有时会输出x⁰项为0的多项式，无法解决这类多项式的序列反转问题，因此提出以下问题：

1. “最大长度”多项式与“本原多项式”是否为同一概念？ #

日常语境中，“最大长度多项式”通常指向本原多项式，但二者并非完全等价：

• 本原多项式是GF(2)上的n次不可约多项式，且能让n级LFSR生成最长的2ⁿ-1周期序列，这是LFSR达到最大周期的核心条件。
• 部分工具会把本原多项式乘以x的幂（如x*f(x)、x²*f(x)）也标注为“最大长度多项式”——这类多项式对应的LFSR序列只是本原多项式对应序列的循环移位，周期依然是2ⁿ-1，本质上和本原多项式等价，但不属于严格定义的本原多项式。

2. 本原多项式的x⁰项能否设为0？ #

不能。
本原多项式的前提是它是GF(2)上的不可约多项式。如果多项式的x⁰项（常数项）为0，说明x是它的因式，即f(x)=x*g(x)，显然可约，不符合本原多项式的不可约要求。因此所有本原多项式的常数项必须为1。

3. x⁰项为0时是否可以反转序列？ #

可以，只需先处理多项式中的x因子：

1. 将x⁰项为0的多项式除以x的幂，得到常数项为1的本原多项式f(x)（比如原多项式是x³*f(x)，就除以x³得到f(x)）。
2. 求f(x)的反多项式（即xⁿf(1/x)），这个反多项式也是本原多项式，对应正向序列的反向序列的LFSR特征多项式。
3. 根据需求将反多项式乘以对应的x的幂，或调整LFSR的移位逻辑，即可实现原多项式对应序列的反转。

本质上，x⁰项为0的多项式只是本原多项式的移位版本，对应的序列是本原多项式序列的循环移位，反转这类序列只需先还原成本原多项式对应的序列，再反转，最后做对应移位即可。

内容的提问来源于stack exchange，提问作者cookiecipher