0
$\begingroup$

I'm using random numbers for simulations. The main reason is to have an input sequence where no (simulation) algorithm is going to lock on a pattern and introduce unwanted effects into the simulation. So it seems random numbers have irreversibly lost the structure and it's unlikely that an algorithm is going to "reverse-engineer" it.

Is there a formal way to quantify this, such that pseudo-random numbers come out as being very unstructured?

I've read something about Kolmogorov complexity, but strictly speaking there is a very simple algorithm which can generate (pseudo)random numbers?! So they are not complex in this sense?

$\endgroup$
  • $\begingroup$ Are you sure any algorithm can generate random enough numbers without external source of entropy? $\endgroup$ – joro Jan 22 '15 at 13:18
  • $\begingroup$ @joro: Of course not. I do not suppose a pristine random number sequence, but I rather assume the real-world pseudo-random numbers. In the end, that's what I use. And I assume the period is large enough for the simulation. I cannot be sure that an evil algorithm will hack into it by trialing seeds for a pseudorandom generator. But most algorithms don't. How can I quantify this? $\endgroup$ – Gerenuk Jan 22 '15 at 16:47
  • $\begingroup$ There are free programs/services which will tell you how random a sequence of bytes is. You might consider asking about "quality of random sequence of bytes" on crypto.stackexchange.com. Are Fibonacci numbers numbers modulo large n "pseudorandom" by your definition? Is \pi in base 2 random enough for you? $\endgroup$ – joro Jan 22 '15 at 17:33
  • 5
    $\begingroup$ I think this question is more suitable for Computer Science or Cryptography. $\endgroup$ – Kaveh Jan 22 '15 at 18:05
  • 1
    $\begingroup$ see also what randomness really is cs.se. see also diehard tests $\endgroup$ – vzn Jan 22 '15 at 22:18
7
$\begingroup$

I can give several answers to your question.

Algorithmic randomness. When should we call a sequence $x_1,\ldots,x_n$ of bits random? A priori, all sequences have the same probability, so it's not clear on what grounds we should single out one sequence or another as not being random. This is partly a philosophical question, but "applied philosophy" has given rise to several definitions of algorithmic randomness, detailed in the Wikipedia entry. These notions are actually for infinite sequences, but some of them can also be used for finite sequences, for example the notion of Kolmogorov-random sequence that you mention in your question. The trouble with these notions is that one cannot compute random sequences – that's a feature of the definitions.

Pseudorandomness. Complexity theorists and (theoretical) cryptographers prefer a more permissive notion of randomness. Suppose you need a random sequence to run algorithm A which belongs to complexity class C. A pseudorandom sequence is a sequence that "fools" algorithms of complexity class C – that is, it looks random to such algorithms. More formally, algorithms of class C cannot distinguish a small set of pseudorandom sequences from a truly random sequence. As joro mentions in their comment, for this definition to make sense, you need to look at a collection of pseudorandom sequences, since one sequence could always be distinguished from a random sequence (at least in non-uniform computation models).

There are no known pseudorandom sequences against complexity classes beyond some very weak ones, though there are constructions which work assuming some complexity assumptions. Such constructions are not necessarily useful for practical applications, for three reasons: (1) you are given a large set of sequences rather than one sequence, and you have to run your (decision) algorithm on all of them; (2) constructions in complexity theory tend to be impractical; the pseudorandom sequences are probably really hard to generate in practice, especially for realistic values of $n$ (the input size); (3) asymptotic analysis doesn't usually yield concrete bounds, so it would be hard for you to figure out what parameters to use; worse, if the security of the construction relies on some non-explicit complexity assumption (e.g. P$\neq$NP), the guarantee could be purely asymptotic, and not give any explicit bounds.

Practical randomness. Random numbers are used in practice in two kinds of situations: numerical simulations and cryptography. When using random numbers for numerical simulations, the "quality" of the numbers is not as important as the time it takes to generate them; in practice, even rather simple pseudorandom number generators seem to "work". A search of the relevant literature will reveal some modern examples. Some of the old pseudorandom number generators were indeed bad (in some situations), but the this threshold has been crossed, and from an engineering perspective the problem can be considered solved.

Random numbers used for cryptographic purposes need to be more secure, since now we're against somebody who's construction the algorithm for the express purpose of reverse engineering the random stream. In this case one needs to be a bit more careful and use a secure, industry standard stream cipher. Such ciphers are available, and I strongly urge against using anything else, especially anything which you designed yourself. For extra security, XOR the output of several stream ciphers using independent keys.

$\endgroup$
  • $\begingroup$ I'm not completely sure, whether I can translate this description to my picture about algorithms locking-in. The pseudorandomness definition seems interesting. But I don't have a notion of "real random numbers" to compare to. And also I have only a single stream of numbers. But, building on this a explanation along the lines of "most algorithms cannot lock-in onto any pattern (apart from the unavoidable long periodicity)" seems good. Maybe, my knowledge about this topic is too limited to understand. $\endgroup$ – Gerenuk Jan 22 '15 at 17:07
  • $\begingroup$ @Gerenuk Your notion of lock in can (maybe) be translated to, an algorithm locks in if it has some ability to predict future random bits. Not being able to predict random bits with prediction strategies of a given computational power is exactly a formulation of notions of algorithmic randomness. $\endgroup$ – kasterma Feb 8 '15 at 19:58
  • $\begingroup$ @Gerenuk Also a notion of real random number is taking a random number uniformly from say a unit interval. Then under many notions of predicting bits it is not too hard to show that any set of reals where the bits are predicted reasonably well forms a null set; i.e. one where the uniformly picked number will end up in with probability 0. $\endgroup$ – kasterma Feb 8 '15 at 20:01
  • $\begingroup$ Just so people don't misunderstand your answer, let me comment that rather simple pseudorandom generators do not usually "work". Use one that has been tested and is considered good by experts. $\endgroup$ – Peter Shor Feb 9 '15 at 12:12
