If a permutation polynomial mod 2**n is employed as a PRNG, it is well
known that the lower order bits of the sequence of the binary words
output are fairly poor statistically. On the other hand, for values of
n that are not too small, the higher order bits are very satisfactory. Extensive testing up to n=256 indicates that as a rule only the 22
lower order bits of the words output are poor. This empirical evidence
is in good conformance to a recent rigorous theoretical result obtained
by Emil Lerner in his PhD research work, who showed that the sequence
of the higher order bits of the outputs of such permutation polynomials
are very uniformly distributed.
The basic idea of the present scheme of pseudo-random bits generation
is that, if one employs two such PRNGs, lets one of them be rotated by
n/2 bits and xor both together, then the good bits of of the outputs of
each should be able to compensate the poor bits of the other. Test
statistics for the case n=32 show that the correctness of our idea is
clearly verified, though there are yet a couple of values that lie
outside the desired confidence interval [7.178, 7.189] due to the fact
that, for n=32, in the outputs of the constituent PRNGs more than one
half of the bits are poor and thus this large defect can't therefore be expected to be completely compensated. For larger values of n, e.g.
n=64, the above mentioned cause of troubles no longer exists and the
test statistics of all individual bits of the xor-combined output are
entirely satisfactory.
Implementation of the scheme is straightforward. A Python code can be
found in:
http://s13.zetaboards.com/Crypto/topic/7355166/1/
M. K. Shen
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)