Today we’re going to talk about random numbers.

If you have learned programming for random numbers should be no stranger, should be more or less used. In addition, our weekly lottery is selected by random number. When we use random number, we often add a prefix to say that it is a pseudo-random number. Then how to explain the pseudo-word of this pseudo-random number and what is a true random number?

True or false random number

At present, the way to divide the true and false random numbers in the academic world is very simple. In a word, it can be said that all the random numbers generated by certain algorithms and procedures are pseudorandom numbers, and the random numbers generated by physical phenomena are true random numbers. That is, computational scientists have proved that algorithms alone cannot generate truly random numbers, which can also be considered an NP problem.

The proof that algorithms generate pseudo-random numbers is too complicated for us to go into, but what are random numbers generated by physical phenomena? And it’s really easy. A very simple example is flipping a coin and rolling a die. Of course, there are more physical phenomena, such as the noise of electronic components, the decay of elements and so on.

What’s the biggest difference between true and false random numbers? It’s all about predictability. The reason why various random numbers obtained by computer algorithms are pseudo-random numbers is that their results are predictable. As long as we know the algorithm, initial state and various parameters, we can predict the next random result. Truly random numbers are unpredictable and purely random.

But are physical phenomena like flipping coins and rolling dice really random? If we know the initial state of the coin and the Angle and force of the toss, can we predict the outcome of the coin toss? Further, can we assume that if we can know all the states of all the examples, are all so-called random numbers predictable? But according to the uncertainty principle of quantum mechanics, we know that we can’t know both the particle’s position and momentum, which means not only that we can’t predict it, but that we can’t assume it.

So it’s kind of a philosophical question whether physics is really random. But at least in the computer world, the problem is clear, algorithms are all pseudo-random numbers, only physics is truly random.

In computer systems, pseudorandom numbers have periods, which we can see if we hold them enough times. However, there is no such cycle for true random numbers. A senior did a random number visualization experiment, that is, to make the results of random numbers into pictures. We can intuitively compare, this is the true random number visualization after the picture:


Does that look like what old TVS used to show when they lost reception? Let’s take a look at the visualization results of pseudo-random numbers generated by the algorithm:


The comparison is still quite obvious. It is obvious that the pseudo-random number has a rule, which is reflected in the texture of the image. If you want to get a truly random number, you can visit random.org, which is free. You can set a limit or upper limit to get a random number within a specified range.

After comparing true and false random numbers, we will look at the principle of pseudo-random number generation algorithm commonly used in computer systems.

Square the middle

We first introduced is the square method, this method is very simple and crude, is used to generate four random numbers.

What’s the logic? So first we need a random seed, say 2333, and then we square this random seed, and we get 5442889. This number has six digits, so we fill it with a 0 to the left and it becomes 05442889, and then we take the middle four digits and it’s 4428, and that’s what we get randomly. The next time we calculate the random number, the seed of the random number will be 4428.

The algorithm was written by von Neumann, the father of computing, and has been used ever since he defined the architecture of computing. The reason he favored it at the time was simple: it was easy to calculate, fast, and easy to detect errors. It argues that if you really design a complex algorithm to generate random numbers that look good, you might hide more bugs than you solve.

seed = 2333
def random(a):
    global seed
    seed = seed ** 2
    return int(str(seed)[1:5])
Copy the code

I wrote the code and actually ran it, and it didn’t look that crazy.


LCG algorithm

Although von Neumann’s random number algorithm looks simple, it is very sloppy and obviously cannot be used in many situations. So people came up with a new algorithm, this algorithm is also very simple, it looks like the English abbreviation is tall, in fact, the translation isLinear congruence method. That is to take advantage ofTo generate random numbers.

The final result is the result of the above calculation, and the three numbers ABC are the parameters we selected. The next time it is random, the last result is computed as the new seed. Let’s write the recursion formula for this:


The algorithm can be seen at a glance, and its core lies entirely in the choice of the three parameters ABC. A =25214903917, b=11, c=. These numbers are not just picked on the fly, they are calculated by mathematicians. In factRandom’s class in the Java JDK uses such an algorithm.

seed = 2
def lcg(a):
    global seed
    seed = (25214903917 * seed) & ((1 << 48) - 1)
    return seed
Copy the code

This algorithm is also very simple, and the results are good. If we want to increase randomness, we can also make some optimizations on the output, such as shifting or switching the order of the bits. However, this algorithm also has disadvantages, that is, its calculation method is fixed, but the random seed is unknown. If we want to, we can deduce these parameters from the random results we get.

This is not a complex algorithm, so the random numbers obtained by THE LCG algorithm cannot be applied to some high-security applications, otherwise there may be security risks.

Mason rotation algorithm

LCG algorithm achieves good pseudo-random number effect, but the cycle is not long enough, and it is easy for hackers to calculate random seeds. Later, two Japanese scholars studied and proposed a new pseudo-random number algorithm, in which mersenne prime number is used, so it is called Mersenne rotation algorithm.

A few words about mersenne primes, mersenne primes means likeA prime number. Using the properties of Mersenne prime numbers, we can design random number periods with mersenne prime length. For example, Python, C++11 and other languages used in the random number calculation package are used by this algorithm. The current version cycle isThis is a huge astronomical figure.

The realization principle of Masons rotation algorithm is very complicated, and there are not many materials on the Internet. I have read some of them and they are not very easy to understand. I will not introduce it here, you can go to see if you are interested. But PERSONALLY, I don’t think it makes much sense, because it’s really useless, and you don’t have to do an interview.

Although mersenne rotation algorithm has a very long period, it is still not a secure random number algorithm and may still be cracked by hackers. However, compared with LCG algorithm, the probability and difficulty of cracking have increased a lot.

You might be wondering, what kind of algorithm is safe? In fact, the industry’s security algorithm is actually quite clever, the general common method is to use a mathematical problem to design an algorithm. The RSA encryption algorithm, for example, exploits the problem of factoring large integers. There is no good method for such problems in the industry except violent calculation, and the complexity of violent calculation is very, very high, it is impossible to have a solution in a limited time, naturally this is a safe algorithm. If a hacker is able to design an algorithm to crack it, he doesn’t need to crack it at all. He can just publish his solution in a paper and get fame and fortune.

When you look at the deep scientific principles hidden behind such a common function as random numbers, it is even more shocking that our civilization is so advanced that we can’t even do a random number. I wonder how you feel when you see this?

That’s all for today’s article. I sincerely wish you all a fruitful day. If you still like today’s content, please join us in a three-way support.

Original link, ask a concern

This article is formatted using MDNICE