Linear Congruential for Pseudorandom Number

    11 Sep, 2024

    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:

    Nj+1=(ANj+B)%MN_{j+1} = (A * N_{j} + B) \% M

    The most important elements in the LCG are three integers: the multiplier AA, the increment BB, and the modulus MM.

    These values, AA, BB, and MM, are constants set by the generator. The period of the LCG is at most MM, though in most cases, it will be less than MM. To achieve the maximum period, the following conditions must be met:

    • BB and MM are coprime;
    • All prime factors of MM divide A1A-1;
    • If M%4=0M \% 4 = 0, then A1A-1 must also be divisible by 4;
    • AA, BB, and N0N_{0} must be smaller than MM, and AA, BB 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 2322^{32}, 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 MM, the sequence generated by the LCG has a maximum period of MM. Suppose the recursive formula is Nj+1=(ANj+B)modMN_{j+1} = (A * N_{j} + B) \mod M. If the period is TT, then Nk+T=NkN_{k+T} = N_{k}, and since Nk+1=(ANk+B)modMN_{k+1} = (A * N_{k} + B) \mod M, this implies that each value of NkN_{k} uniquely determines the value of Nk+1N_{k+1}. Thus, the period TT must be less than or equal to MM, because there are only MM possible distinct integers when taken modulo MM. The (M+1)(M+1)-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 TMT \leq M.

    Next, it is important that the multiplier and modulus be coprime. This is easy to understand: consider Nj+1=(ANj+B)modMN_{j+1} = (A * N_{j} + B) \mod M. If AA and MM are not coprime, suppose A=adA = a * d and M=mdM = m * d where d>1d > 1. Expanding the recursive formula yields Nj+1=ANj+B+kMN_{j+1} = A * N_{j} + B + k * M. Since BB is constant, it can be treated as a shift, and by subtracting BB from both sides, we get Nj+1B=(a(NjB)+aB+km)dN_{j+1} - B = (a * (N_{j} - B) + a * B + k * m) * d. This shows that all values of Nj+1BN_{j+1} - B contain the factor dd. For example, if d=2d = 2, the sequence of MM possible numbers will only yield even numbers plus the shift BB, meaning the period TM/2T \leq M / 2. This disrupts the uniform distribution of the sequence.

    A few simple examples can illustrate this. Suppose A=3A = 3, M=5M = 5, and N0=2N_0 = 2, the sequence would be {2,1,3,4,2,1,}\{2, 1, 3, 4, 2, 1, \dots\}, with a period of 5. If we set A=6A = 6, M=10M = 10, and N0=2N_0 = 2, the sequence would be {2,2,2,}\{2, 2, 2, \dots\}, 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 MM, 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, AA and BB, start from positions xx and yy respectively, with AA jumping mm units and BB jumping nn units each time. The total circumference of the track is LL. 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:

    (x+mk)(y+nk)(modL)(x + m*k) ≡ (y + n*k) \pmod{L}

    Where denotes congruence modulo LL.

    Expanding this gives:

    x+mk=y+nk+Lkx + m*k = y + n*k + L*k'

    Rearranging terms, we get:

    xy=(nm)k+Lkx - y = (n - m)*k + L*k'

    Thus,

    (xy)(nm)k(modL)(x - y) ≡ (n - m)*k \pmod{L}

    Let nm=an - m = a and xy=bx - y = b,
    yielding the standard linear congruence:

    akb(modL)a*k ≡ b \pmod{L}

    Definition: If aa and bb are integers, the expression axb(modM)a*x ≡ b \pmod{M}, where xx is an unknown integer, is called a linear congruence. Here, and ((modM))(\pmod{M}) indicate that both sides are taken modulo MM.

    To solve a linear congruence, we proceed with the following transformations:

    1. The standard linear congruence axb(modM)a*x ≡ b \pmod{M} is equivalent to the Diophantine equation ax+My=ba*x + M*y = b.
    2. Let dd be the greatest common divisor (gcd) of aa and MM, denoted gcd(a,M)=dgcd(a,M) = d. If the equation has a solution, dd must divide bb. We rewrite the equation as a0x+M0y=b0a_0*x + M_0*y = b_0, where a=a0da = a_0*d, M=M0dM = M_0*d, and b=b0db = b_0*d. Here, a0a_0 and M0M_0 are coprime, meaning gcd(a0,M0)=1gcd(a_0, M_0) = 1.
    3. Let x=x0b0x = x_0*b_0 and y=y0b0y = y_0*b_0. The equation becomes a0x0+M0y0=1a_0*x_0 + M_0*y_0 = 1, or equivalently a0x01(modM0)a_0*x_0 ≡ 1 \pmod{M_0}.

    Finally, we use modular inversion to compute x0x_0.

    Theorem: If aa and MM are coprime integers and M>1M > 1, there exists a unique inverse of aa modulo MM.

    This theorem can be proven as follows:

    Since aa and MM are coprime, there exist integers ss and tt such that sa+tM=1s*a + t*M = 1. (If aa and MM have a common divisor d>1d > 1, then sa+tM=dks*a + t*M = d*k, which cannot equal 1). Taking the equation modulo MM, we get sa1(modM)s*a ≡ 1 \pmod{M}. Thus, ss is the modular inverse of aa modulo MM.

    Let aˉ\bar{a} denote the modular inverse of aa modulo MM, so x0aˉ(modM0)x_0 ≡ \bar{a} \pmod{M_0}, meaning x0aˉ+kM0x_0 ≡ \bar{a} + k*M_0.

    For example:

    To solve 5x7(mod9)5*x ≡ 7 \pmod{9}:

    1. Since gcd(5,9)=1gcd(5,9) = 1, we know that 55 has an inverse modulo 99. Using the extended Euclidean algorithm, we find 25+(1)9=12*5 + (-1)*9 = 1.
    2. Therefore, 22 is the inverse of 55 modulo 99. Multiplying both sides of the original equation by 22 gives 25x27(mod9)2*5*x ≡ 2*7 \pmod{9}.
    3. Simplifying, we get x14(mod9)5(mod9)x ≡ 14 \pmod{9} ≡ 5 \pmod{9}.
    4. Thus, the solution is x=5+9kx = 5 + 9k.

    In summary, we can solve a general linear congruence axb(modL)a*x ≡ b \pmod{L} by transforming it into a standard congruence a0x01(modM0)a_0*x_0 ≡ 1 \pmod{M_0}. After solving the standard congruence, we map the solution back. If the solution to the standard equation is x0{x=p+qM0}x_0 \in \{x = p + q*M_0\}, then the solution to the original equation is x{x=bdp+qM0}x \in \{x = \frac{b}{d}*p + q'*M_0\}.

    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:

    1. 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.
    2. 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.
    3. Non-uniformity: In some cases, LCG-generated sequences may not be uniformly distributed, especially when parameters are poorly chosen, leading to statistical biases.
    4. 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

    class LinearCongruentialGenerator {
      private seed: number;
      private readonly a: number;
      private readonly c: number;
      private readonly m: number;
    
      constructor(
        seed: number,
        a: number = 1664525,
        c: number = 1013904223,
        m: number = 2 ** 32
      ) {
        this.seed = seed;
        this.a = a;
        this.c = c;
        this.m = m;
      }
    
      public next(): number {
        this.seed = (this.a * this.seed + this.c) % this.m;
        return this.seed;
      }
    
      public nextFloat(): number {
        return this.next() / this.m;
      }
    }
    
    // Example usage
    const lcg = new LinearCongruentialGenerator(12345);
    console.log(lcg.next());
    // Outputs a random integer
    console.log(lcg.nextFloat());
    // Outputs a random floating-point number between 0 and 1
    

    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:

    function testRandomness(
      generator: LinearCongruentialGenerator,
      iterations: number = 10000
    ): void {
      const results: number[] = new Array(10).fill(0);
    
      for (let i = 0; i < iterations; i++) {
        const randomValue = Math.floor(generator.nextFloat() * 10);
        results[randomValue]++;
      }
    
      console.log("Randomness Test Results:");
      results.forEach((count, index) => {
        console.log(`${index}: ${"*".repeat(count / 100)}`);
      });
    }
    
    // Example usage
    const lcgTest = new LinearCongruentialGenerator(12345);
    testRandomness(lcgTest);
    

    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.