How is a random number generated at runtime?

Question

Since computers cannot select random numbers (can they?), How is a random number actually generated. For example, in C # we say

Random.Next() 

What is going on inside?

Answer 1

You can check out this article . According to the documentation, the specific implementation used in .NET is based on the Donald E. Knuth random number generator algorithm. For more information, see D. E. Knut. "The Art of Programming, Volume 2: Seven-Dimensional Algorithms." Addison-Wesley, Reading, MA, Second Edition, 1981 .

Answer 2

Since computers cannot select random numbers (can they?)

As others have noted, "Random" is actually a pseudo-random. To answer your question in brackets: yes, computers can choose truly random numbers. This is much more expensive than the simple integer arithmetic of a pseudo random number generator and is usually not required. However, there are applications in which you must have unpredictable true randomness: cryptography and online poker immediately come to mind. Using a predictable pseudo-randomness source, attackers can more easily decrypt / fake messages, and cheaters can figure out who they have in their hands.

There are methods in crypto.NET classes that provide random numbers suitable for cryptography , or games in which money is on the line. As for how they work: the literature on cryptocurrency randomness is vast; consult any good cryptography study guide at the university.

Special equipment also exists for receiving random bits. If you need random numbers derived from atmospheric noise, see www.random.org.

Answer 3

Knut is very good at randomness.

We are not very good at randomness. How can one be predictably random? Still, pseudo-random sequences may seem completely random in statistical tests.

There are three categories of random number generators, which are amplified in the comments above.

First, you have pseudo-random number generators, where if you know the current random number, it is easy to calculate the following. This makes it easy to convert other numbers if you learn a few.

Then there are cryptographic algorithms that make this a lot more complicated. I believe that they are still pseudo-random sequences (unlike what is implied in the comment above), but with the very important property that knowing several numbers in a sequence does NOT make it obvious how to calculate the rest. The way it works is that crypto procedures tend to hash the number, so if one bit changes, each bit can equally change as a result.

Consider a simple modular generator (similar to some implementations in C rand ())

int rand () {return seed = seed * m + a; }

if m = 0 and a = 0, this is a lousy generator with a period of 1: 0, 0, 0, 0, .... if m = 1 and a = 1, this is also not a very random form: 0, 1, 2, 3, 4, 5, 6, ...

But if you choose m and a for primes around 2 ^ 16, it will affect the beautiful looking very random if you accidentally inspect it. But since both numbers are odd, you will see that the low bit will switch, i.e. The number will be too odd and even. Not a big random number generator. And since there are only 2 ^ 32 values ​​in a 32-bit number, by definition after 2 ^ 32 iterations, you repeat the sequence again, making it obvious that the generator is NOT random.

If you think of medium bits as good and scrambled, while lower bits are not so random, then you can build a better random number generator from several of them, with different XORed bits together, so that the whole bit is well covered. Something like:

(rand1 () → 8) ^ rand2 () ^ (rand3 ()> 5) ...

However, each number is switched synchronously, which makes it predictable. And if you get two consecutive values, they are correlated, so if you build them, you get the lines on the screen. Now imagine that you have rules that combine generators, so that sequential values ​​are not as follows. for example

v1 = rand1 () → 8 ^ rand2 () ... v2 = rand2 () → 8 ^ rand5 () ..

and imagine that the seeds are not always moving forward. Now you are starting to do something much more difficult for reverse engineering forecasting, and the sequence is longer.

For example, if you calculate rand1 () each time, but only push the seed to rand2 () every third time, the generator that combines them may not repeat much longer than the period of one of them.

Now imagine that you are pumping your (rather predictable) random number generator modulo type through DES or some other encryption algorithm. This will copy the bit.

Obviously there are better algorithms, but this gives you an idea. Numerical Recipes implements many algorithms implemented in code and explained. One very good trick: to generate not one, but a block of random values ​​in the table. Then use an independent random number generator to select one of the generated numbers, generate a new one and replace it. This disrupts any correlation between adjacent pairs of numbers.

The third category is the actual hardware random number generators, for example, based on atmospheric noise

http://www.random.org/randomness/

This, according to modern science, is truly random. Perhaps someday we will find that it obeys some basic rule, but at present we cannot predict these values, and they are “truly” random, as far as we know.

The boost library has excellent C ++ implementations of Fibonacci generators, acting kings of pseudo-random sequences, if you want to see some source code.

Answer 4

I will just add the answer to the first part of the question (the "maybe?" Part) .h

Computers can generate (well, generate, perhaps not quite an exact word) random numbers (as in, not pseudorandom ones). In particular, using random randomness obtained through specialized hardware devices (which generate randomness based on noise, for example, for example), or using environmental inputs (for example, hard disk timings, user input timeouts).

However, this does not affect the second question (how does Random.Next() ).

Answer 5

The Random class is a pseudo random number generator .

This is basically an extremely long, but deterministic repeating sequence. "Chance" comes from the beginning in different positions. An indication of where to start is done by selecting seed for a random number generator and can, for example, be done using system time or by obtaining a random seed from another random source. the default random event constructor uses system time as a seed.

The actual algorithm used to generate the sequence of numbers is described on MSDN :

The current implementation of the Random class is based on the algorithm of the random number generator Donald E. Knuth. For more information see DE Knuth. "The Art of Programming, Volume 2: Seven-Dimensional Algorithms." Addison-Wesley, Reading, MA, Second Edition, 1981.

Answer 6

Computers use pseudo random number generators . In fact, they work, starting with the seed number and repeating it using the algorithm every time a new pseudorandom number is required.

The process, of course, is completely deterministic, so the given seed will generate exactly the same sequence of numbers every time it is used, but the generated numbers form a statistically uniform distribution (approximately), and this is fine, since in most cases all you need This is an accident.

It is common practice to use the current system time as a seed, but if more security is required, the entropy can be collected from a physical source, such as disk latency, to generate a seed that is harder to predict. In this case, you also want use a cryptographically strong random number generator such as this .

Answer 7

I don’t know a lot of details, but I know that a seed is used to generate random numbers, and then based on some algorithm that uses this seed to get a new number.

If you get random numbers based on one seed, they will be the same.