Analysis of pseudorandom number algorithms: Linear congruence generators, feedback shift registers and AES-based
pseudorandom number generators
Hannes Salin, 2011, Royal Institute of Technology (Sweden)
Abstract
This essay deals with pseudorandom number generation in a comparative
and analytical perspective. The focus is on three different types of
algorithms: a linear congruence generator, a linear feedback shift register
and an AES-based psuedosrandom generator. Of these three, the
latter two are implemented in C++ by the author and the linear congruence
generator is an implementation found on the Internet (author:
Robin Whittle)
This comparison aims to investigate whether different pseudorandom
number generators differ in performance and the degree of statistical
randomness of its output. This is to demonstrate that one should
choose the right pseudorandom number generator to the right context.
Performance testing was conducted by measuring the time for each
algorithm to generate 10^3, 10^6, 10^7 and 10^9 integers (around 4 kB, 4
Mb, 40 Mb and 4 Gb random data). A simple statistical testing was
done with the test battery ENT which provides five different statistical
tests to measure the randomness of integer/bit-sequences. With the test
result that followed, an analysis over the differences between the algorithms
could be done. The result was that of the three tested algorithms
the AES-based PRNG was considered to be the best algorithm
from a security perspective when it had the best statistical values. If
you disregard safety requirements the linear feedback shift register was
considered to be the most useful algorithm from a performance perspective,
because its speed and relative statistical properties were very
good..