4
$\begingroup$

Although the previous answers are fairly comprehensive, let me just add that there are notions of time-bounded Kolmogorov complexity which can apply in your situation. For example, $K^t(x)$ is the length of the shortest program that produces $x$ within time $t(|x|)$. So, for example, a pseudorandom number generator that takes time $n^3$ could still produce numbers with high $K^t$ for $t(n)=n^2$, even though the numbers it produces will all have usual Kolmogorov complexity bounded by a single constant. Look up "Resource-bounded Kolmogorov complexity" or see Li and Vitanyi chapter 7 for more details.

$\endgroup$
0
$\begingroup$

Random numbers are defined as a sequence which has no pattern, and therefore no predictability, no matter who looks and no matter what tests) they use. There are problems with finite sequences vs infinite sequences, but we'll not go there.

Random is not in the eye of the beholder -- if the beholder is human. Cats might be very much better, but training them is currently over difficult. Magicians routinely perform parlor tricks asking audience members to produce random numbers. Humans don't do it well at all.

There are some tests for randomness (or that find non-random, many perhaps all?, sequences.) Which is the more or less the inverse problem, of course. Knuth , vol 2, suggests a large number of statistical tests for random sequences, and essentially gives up. These tests will catch some of the most blatant non-random sequences that someone claims is random, but ... By all means, test if you have time, but don't think you problems are over if no non-randomness is found. Might pop up on the test Knuth didn't know about, or the one JoeStat invents tomorrow.

No program running a finite state machine (all practical computers of any architecture, though perhaps quantum computers might be a possibility) can produce a random sequence. It is the nature of a finite state machine.

Some physical processes are believed (with apparently good reason) to be random, and so a reading from such a process might produce random sequences. Both Intel and Via have long built such random number generators into some of their CPUs. Some Silicon Graphics researchers demonstrated that the patterns in a LavaLamp are random (I think I believe this!), and so on. The difficulty is that such processes must be observed and converted into digital information for use. All measurement methods we have are imperfect,and assuring that the method you chose to read white noise from some silicon junction might induce a pattern into the sequences you produce is fundamentally impossible. Can you prove that this is not so?

Some mathematical entities are believed to be random. For instance, pi. The digits which make up its sequence are thought to be random. But there exists an algorithm for finding the nth digit of pi very quickly. What consequence does this have? Or e? Or phi? Or phi? Or ...?

This is a difficult problem. The RANDU routine, from the SHARE algorithm collection, was thought good enough for decades. The random number function in nearly all languages libraries and operating system routines are sadly inadequate. Do not use them without careful investigation. RANDU wasn't random and so much research requiring random sequences may have been flawed. John von Neuman suggested using the inner digits of large squares. But his quote about any one looking for algorithmically generated random numbers being in a state of sin is quite apt.

Randomness appears to be relatively easy to produce, and so many programmers have written routines which claim to be random; which probably accounts for so many library routines being quite non-random. Netscape built one into some early versions of its software until it was proven rather spectacularly to be grossly non-random.

As a practical matter, Shannon's concepts of information entropy are directly relevant. Kolmogorov complexity is in some sense a measure of the entropy of the sequence under test.

In the practical world, in which something purporting to a random number is required, and the randomness of it underpins the security of some security scheme, such caveats are troublesome. No system has sufficient processing capacity to apply all of Knuth's tests, all those other tests, and ... to the random numbers it not only needs but must use.

Hence the concept of cryptographically secure random numbers. Notice the mealy mouth evasion here. These are not random, they are just believed to be "sufficiently random" to be of use in cryptography whose effectiveness (ie, security) is dependent on their randomness.

And, CSRN vary in how random they can be. For instance, stream cyphers require large sequences of random key material to be generated in a short time. The actual encryption function in these is, in principle, the extremely fast machine instruction XOR. If the key generating sequence can be determined security goes poof. A secure, high speed pseudo random generator is required, and furthermore, one (or many) which provide high security.

Other cyphers, such as the various block cyphers, require random keys for security. Those keys must be long enough to be hard to guess in a brute force attack, but if they are non-random no brute force will be required.

Asymmetric key cypher algorithms also require random keys, but they must meet certain mathematical tests, and be so related that the encryption algorithm is really one way, even against well equipped attack.

Poorly designed encryption algorithms are poor and breakable, no matter how well the keys approach real randomness. Can you tell the difference between such an algorithm and a well designed one? Specialists have trouble, so modesty is suggested.

Various schemes have been suggested for CSRNGs, but nearly all are somewhat dubious. For instance, if real world data (disk timings, key stroke timings, network packet timings, ...) is used, what degree of assurance can one have that one's disks (etc) don't have some periodicity that a sufficiently motivated attacker can't discover?

The Linux kernel is sufficiently sensitive to this issue that it has two random routines, one which is quick and will continue to produce "random numbers" on each call, and another which is rather slower, but which produces only random numbers tied directly to various physical parameters in the running machine.

But I suggest you consult Practical Cryptography by Schneier and Ferguson for the design of a CSRNG system they call Fortuna. It goes some way to avoid any entropy limitation from any source, to mix the inputs from each of the (perhaps not entirely random) sources it gets in such a way to decrease predictability as much as possible. It also protects against now unknown attacks against the entropy pool(s) it uses, and to evade attacks against that pool when the machine is off (and so vulnerable to disk theft and analysis). It is not a simple system, but it appears to be quite robust, sufficiently fast for many uses (if not for the entire key sequence required by high speed stream cyphers -- seeds for such a generator would seem very usable however). And the design, and design criteria, are publicly available, a far from trivial desideratum.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.