Linear congruential method is a pseudo-random number generation method that generates a random number sequence based on a deterministic mathematical algorithm.
Algorithm Overview
Programmers are generally familiar with random numbers, and it is well-known that the random numbers generated by computers are often pseudo-random. What exactly is a pseudo-random sequence?
Pseudo-random numbers are a sequence of numbers that appear random but are generated using a deterministic algorithm, meaning they are not truly random.
Since randomness is simulated through an algorithm, what kind of algorithm can achieve an effect close to true randomness, and how does it work?
One of the simpler methods is the linear congruential generator (LCG).
The LCG is based on the recursive formula:
The most important elements in the LCG are three integers: the multiplier , the increment , and the modulus .
These values, , , and , are constants set by the generator. The period of the LCG is at most , though in most cases, it will be less than . To achieve the maximum period, the following conditions must be met:
- and are coprime;
- All prime factors of divide ;
- If , then must also be divisible by 4;
- , , and must be smaller than , and , must be positive integers.
The advantage of the LCG is that it is very easy to implement and generates numbers quickly. However, its drawback is also clear: for a 32-bit number, the maximum period is limited to , which is inadequate for applications that require high-quality random numbers, such as cryptography.
Randomness Analysis
With this understanding, one might wonder, how does the LCG simulate a random process? True randomness implies that any number can appear, meaning all outcomes are equally probable, following a uniform distribution. So, how does the LCG achieve uniform distribution?
First, we need to understand the period of the LCG. From the definition above, it is clear that for a modulus , the sequence generated by the LCG has a maximum period of . Suppose the recursive formula is . If the period is , then , and since , this implies that each value of uniquely determines the value of . Thus, the period must be less than or equal to , because there are only possible distinct integers when taken modulo . The -th number will necessarily be the same as one of the previous numbers, and since the recursive relationship is one-to-one, the subsequent sequence will repeat, leading to a period .
Next, it is important that the multiplier and modulus be coprime. This is easy to understand: consider . If and are not coprime, suppose and where . Expanding the recursive formula yields . Since is constant, it can be treated as a shift, and by subtracting from both sides, we get . This shows that all values of contain the factor . For example, if , the sequence of possible numbers will only yield even numbers plus the shift , meaning the period . This disrupts the uniform distribution of the sequence.
A few simple examples can illustrate this. Suppose , , and , the sequence would be , with a period of 5. If we set , , and , the sequence would be , with a period of 1.
Returning to the initial question, how does the LCG achieve uniform distribution? As seen from the discussion above, with carefully chosen parameters, it is possible to construct a sequence with a period of , where each number appears exactly once in each cycle. This ensures that the frequency of appearance for each number in the sequence is the same, thus satisfying the uniform distribution requirement.
Solving Linear Congruences
Having understood the relationship between random distribution and the linear congruential method, let's extend our knowledge to learn how to solve linear congruences. This is not just a theoretical mathematical problem; it has numerous practical applications. For instance:
On a circular track, two frogs, and , start from positions and respectively, with jumping units and jumping units each time. The total circumference of the track is . If both frogs start at the same time, they are said to meet if they land on the same point. The question is, after how many jumps will the two frogs meet at the earliest?
Based on these conditions, we can formulate the following equation:
Where denotes congruence modulo .
Expanding this gives:
Rearranging terms, we get:
Thus,
Let and ,
yielding the standard linear congruence:
Definition: If and are integers, the expression , where is an unknown integer, is called a linear congruence. Here, and indicate that both sides are taken modulo .
To solve a linear congruence, we proceed with the following transformations:
- The standard linear congruence is equivalent to the Diophantine equation .
- Let be the greatest common divisor (gcd) of and , denoted . If the equation has a solution, must divide . We rewrite the equation as , where , , and . Here, and are coprime, meaning .
- Let and . The equation becomes , or equivalently .
Finally, we use modular inversion to compute .
Theorem: If and are coprime integers and , there exists a unique inverse of modulo .
This theorem can be proven as follows:
Since and are coprime, there exist integers and such that . (If and have a common divisor , then , which cannot equal 1). Taking the equation modulo , we get . Thus, is the modular inverse of modulo .
Let denote the modular inverse of modulo , so , meaning .
For example:
To solve :
- Since , we know that has an inverse modulo . Using the extended Euclidean algorithm, we find .
- Therefore, is the inverse of modulo . Multiplying both sides of the original equation by gives .
- Simplifying, we get .
- Thus, the solution is .
In summary, we can solve a general linear congruence by transforming it into a standard congruence . After solving the standard congruence, we map the solution back. If the solution to the standard equation is , then the solution to the original equation is .
Through this, we have outlined the process of solving linear congruences and deepened our understanding of the linear congruential method.
Insecurity of the Linear Congruential Method
The linear congruential method (LCG) is a pseudo-random number generation technique based on deterministic mathematical algorithms. Although it can meet the needs for general pseudo-random numbers, it is not suitable for high-security applications, such as cryptography or applications requiring strong randomness. Below are some key considerations regarding the insecurity of LCG:
- Determinism: LCG is deterministic, meaning that the same seed and parameters will always produce the same sequence of random numbers. This poses a security risk, as an attacker could reproduce the sequence by guessing the seed and parameters, breaking the randomness.
- Periodicity: The random number sequences generated by LCG are periodic. Once the sequence reaches its period, it starts repeating. This periodicity can cause problems in applications that require long-term randomness.
- Non-uniformity: In some cases, LCG-generated sequences may not be uniformly distributed, especially when parameters are poorly chosen, leading to statistical biases.
- Security: LCG is unsuitable for cryptographic or high-randomness security applications. For such use cases, cryptographically secure pseudo-random number generators (CSPRNGs) must be employed.
In conclusion, while LCG can be used for general pseudo-random number generation in simulations, games, or random testing, it should not be used in applications that require high security and strong randomness.
Code Implementation
Below is the implementation of a Linear Congruential Generator (LCG) using TypeScript, along with a simple program to test the effectiveness of its randomness.
LCG Implementation
Code to Test Randomness
We can test the randomness of the generator by generating a set of random numbers and plotting their distribution. Below is a simple test program:
This test program generates a set of random numbers and counts the occurrences of each number. By observing the distribution of the output, we can make an initial assessment of the randomness of the generator.