Anything but Random

From programing we know that nothing happens for a random reason. Errors, or fluke results are all due to an unforseen proccess, BUT its not random. So this leads me to wonder what is a random number. For computing my guess is that they use a function to spit out arandom number. But the function must have a varible input, otherwise we would always get the same return. My guess is that all funtions that produce a random number or string must be based off the system clock? If this is true, couldnt built in random number generators provided by Microsoft Visual Studio be reverse engeneered so that one could predict a random number? IF so This could be a security issue if Passwords were randomly generated... I hope this makes sense.
~Poe

You're right. Most random number functions rely on a "seed" and that seed usually comes out of the system clock. However, even if you could reverse engineer the function to predict the number, it's still nearly impossible to guess a randomly generated password since for that, you'd have to know the time at which it was generated down to the last millisecond. Finding that out is nearly impossible, since there are 60000 milliseconds in a minute, 3600000 in an hour and 86400000 in a day. Needless to say, that's a hell of a lot of possible seeds.

Cheers,
cgkanchi

Well this was a rather good first post from a newbie.

You are actually on the right track with this (or at least some think) there is a man doing research on this and says, "he found a way," or "he is on the brink of finding it." I misplaced the link to the site but there is a complete site on it. Just google for it.

I really haven't made an opinion on this subject. However I feel that all things are possible!

- MilitantEidolon

in fact, "random numbers" generated by those algorithms are called "pseudo-random numbers", since with they can be predicted with the apropriate effort.

The only "true" random number generators are they made on hardware, using signal/noise that cant be predicted (yet).

Quote:

---

The only "true" random number generators are they made on hardware, using signal/noise that cant be predicted (yet).

---

One could argue that as soon as it can be predicted, it's not random anymore. As soon as the signal/noise you're talking about can be predicted, those random numbers will become nothing but pseudo-random numbers.
Entropic sources are right now an excellent basis for random numbers, but that's only based on the fact that there are so many factors involved that it is too hard to predict it. And as soon as they become predictable (not likely to happen very soon, but possible), there goes your randomness.

Compare it to rolling the dice. Most people would say that that's completely random, but I don't think so: if you take into consideration gravity, the movement of the solar system, the movement of the person throwing the dice, the bounce-factor of the table, the hardness of the dice, wind, and billions of other factors (I guess you could say that the breathing of every single person on this earth manipulates how the dice roll) you don't have randomness anymore.

I don't even believe that there is one source out there that can be called completely random.

Some programs generate their "random" numbers based on the way a person types the input (time between each key stroke). I'm pretty sure this is true for encryption programs such as PGP or GnuPG. Seems like this is a pretty good source of randomness because as someone types in their passphrase, they probably aren't going to type at a completely consistent rate.

As far as Visual Studio goes, I'm pretty sure the clock is used for a seed for random numbers. In VB it uses the Timer variable as a default when no seed is given. This variable holds how many seconds have passed since midnight.

I agree with Negative. I don't think that anything is completely random. But there are some things that are less predictable than others.

Negative, excellent point. Now, I just can't help but reply to this thread. Some time ago, I read a book on chaos physics and your particular response (along with this thread about randomness) reminds me of something called the Lorenz Attractor (strange attractors) and another idea known as the Butterfly Effect (sensative dependence on initial conditions).

Quote:

---

Entropic sources are right now an excellent basis for random numbers, but that's only based on the fact that there are so many factors involved that it is too hard to predict it.

---

Perfect example of the Butterfly Effect. Not only does this work with rolling dice but also many other instances, such as long term weather prediction. The problem being is, that you could have seemingly indentical initial conditions but all it takes it one of the countless factors to change, even if on the smallest of scales, and the outcomes can vary drastically (I refer to a very famous controlled experiment that was attempted to replicate weather patterns based on indentical initial conditions). Predicting these outcomes is nearly impossible simply because of the vast number of factors influencing it.

Quote:

---

if you take into consideration gravity, the movement of the solar system, the movement of the person throwing the dice, the bounce-factor of the table, the hardness of the dice, wind, and billions of other factors (I guess you could say that the breathing of every single person on this earth manipulates how the dice roll) you don't have randomness anymore

