A SIMPLE UNPREDICTABLE PSEUDORANDOM NUMBER GENERATOR
A SIMPLE UNPREDICTABLE PSEUDORANDOM NUMBER GENERATOR
复制标题
DOI：
10.1137/0215025
复制
发表时间：
1986-05-01
影响因子：
1.6
通讯作者：
SHUB, M
中科院分区：
文献类型：
--
作者：
BLUM, L;BLUM, M;SHUB, M
本文提出了两个密切相关的伪随机序列发生器：输入为P撇的发生器输出1除以P所得的商数。生成器的输入为N，（其中N是不同素数的乘积，每个素数全等于3 mod 4，并且是二次剩余），输出为，从短种子中，每个生成器有效地产生长的分布良好的序列。此外，这两个发电机的核心都有计算困难的问题。然而，第一个生成器的序列是完全可预测的（从任何一小段连续的数字中，人们可以推断出“种子“P，并向前和向后继续序列），而第二个生成器，在某种棘手的假设下，在精确的意义上是不可预测的。第二个生成器有额外的有趣的属性：从和N的知识，但不是PorQ，一个可以产生的序列向前，但在上述棘手的假设下，一个不能产生的序列向后。从PandQ的额外知识，可以反向生成序列;甚至可以从序列中的任何一点“跳”到任何其他点。由于这些属性，thegenerator承诺许多有趣的应用，例如，到公钥密码学为了在实践中使用这些生成器，需要分析这些序列的各种属性，例如它们的周期。分析从这里开始。
Two closely-related pseudo-random sequence generators are presented: Thegenerator, with inputPa prime, outputs the quotient digits obtained on dividing 1 byP. Thegenerator with inputsN,(whereis a product of distinct primes, each congruent to 3 mod 4, andis a quadratic residue), outputswhereand.From short seeds each generator efficiently produces long well-distributed sequences. Moreover, both generators have computationally hard problems at their core. The first generator’s sequences, however, are completely predictable (from any small segment ofconsecutive digits one can infer the “seed,”P, and continue the sequence backwards and forwards), whereas the second, under a certain intractability assumption, is unpredictable in a precise sense. The second generator has additional interesting properties: from knowledge ofandNbut notPorQ, one can generate the sequence forwards, but, under the above-mentioned intractability assumption, one can not generate the sequence backwards. From the additional knowledge ofPandQ, one can generate the sequence backwards; one can even “jump” about from any point in the sequence to any other. Because of these properties, thegenerator promises many interesting applications, e.g., to public-key cryptography. To use these generators in practice, an analysis is needed of various properties of these sequences such as their periods. This analysis is begun here.