大周期小数的LFSR

Question

我想用LFSR生成一些随机数。然而，LFSR输出取决于抽头的数量，因此在一个大的时间段内，我使用了大(相对)位数。这使得数字与周期一样大。例如，我想使用16位LFSR来生成随机的5位数字.怎样才能减少位数，但仍然确保单个数字不会重复，序列不会变短？

编辑：

对于5级，我使用多项式x^5+x^3+1和以下代码：

lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0x0014u); 

对于n= 16，我使用多项式x^16 + x^14 + x^13 + x^11 +1

lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xB400u);  

这些都有问题吗？

Answer 1

将m\le n位从n-bit LFSR状态中提取出来，仍然会得到一个具有周期2^n-1的m-bit字序列，假设n-bit LFSR的状态不是零，其生成多项式是本原的。证明草图:利用带有本原反馈多项式的LFSR的一个基本性质，它的周期不包括全零状态，它的周期具有2^n-1状态。因此，任何位都有周期2^n-1和2^{n-1} 1和2^{n-1}-1 0。

此外，该序列与周期m-bit序列2^n-1一样均匀分布:除达到2^{n-m}-1时间的0外，每个2^m值都达到2^{n-m}时间。事实上，这种分布太均匀了，不可能是随机的。

因此，取(比方说)最大长度16位LFSR的低5位将产生一个周期为65535的序列，在此期间，32个值中的每一个都将达到2048次，除了0达到2047次外。然而，这甚至不会产生一个可通过的非加密RNG:如果LFSR使用Fibonacci结构，任何输出中的4位直接来自上一个输出，而Galois结构的情况就很难更好了(或者根本不需要，取决于多项式)。例如，在更新的问题中使用16位生成器(按照我喜欢的惯例，使用多项式x^{16}+x^5+x^3+x^2+1而不是它的自反x^{16}+x^{14}+x^{13}+x^{11}+1)

#include <stdio.h>
int main(void){
  unsigned x = 1, j = 128, y; // initial sate, number of outputs, output
  do {
    y = x&31;
    printf("%02X%c", y, --j&15?' ':'\n');
    x = x>>1 ^ 0xB400&-(x&1);
  } while(j);
return 0;}

我们得到了这个：

01 00 00 00 00 00 00 10 08 14 1A 0D 16 0B 05 02
01 00 10 08 04 02 11 08 14 0A 05 02 11 18 0C 16
1B 1D 1E 0F 17 1B 0D 16 0B 15 1A 0D 16 0B 05 02
11 08 04 12 19 1C 1E 0F 17 0B 05 12 19 1C 0E 17
1B 1D 0E 07 03 01 10 18 1C 0E 17 1B 1D 1E 0F 07
13 09 14 0A 05 12 19 1C 0E 07 13 19 1C 1E 1F 1F
1F 1F 1F 0F 07 13 09 14 1A 1D 0E 07 03 01 10 18
1C 1E 1F 0F 07 13 09 04 12 09 14 0A 15 1A 1D 1E

令人痛苦的是，任何输出的右十六进制数字总是前一个输出的右移1。

一种可能的解决方案是为每个输出的m位执行LFSR m时间步骤，在每个步骤中收集1位。一个问题是，当\gcd(m,2^n-1)\ne 1时，周期被这个因子所减少(并且均匀分布的证明不再有效)。

相反，我以前建议输出y = ((0x6D9B*x+0xDB75)&0xFFFF)>>11。它确实改善了一些事情，但是y = x&31的一些问题仍然存在:两个连续输出的分布非常糟糕。像y = 0x6D9B*x, y = (y<<4 ^ y)*0xDB75, y = (y<<2 ^ y)>>11 & 31这样的东西进一步改进了一些东西，同时明显地保持了周期和均匀分布(因为在>>11 & 31执行步骤之前，从低16位x到低16位y的转换是映射)。

警告:即使通过使用更复杂的输出转换来完善这一点，结果序列在任何程度上都不是加密强的，如果没有更多的状态位，就不可能做到这一点。

Answer 2

1. 如果您将其用于加密目的，请不要使用LFSR。使用LFSR产生伪随机数是高度不安全的。相反，您应该使用标准的密码PRNG，例如/dev/urandom。您只需重复从/dev/urandom读取字节，并保持低5位。这将提供一个非常大的周期(就所有实际目的而言，基本上是无限的)，并将保留其加密能力。
2. 另一方面，如果您没有将此用于加密目的，则此问题在此处为非主题，应关闭。

让我们知道是哪一种情况，这样我们才能适当地调整问题和反应。