Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Randomness: Part I

DZone's Guide to

Randomness: Part I

In part one of this series on random numbers we explored the flatness of the distribution and why that was important for Monte Carlo simulations. But another important part of randomness is unpredictability. How predictable is your pseudorandom number generator?

· Performance Zone
Free Resource

Transform incident management with machine learning and analytics to help you maintain optimal performance and availability while keeping pace with the growing demands of digital business with this eBook, brought to you in partnership with BMC.

Random numbers should appear to be jumbled into no discernible order. But pseudorandom number generators are programs and therefore deterministic. In some sense they are like a deck of cards that's been well shuffled. As you deal the cards out and place them faceup one on top of the other they seem to come up randomly, but if you pick up the deck and start dealing again the cycle will repeat. An easy improvement on the cyclical problem is to arbitrarily pick a "seed" number and to deal that many cards first before using the next card as your random selection. This does help with the obvious cyclical repetition, but unless you "seed" every operation you will still get small spans that follow the inherent pattern. You might think you could use a pseudo-random number for the "seed" on another pseudorandom number generator, but all that does is create a new deterministic pattern that's based on both of the pseudorandom numbers.

From a practical perspective if your pseudorandom number generator has a fine enough resolution (e.g. 64 bits or more) and the probability of the output of the generator is statistically flat over the entire output range, then for most applications this approach might be random enough. But sometimes pseudorandom number generators contain hidden correlative aspects in their algorithms. For instance if you were to select pairs of random numbers in sequence and plot them on an X-Y plane you would expect a random dot pattern. But some pseudorandom number generators produce something like:

Image title

And if you selected groups of three numbers and plotted them in three dimensions you may get something like:

Image title

Suddenly, the illusion of randomness is gone, and if you continue increasing the dimensionality the correlation shows up as increasingly higher dimension hyper planes. Something very predictable is going on here. And if you're relying on the randomness to encrypt data then it can't be good if someone else can predict what your next "random" number will be. 

[For those of you interested in diving into the history of pseudorandom number generators and an analysis of how they work (and how bad they can be) here is an oldish but interesting paper: A Collection of Classical Pseudorandom Number Generators with Linear Structures. (Credit: The two figures above came from this paper.)]

The group RANDOM.ORG is completely focused on random ideas. One of the many things they provide is a service to generate random bitmaps using a true random number generator (TRNG) which uses atmospheric noise for its source of randomness. Below is an example of a truly random bitmap:

Image title

They can also produce bitmaps from pseudorandom number generators (PRNG) and here is one from the rand() function in PHP running on Windows.

Image title

[I still find it amazing that we can so easily and quickly see these patterns visually, but would struggle with purely numerical methods to detect the same patterns.]

So with patterns comes predictability and with predictability, we weaken our power to encrypt securely. Can we improve our pseudo-randomness techniques? Can we make devices that give us truly random numbers?

We will take up these issues in Randomness: Part II.

Evolve your approach to Application Performance Monitoring by adopting five best practices that are outlined and explored in this e-book, brought to you in partnership with BMC.

Topics:
random numbers ,cryptography ,statistics

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}