2

线性同余生成器是一个很好的算法。但是有更快的算法吗？

4

3 回答 3

4

由于 8 位 CPU 通常无法进行快速除法甚至乘法运算，因此使用线性同余生成器通常不是一个好主意。

线性反馈移位寄存器 (LFSR)仅使用移位和逻辑运算。

如果您使用数组，它将成为广义线性反馈移位寄存器 (GLFSR)，这是Mersenne Twister使用的通用方法。它循环遍历数组，而不是在每一步移动所有位，这样您就可以拥有一个大的状态空间（数百到数千位），而只需很少的计算工作。

请注意，由于它是一种线性方法，因此不适用于密码学。

于 2013-05-26T15:08:22.353 回答
4

我记得，有一个 8x8=16 位乘法器，因此实现一个 lag-n进位乘法生成器可能是可行的。这种技术的优点是，如果你能找到一个合适的安全素数，你可以用很少的算术得到一个很长的周期。

不幸的是，只有 8 位乘数的安全素数选项似乎并不多，而且我担心较短的乘数可能会导致一些通常不会出现在 MWC 中的弱点。

我只是把它放在一起，虽然我不能 100% 确定它正确地实现了 MWC，但它实际上通过了数量惊人的更顽固的测试：

#define STATE_BYTES 7
#define MULT 0x13B /* for STATE_BYTES==6 only */
#define MULT_LO (MULT & 255)
#define MULT_HI (MULT & 256)

uint8_t rand8(void)
{
    static uint8_t state[STATE_BYTES] =
    { 0x87, 0xdd, 0xdc, 0x10, 0x35, 0xbc, 0x5c };
    static uint16_t c = 0x42;
    static int i = 0;
    uint16_t t;
    uint8_t x;

    x = state[i];
    t = (uint16_t)x * MULT_LO + c;
    c = t >> 8;
#if MULT_HI
    c += x;
#endif
    x = t & 255;
    state[i] = x;
    if (++i >= sizeof(state))
        i = 0;
    return x;
}

如您所见，乘法器实际上是 9 位，但我们使用移位加法来实现硬件乘法器无法管理的最后一位。

在进一步的测试中，我发现了一个合适的 89 位安全素数，它确实通过了几乎所有的顽固分子。更改这些行：

#define STATE_BYTES 10
#define MULT 0x153 /* for STATE_BYTES==10 only */

我用这个种子进行测试：

static uint8_t state[STATE_BYTES] =
{ 0x87, 0xdd, 0xdc, 0x10, 0x35, 0xbc, 0x5c, 0xb6, 0xca, 0x0a, };
static uint16_t c = 0x42;

种子只是来自 /dev/random 的一些位，您可以自由选择自己的。但是，增加状态大小基本上是作弊，因为它可以让种子的质量在随机性测试的成功或失败中发挥更大的作用。坏种子可能会导致不太随机的结果。

于 2013-05-26T17:40:31.850 回答
0

不，没有通过通用 CPU 实现的显着更快的算法。正如@Joachim Isaksson 和@Michael Burr 所提到的，如果不降低质量或做一些奇怪的事情，就没有什么可以做的了。g：在编译时计算一个巨大的随机数列表，然后运行时生成很快。

任何真正的快速随机数生成器都使用专门的硬件。由于您已标记 [微控制器]，请查看您正在使用的处理器以了解它可能提供的特殊功能。

此外：为您的 PRN 需求提供更多信息可能有助于引出一些新颖的想法（数字长度、速度：O(n) 或时间、随机性程度等），例如使用由大素数修改的微控制器基于时间的计数器.

于 2013-05-25T15:04:56.973 回答