---

You're absolutely correct. now if we could just get rid of those annoying billions of factors
:D .
Now, the reason I mention strange attractors is simply because no matter how random something may appear to be, sometimes it still follows a loose pattern. Think of a flag fluttering, cigarette smoke rising from the cigarette, etc. Although the actions may never replicate exactly, they also don't vary drastically either. They seem to follow an observable pattern of some sort. So, it seems that there may exist, a pattern even in the most random of events.

Quote:

---

I don't even believe that there is one source out there that can be called completely random

---

On that, I agree with you. But, applying pattern to something seemingly random to a point where it has a very precise, predictable, behavior? that's another story.

This kinda belongs in cosmos. :)

Randomness is really just our term for any sequence of events that lies beyond the threshold of predictability. "Suitably unpredictable" might be a better term, but I digress.

As for the original point, for now it is random enough to be suitable for our current needs, but as processing power increases it may well be possible to predict things like interference. That being said, there would be other problems with predicting it, and it is (IMO) going to prove to be one of those things that yields diminishing returns.

guys that is some real deep stuff, and i enjoyed reading, esp about the butterfly effect, really interesting stuff, anyways isnt a completly random generated characters could be from a human and not a machine, because not everybody thinks alike and that COULD be completly random, maybe im wrong

The thing that interests me the most about the randomness is how it relates to compression.

There are a lot of factors involved, including what kind of predictability the compression algorithm is designed to remove (RLE off the top of my head, don't know about others), but generally the compressed output is considered to be heavily random. When you can no longer compress something, at least in the scope of the compression algorithm used, that is considered perfectly random. Of course, different algorithms have different points of view on what is random.

To an RLE (Run Length Encoding) algorithm, this is considered perfectly random ("qwertyuiop") while this is not ("qoiipowwittt"). RLE compression detects duplicate characters like "ttt" and can compress them in special ways. I'd imagine that there are other algorithms that would consider the first example to be non-random (it might detect the characters are just a run along the top row of a keyboard) while the second example is somewhat more random since it can't be compressed as much by it besides the duplicate characters. But the compressed output would in the end be considered strongly-random.

Those definitions and limited views on what is random is interesting to me. I'm not going to devote my life to studying it (although I will become an Engineer/Scientist), but whenever I can I love to point those things out. Cheers.


Edit: BTW, interestingly random s/n ;)

Quote:

---

On that, I agree with you. But, applying pattern to something seemingly random to a point where it has a very precise, predictable, behavior? that's another story.

---

Something on the lines of the lack of a pattern being a pattern?

And surely there's no reason to take into account all the factors...consider the rolling dice for example:If you only consider a few 'primary' factors like how the person threw it,the hardness factor etc..you'd be on your way to getting a first degree 'simulation' of your model(throwing the dice in this case)..then,depending on your requirements,you could either make do with your present model or make another simulation taking into account a few more 'secondary' factors and thus getting a higer degree of accuracy in predicting the outcome..ofcourse,to be entirely sure you'd have to make an infinite number of simulations..but you'd only need to get a certain amount so that you could get the accuracy to reasonable proportions,thereby reducing the number of choices..and then trying them all or guessing(anyone think this can be extended to that password idea?)

And yes,I agree..this is fast turning into great cosmos material lol

Hi

as for "pseudo-random numbers":

It has been stated here, random numbers produced by computers are not completely random,
ie they are deterministic, hence they are called "pseudo-random numbers". This of course,
is completely true. A very simple "pseudo-random-generator"-algorithm is

Code:

---

long int a,b,c,d;


// initialisation (set the "seed")

a=14;

// pseudo random generator that generates number between 0 and 100

  for (i...){
        b=23472985;                        // these two numbers define the "random number generator"
        c=394749587;                        // these two numbers define the "random number generator"

        d=a*b % c;                        // typical pseudo-"random number"-algorithm

        a=((d%100)+100)%100;                // a is a random number between 0 and 100. Used as the "next" seed.

  }

}

---

With the same initial seed "a", and the same parameteres "b" and "c" you generate the same "random numbers"
always. The quality of a random generator is measured by two characteristics:
- uniformness of the distribution of "random numbers"
- correlation between the "random numbers"

