Xorshift和所有LFSR类型的发电机都会发出尖叫声,停止运转,如果一个人用全零状态播种它,就什么也不做。它显示(如果我的测试中没有bug ),下面的函数:
y = one_xorshift_round(y)
y = y ^ key
将抵抗这种锁,因为y的任何非零状态都会产生一个随机值的变化,而任何状态为零的状态都是由键对其他东西的XORed。如果关键因素导致它降到零,它将修复它的下一轮。
我可以想象,您还会从每个产生不同序列的“键”值中获得额外的好处。
我的应用程序是一个Arduino库,它需要统计上的随机数,这些数字根本不需要任何密码强度,但不能一次又一次地重复相同的周期。我想要做的是使用当前的微秒计数,因为板是开启的,它应该在每次使用RNG时都增加一点熵(因为用户输入所导致的事物的确切时间的不确定性等等),并且还会导致随机序列随时间的不同而不同,有一定的人为假象,有一个更大的周期。
我的问题是,是否有一些键的值,或者简单的可变键模式,会导致XORSHIFT生成器做一些不好的事情,比如进入一个短周期?我想,实际计算出来的数学是非常复杂的,但也许有人引用了一篇论文,或者引用了一个类似修改的RNG?
谢谢!
编辑,附加信息:我对所有零状态问题的第一个反应就是每一轮添加1到状态,但是我发现在状态中添加一个常数可以减少一个随常数而变化的值,但似乎没有任何简单的模式。
发布于 2014-03-06 20:12:30
键会导致较短周期的最简单情况是,键是独占的或一个值,并从原始生成器继承它的值。这样做的效果是将状态重置为以前的值,这样它就只能产生一个输出。
如果来自原始生成器的许多不同输出对的键值相同,那么这将代表随机测试中的严重失败,因此更有可能存在许多不同的值,从而有效地将周期中的一个阶段在该周期的不同点上退一步。
所以,假设你的密钥的很多值都可以缩短发电机的周期,这可能是公平的,因为它最终会被困在一个单一值的轨道上。还有一些更复杂的情况会导致更长的轨道,而这些轨道仍然不是完整的周期,但这些情况要想清楚得多。
相反,您可能要做的是分别收集熵,并使用它来调整来自PRNG的输出,而不会破坏PRNG本身的质量。例如,
void add_entropy(uint32_t more)
{
entropy = one_xorshift_round(entropy + more);
}
uint32_t rand(void)
{
y = one_xorshift_round(y);
return one_xorshift_round(y + entropy);
}
发布于 2014-04-04 00:04:30
我不会过多地摆弄一个随机生成器(比如任意改变状态空间),因为它的良好统计特性可能会消失。
测试种子并不是所有的零一点都不坏:这是在这类生成器中所做的事情。如果你想要注入熵,只需在状态空间上输入熵位,如果你得到所有的零,只需输入一个常数。如果状态空间足够大,那么概率很低,所以您输入的内容与此无关。在这种情况下,许多已发布的生成器使用生成器的名称(作为ASCII值的序列)作为生成器的种子!:)
不过,我建议您尝试一些64位变量,如xorshift*/ xorshift +,因为它们比纯xorshift生成器具有更好的统计特性。您可以在http://prng.di.unimi.it/找到最新的报告。
https://stackoverflow.com/questions/22214931
复制相似问题