如何解决线性反馈移位寄存器不能生成0的问题

线性反馈移位寄存器是一种常见的随机数生成器，但其存在一个问题，即无法生成全为0的随机数序列。解决这个问题的方法是通过添加一个额外的电路来实现。

一种常见的方法是使用一个反馈选择电路，该电路可以将寄存器中所有位的异或和反馈回到寄存器的高位。这样，即使当前寄存器中所有位都是0，反馈选择电路也会将1反馈回到高位，从而保证生成的随机数序列中不会出现全为0的情况。

另一种方法是使用一个非线性电路，例如置换盒或S盒，将线性反馈移位寄存器的输出进行非线性变换。这样，即使初始状态为全0，经过非线性变换后的输出也不会全为0，从而保证了生成的随机数序列的随机性和完整性。

需要注意的是，这些方法可以增强线性反馈移位寄存器的随机性能，但并不能完全消除其存在的局限性。因此，在实际应用中，需要根据具体的需求和安全要求选择合适的随机数生成器。

相关问题

非线性反馈移位寄存器实现随机数生成

### 非线性反馈移位寄存器实现随机数生成

在密码学和安全应用中，非线性反馈移位寄存器（NLFSR）用于生成伪随机序列。与线性反馈移位寄存器不同的是，NLFSR 的反馈函数是非线性的，这使得预测下一个状态变得更加困难。

#### NLFSR 工作原理

为了形成一个最大长度序列（m-sequence），LFSR 的反馈抽头必须对应于模2下的n次本原多项式[^1]。然而，在 NLFSR 中，反馈逻辑不是简单的异或操作，而是更复杂的布尔表达式。这种复杂性增加了系统的不可预测性和安全性。

下面是一个基于 Python 实现的简单 NLFSR：

class NonLinearFeedbackShiftRegister:
    def __init__(self, state, tap_positions):
        self.state = list(state)
        self.tap_positions = tap_positions
    
    def next_state(self):
        new_bit = 0
        
        # Compute non-linear feedback function using AND/OR/XOR operations between tapped bits.
        for i in range(len(self.tap_positions)-1):
            bit_i = int(self.state[self.tap_positions[i]])
            
            if i == 0:
                new_bit ^= ((bit_i & int(self.state[self.tap_positions[-1]])) | (~bit_i & ~int(self.state[self.tap_positions[-1]])))
            else:
                prev_tap_pos = self.tap_positions[i-1]
                curr_tap_pos = self.tap_positions[i]

                new_bit ^= (((bit_i ^ int(self.state[curr_tap_pos])) & int(self.state[prev_tap_pos])) |
                            (~(bit_i ^ int(self.state[curr_tap_pos])) & ~int(self.state[prev_tap_pos])))
        
        shifted_bits = [new_bit] + self.state[:-1]
        self.state = shifted_bits.copy()
    
    def get_output(self):
        return ''.join(str(bit) for bit in reversed(self.state))

# Example usage
nlfsr = NonLinearFeedbackShiftRegister('110', [0, 1])
for _ in range(8):
    nlfsr.next_state()
    print(nlfsr.get_output())

此代码片段展示了如何创建并迭代更新 NLFSR 状态的方法 `next_state` 和获取当前输出的方法 `get_output`。请注意，实际应用中的反馈函数会更加复杂，并且通常由硬件电路来实现以提高效率。

用密码学的知识解决:已知某线性反馈移位寄存器的反馈函数对应的特征多项式是p(x)=x4+x+1，求： （1）该线性反馈移位寄存器的线性递推式和结构图； （2）设初始状态是(a1,a2,a3,a4)=（1，0，0，0），求此线性反馈移位寄存器产生的序列及其周期。

首先我们来解释一下题目中的术语：

- 线性反馈移位寄存器（LFSR）是一种在密码学中广泛使用的序列生成器，它由若干个寄存器组成，每个寄存器只能存储0或1。在每个时刻，LFSR 会根据寄存器中的值计算出一个新的位，然后将这个新位插入到寄存器的最高位，同时将寄存器中的位向右移动一位。这个新位就是 LFSR 的输出，而输入则是一个外部控制信号（称为“反馈”信号），它会对新位的计算产生影响。
- 反馈函数是一个布尔函数，它描述了反馈信号如何从寄存器中的位计算出来。在本题中，反馈函数对应的特征多项式是 p(x) = x^4 + x + 1，这意味着反馈函数是一个 4 位的线性函数，计算方式为对于任意 4 位寄存器的值 a1, a2, a3, a4，反馈函数的输出为 a1 xor a4 xor 1。

现在我们来回答题目的两个问题：

（1）该线性反馈移位寄存器的线性递推式和结构图

根据 LFSR 的定义，我们可以列出它的线性递推式：

an = an-4 xor an-1

其中 a1, a2, a3, a4 分别表示 4 个寄存器的值，an 表示在第 n 个时刻 LFSR 的输出。由于本题中寄存器的个数为 4，所以这个式子就是该 LFSR 的递推式。

至于结构图，我们可以将 4 个寄存器和反馈函数按照下图连接起来：

     +-------+
     |       |
     v       |
+----+---+   |
|        |<--+
|  p(x)  |
|        |---+
+----+---+   |
     |       |
     v       |
     +-------+

其中箭头表示数据流的方向，反馈函数 p(x) 计算 a1 xor a4 xor 1 的结果并作为输入送回寄存器。这样就形成了一个简单的 LFSR。

（2）设初始状态是 (a1, a2, a3, a4) = (1, 0, 0, 0)，求此线性反馈移位寄存器产生的序列及其周期

根据递推式，我们可以递归地计算出 LFSR 的输出序列：

a1 = 1
a2 = 0
a3 = 0
a4 = 0
a5 = a1 xor a4 = 1
a6 = a2 xor a5 = 1
a7 = a3 xor a6 = 1
a8 = a4 xor a7 = 0
a9 = a5 xor a8 = 1
a10 = a6 xor a9 = 0
a11 = a7 xor a10 = 1
a12 = a8 xor a11 = 1
a13 = a9 xor a12 = 0
a14 = a10 xor a13 = 1
a15 = a11 xor a14 = 0
a16 = a12 xor a15 = 1
a17 = a13 xor a16 = 1
a18 = a14 xor a17 = 0
a19 = a15 xor a18 = 1
a20 = a16 xor a19 = 0
...

可以看出，LFSR 的输出序列是一个无限长的伪随机序列，其中每个位都是 0 或 1。为了方便起见，我们可以将序列分成若干个周期，每个周期包含 15 个位：

1 1 1 0 1 0 1 1 0 1 0 1 0 1 1

可以验证，这个周期满足递推式，即对于任意正整数 n，有：

an = a(n+15)

因此，这个周期的长度为 15。