5

我正在编写一个小姐妹加密功能，我需要一个 PRNG，它可以在整个操作系统中产生一致的结果（所以没有浮点数学，利用硬件或系统级软件）。这会很好，但不是必需的，因为 PRNG 的周期长于 2 30。

我目前正在使用 32 位Xorshift：

#!/usr/bin/perl

use strict;
use warnings;

{
    use integer; #use integer math
    my $x = 123456789;
    my $y = 362436069;
    my $w = 88675123; 
    my $z = 521288629;

    sub set_random_seed {
        $w = shift;
    }

    sub random { 
        my $t = $x ^ ($x << 11);
        $x = $y;
        $y = $z;
        $z = $w;
        my $rand = $w = ($w ^ ($w >> 19)) ^ ($t ^ ($t >> 8)); 
        return $rand % 256; #scale it back to a byte at a time
    }
}

set_random_seed(5);
print map { random(), "\n" } 1 .. 10;

但我很担心，因为我真的不明白它是如何工作的。例如，原始来源没有设置种子的能力，所以我添加了一个，但我不知道我是否为种子选择了正确的变量。

所以，所有这一切都归结为

  1. 你知道 CPAN 上有一个适合我需要的模块吗？
  2. 如果没有，您知道适合我需要的算法吗？
4

2 回答 2

7

Math::Random::Auto是一个 CPAN 模块，实现了著名的Mersenne twister PRNG。

于 2009-03-27T14:09:49.270 回答
7

尝试使用 LFSR -线性反馈移位寄存器。. 外部链接上的第一个链接具有产生任意数量的随机性所需的一切。这样做的好处是它很容易实现，并且可以使用所有整数数学来完成。

我在一个 8051 项目上成功地使用了它。使用 perl，这将是一件轻而易举的事。

更新：

这是一个 8 位 LFSR 的快速 perl 实现：

use strict;
use warnings;

use List::Util qw(reduce);
use vars qw($a $b);

print 'Taps: ', set_taps( 8, 7, 2, 1 ), "\n";
print 'Seed: ', seed_lfsr( 1 ), "\n";
print read_lfsr(), "\n" for 1..10;

BEGIN {
    my $tap_mask;
    my $lfsr = 0;

    sub read_lfsr {
        $lfsr = ($lfsr >> 1) ^ (-($lfsr & 1) & $tap_mask );

        return $lfsr;
    }

    sub seed_lfsr {
        $lfsr = shift || 0;
        $lfsr &= 0xFF;
    }

    sub set_taps {
        my @taps = @_;

        $tap_mask = reduce { $a + 2**$b } 0, @taps;

        $tap_mask >>= 1;

        $tap_mask &= 0xFF;

        return $tap_mask;
    }
}

这段代码只是一个原型。如果我想在生产中使用它，我可能会将它包装在一个对象中并使寄存器大小可配置。然后我们将摆脱那些讨厌的共享变量。

于 2009-03-27T14:12:25.067 回答