The above algorithm, I haven't tested it, should generate quite a nice uniformness, if I recall correctly.
However, the correlation between the "random numbers" is very high, ie. after producing some (quite) large
numbers of "random numbers", they start to repeat. Set b and c to small values, like b=123 and c=165 and you
will easily recognise a scheme.

For encryption techniques, for simulations of large systems (using socalled "Monte Carlo" techniques), etc., the
important point for a "pseudo-random generator" is a very large correlation time, ie the time where the numbers
start to repeat. Me for example, I use a "pseudo-random generator" with a correlation time that is orders larger
than the number of atoms within the universe - ie if you do not know the "seed", you cannot use information,
for whatever purpose, coming from the random generator itself. However, your algorithm might be restricted in
some "subspace" such that you can try to obtain additional information, for whatever purpose.
Note: Especially in scientific simulations, the "pseudo-randomness" is a fundamental criterion of a random-generator,
since the published results based on simulations have to be reproducible.


as for chaotic systems:
Chaotic behaviour has nothing to do with randomness and/or unpredictability. This has
been pointed out and illustrated nicely by ShagDevil. Chaotic systems are defined as
systems, as it has been stated here, where solutions are heavily dependent of the initial conditions.
Mathematically (however not rigorously spoken):
If I change the initial conditions by some small number ("neighborhood"),
the solutions have no a priori "neighborhood", ie the solution may change from here to mars.
It's just a mathematical phenomenon, and quite a lot chaotic systems can be solved
or at least described analytically.

as for "complete randomness":
There is indeed a source out there, that is "perfectly" random. Namely, quantum effects. As an example, the
radioactive decay of elements is a purely random process and cannot be "fixed" by knowing ALL involving factors,
as with the example of the flipping coin. Actually, "perfect" random numbers are being generated [1].

I hope, I was not too technical.

Cheers.


[1] http://www.randomnumbers.info/content/Press.htm

sec_ware: Does that source use something related to the double-slit experiment to generate numbers? At least that is all I can get from semi-transparent mirror and light particle and reading the website of the company that made the generator. For those interested in this experiment and wanting to see the results that as far as I know nobody has been able to explain/analyze/predict because they cannot be measured due to quantum mechanics, Wikipedia has an article here: http://en.wikipedia.org/wiki/Double_slit_experiment


Also, that is a code sniplet that explains a lot to me since I'd never have thought about it myself. But why the "a=((d%100)+100)%100;"? Variable d has to be positive to return a number between 0 and 100, and that code sniplet is apparently designed to make it positive. Infact, d=a*b % c; would be wrong if that is the purpose to the a=... part since it would be negative if you intended a to be signed. So make the input unsigned and get rid of the sign changing part in a=... Basically, you want between 0 and 100 so make sure it will always return between those two numbers :p

Hi Tim_axe

ad code-sniplet.
thanks for the hint about the unsigned. of course, you are completely right.
i did the example in 10secs, realised that i have negative d's, and changed
it with that horrible construct. Sometimes, a brain pops up complicated
ideas faster than the simpler ones :D

[slightly off topic]

ad the experiment.
a little clarification to the double-slit experiment: If people think of electrons, they
think in terms of "particles" - and so people tend to describe the properties, like
momentum etc., in terms of the old Newton Law's. Then, around 1920 or so, people
like Schroedinger, Heisenberg and Dirac thought about different ways how to
describe such small particles - quantum theory began to take form.

The reason: More and more experiments could not be explained in terms of particle/waves,
since some experiments with waves have shown clear characteristics of particles, while
experiments with particles have shown clear characteristics of waves
(this is known as "duality of particles and waves") -
like the double-slit experiment:
There is no reason for particles to show some interference-pattern. Hence,
one had to think about the validity of our description of small particles like the electron.
As a result, the Schroedinger equation and Wavefunctions of the electrons were "invented".

Nowadays, the double-slit experiment can be "explained", thanks to Feynman. The solution:
It's the question you ask the system that is reflected in the result...quite metaphysical !

