This blog post explains the limitations of computer-generated random numbers, the nature of randomness, and the difference between TRNG and PRNG in an easy-to-understand manner.
“If there is one thing computers are bad at, it’s tossing a coin.” That’s what Steve Wards, a professor of computer science at MIT, said. He said that today’s computers can only process the conditions that humans have set, according to the algorithm, which is a way of processing the conditions, so it is difficult for computers to show the randomness that can be expected from a coin toss. Computers can process millions of pieces of data through numerous complex calculations and precise predictions, but “randomness” remains a difficult challenge because it requires an element of unpredictability. This is why the computer’s processing method is based on the values entered by a person. So how can we overcome this limitation?
However, random numbers are essential for many programs that are closely related to our lives. Examples include OTP, which is often used for security, and gacha items, which are one of the main sources of income for many game companies. OTP strengthens security by generating a new number every time you log in, and games provide unpredictable excitement to users by randomly providing rewards through the gacha system. Numbers with this kind of randomness are becoming an essential element in various fields. This raises the question of how to make computers output “random” numbers that are “easy for us to use.” The most basic principle is to observe and record random factors and use the data. Modern science has advanced to the point where it can accurately predict many phenomena, but there are still many phenomena that humans cannot accurately predict. By observing this phenomenon, it is as if we are “borrowing” random elements that occur in nature and assigning random numbers to the computer. For example, the site random.org observes the noise in the air and uses the results to derive and provide us with random numbers. Devices, programs, etc. that generate random numbers in this way are collectively referred to as True Random Number Generators (TRNGs).
However, generating and using completely random numbers is another matter. The numbers generated by a true random number generator (TRNG) are completely random and cannot be predicted by any human, but there are two challenges to using them right away. First, the speed at which the numbers are output cannot exceed the speed at which they are measured, so some TRNGs may not be able to do their job when a large number of numbers are needed in a short period of time. For example, if there is a TRNG that throws a coin 10 times per second and records 1 for heads and 0 for tails, this TRNG is not suitable for use when 1000-digit binary random numbers are needed within 10 seconds. Another problem is that the numbers are too random to be reproduced in another space or at another time. If it is difficult to reproduce, there are problems with ease of use, such as difficulty in consulting when there is an error in a program related to numbers, or difficulty in sharing the “key” when TRNG is applied to security.
That is why many companies and organizations use PRNG (Pseudo Random Number Generator) in addition to TRNG when generating random numbers. PRNG is an algorithm that basically uses a single number taken from another source to create the next number, uses that number to create the next number, and repeats the process of using that number to create another number. While PRNGs provide randomness, they have repetitive patterns due to the nature of their algorithms. Therefore, to compensate for this, the seed is set to the value of the TRNG to enhance the randomness of pseudo-random numbers.
If you only look at the information so far, it seems that any algorithm can be used as a PRNG if it meets the basic conditions. However, there are two decisive reasons why you should not use any algorithm as a PRNG. The first reason is that the output values of all algorithms eventually become cyclical. PRNGs go through the following process: [Enter a number → Process it in a fixed way → Output the number corresponding to the processed result → Enter another number using the output number → Process it in a fixed way →…]. Due to the limitations of computer programs, the range of numbers used in all input and output steps is limited. Because of this restriction, during the repetition of the same process, there comes a time when “the other number using the output result” becomes the same as “the value received by entering it previously.” From this point on, the numbers that came out before start to come out again, and the numbers that are output become predictable numbers instead of random numbers. This is a limitation of all algorithms, but it is obvious that an algorithm that has been designed to prevent such cycles as much as possible is more valuable as a random number generator than one that has not.
The second reason is that if you use any algorithm, you may end up with a number that never appears among the numbers in the output range. This makes it difficult to write code. For example, let’s say you give 100 people numbers from 1 to 100 in order of their height and use a computer program to pick a number between 1 and 100 and give 100,000 won to the person whose number is that number. If the PRNG algorithm used at this time does not produce the numbers 88 and 99 due to its limitations, this is a violation of fairness. This is not the only case, but if such an error occurs in some fields that require sophisticated random numbers, it can lead to fatal consequences.
Therefore, the algorithms that are usually used as PRNGs are elaborately created with the essence of modern mathematics and modern computer science, so that the cycles are far apart, which is the same as not cycling. In addition, all numbers within the output range appear, and furthermore, the frequency at which all numbers appear is even. The Mersenne Twister, a PRNG created in 1997 and still used in many fields today, has a period of ((2^19937)-1), so although there is a cycle, in theory, all computers on Earth could use it until the end of the universe without ever seeing a cycle of the number, and it has the same distribution in 623 dimensions, so all numbers will appear an equal number of times.
Through TRNG and PRNG, we can use random numbers on a computer. Simply put, since the computer cannot do the coin toss itself, we can have the computer process the coin toss that takes place elsewhere. Random number-based technology is readily available everywhere, but behind it is the hard work of countless people who have faced this problem in the past and worked to solve it. If you occasionally use OTP or buy a gacha item and remember this article, I hope you will thank those people at least once.