To finish this up: There is no explanation of what they do in that Press article. Although I am
not an expert in quantum electronics I make the following (reasonable ? ) guess: The base
system they use is based on a laser - and here your thought about the double-slit
experiment comes in: in order to get such kind of interference, you need "coherence" in
your light ray ("coherence" is some property of laser-"light") - and within a laser, to "produce"
a laser-"ray", there are processes involving "spontaneous emission" - which is a purely
undeterministic process - like the decay of radioactive material (or a neutron, proton, ...)
This, I guess, can be used to create a series of "perfect" random numbers.

Sideremark: Actually LASER (light amplification by stimulated emission of radiation) is just
one part of the actually "object" we call a "LASER".: It should be called
"light oscillation by stimulated emission of radiation) - but who wants to call its
own device a "LOSER" :D
[/slightly off topic]

A final thought about whether these process "I" claim to be undeterministic really
are undeterministic or seem just so, because we do not know enough. All quantum
theories have one underlying assumption: quantum processes ARE random and
happen as they wish - as long as you do not measure, the system is in ANY possible
state. If it decides to do something, it is a priori not deterministic what it will do.
But what if these quantum theories are wrong? There is no proof, a rigorous proof
in the precise mathematical meaning, of the validity of these theories. However,
so far one can explain every experiment human beings have been able to perform -
based on these theories. As soon as we find one experiment that is violating a
prediction, these quantum theories might be wrong - still, it is not clear, "how" wrong
they then will be.

I followed the links around a bit and ended up here as to what they use to generate the numbers: http://www.idquantique.com/qrng.html

I think this operates by firing a photon at a semi-transparent mirror and seeing where it ends up - does it reflect or go through? They probably opperate fairly continously because they are rated at 4mbit/sec speeds. So I guess it isn't directly related, but in a way it is like finding out which path the photon took and using that as the bit to return.

At 4mbit/sec for keys, you can easily come up with huge non-predictable keys needed for secure symetric-key-encryption. You just need a safe way to get the key from point a to point b :)



Anyways, once again, nice code example. Provided the OP knows some C/C++, you could expand and play from there and have a fair understanding of pseudo-randomness. :)

Hi all, once I stumbled into this link. It is a pretty cool project that uses the randomness and chaos of LavaLamps as a source for generating random numbers. Check it out:

http://www.lavarnd.org/

cheers
-J

Just a quick speculation:

- use a large enough variable [32 bit or 64 bit if it's a primitive type, any size if one build one's own data-types]
- init the first 16 bits with the timestamp
- init the last 16 bits with a collection of bitstates in CPU registers
- permute the bits 'randomly' to the left or right by a 'random' number of bits within the bit space

To get the last two random values:

- left or right choice is a two-state system, therefore a bit value [the function itself called to choose a memory address] indicates either direction
- bit permutation [<< >>] chosen from a modulus of the sum of the int value of some addresses on the RAM against the value of the bit-space.

The appearing 0s [from the permutation] to be filled similarly with one of the above methods.

This just shows how mahy methods there are to write out a pseudo-random algorithm. Schneier considers a 'random enough' number to be part of a sequence who's period is large enough to make it unfeasible, given a seed, to compute one whole period [that is, until the whole sequence repeats itself]. This is by cryptographic standards, and it is far more complex than most application that use random numbers care to have.

P.S. Sorry for the brief post on such a complex subject.

tim_axe: thanks for the link. the process is still not explained, but at least now, we have
an idea (as you already have posted earlier!).

johnnymier: the inventiveness of human beings is astonishing. you also might check out [1].

hypronix: Good that there are people who are able to put

Quote:

---

the
important point for a "pseudo-random generator" is a very large correlation time, ie the time where the numbers
start to repeat.

---

in understandeable words :D


For convenience, I attached a fairly complicated pseudo-random number generator, that
generates random numbers without detecteable correlation time - and it can be arbitrarily
tuned. Credits to the inventor and adaptor are given in the file.

The initialisation of the generator can, for example, be coupled to one of the, meanwhile
3 other devices and/or , as also already mentioned, with the speed of the user typing his
password or whatever additional source, like a microphone input ("wind" in your room...).




[1] http://www.physorg.com/news1147.html