LINEAR CONGRUENTIAL GENERATORS

Posted: August 26th, 2021

LINEAR CONGRUENTIAL GENERATORS

Name:

Institution:

Date:

1. Define Linear Congruential Generators

A linear congruential generator (LCG) is defined as an algorithm that produces a sequence of pseudo-randomized numbers [1]). Furthermore, these numbers are calculated using a discontinuous piecewise linear equation, which presents the best-known and oldest pseudo-random number generator algorithms. In other words, linear congruential generators represent the pseudo-random number generator algorithms used to generate numbers randomly in a sequence manner[1].

• How Linear Congruential Generator Work (Show the Procedure)?

The Linear Congruential Generator is characterized by recurrence connection:

X_i+1= (aX_i+c) mod m

Whereby

 X = the pseudorandom sequence values

a, the multiplier, a ≥ 0.

m, the modulus; m > X0, m > a, m > c.

c, the increment; c ≥ 0.

X₀, the starting value or the seed; X₀ ≥ 0.

If c ≠ 0, the generator is a mixed congruential generator that causes an affine transformation recurrence and not a linear one. However, inaccuracy caused by this method is well-established in computer science [2]. If c = 0, the method is known as a multiplicative congruential generator. Therefore, the desired random sequence of numbers (X_n) is obtained through:

X_n+1 =(aX_n + c) mod m, n ≥0.

X_n is chosen to be in [0, m-1], n ≥0.

• How Can We Use a Linear Congruential Generator to Generate Seeds in Tracing Application?

Linear congruential generators that generate random numbers are called pseudo-random; since to generate random sequences, they need a seed number[2]. Therefore, linear congruential generators are not all random because of the requirement stated before. However, optimal and theory selection is a suitable choice for tracing applications.

The vital aspect of the Linear Congruential Generator is to generate a random pseudo number based ona number before adding a specific offset, which wraps the outcomes if it exceeds a particular limit [4]. In tracing application, multiple streams of numbers that have random sequences and independent, are implemented for practical use. One way to deal with this problem is to partition a whole time of a single sequence into several long disjoint sub-sequences. Hence, the Linear Congruential Generator often forms forward and backward loops for various sub-sequences and sequences. This property is known as the ‘jumping ahead’ property for Linear Congruential Generator performance in tracing applications[3].

• How Can LCGBe Useful For Tracing Systems? For Example, Security, and Privacy.

The linear congruential strategy has the benefit of being fast, requiring just a couple of operations per call. Hence for tracing systems, using linear congruential generatorsshuffles the outcomes to remove the least critical bit correlations[4]. A programmed random number r_n is not used as the output to achieve the shuffling, rather n-th number israndomized later call.

Furthermore, a linear congruential generator requires the storage of the most recent number value[5]. This is useful for tracing companies since it will help in determining the appropriate information to be used.For tracing systems, Linear Congruential Generators can easily be replicated, according to Glen (2018). For instance, using a similar seed can produce the same grouping over and over, which is amazingly useful for tracing systems.  Furthermore, by utilizing similar numbers, one can either reduce or minimize the fluctuation of difference that would be brought about using various numbers. Any distinction in the correlations is because of the essential difference in the models themselves. According to [2], linear congruential generators help with faster calculations. The count can be performed with a couple of whole number arithmetic instructions. Therefore, this is the reason why LCGs are used in all tracing systems around the globe.

References

[1] Glen S. (2018). Random seed: Definition. Statistics How To. https://www.statisticshowto.com/random-seed-definition/

[2] Entacher, K. (1998). Bad subsequences of well-known linear Congruential pseudo-random number generators. https://www.researchgate.net/publication/228386019_Bad_Subsequences_of_Well-Known_Linear_Congruential_Pseudorandom_Number_Generators

[3] Hallgren, S. (1994). Linear congruential generators over elliptic curves. Carnegie-Mellon University. Department of Computer Science.

[4] Kurlberg, P., & Pomerance, C. (2005). On the periods of the linear congruential and power generators. Acta Arithmetica, 119(2), 149-169. https://doi.org/10.4064/aa119-2-2

[5] Schlegel, A. (2018). Linear Congruential generator for pseudo-random number generation with R. Aaron Schlegel’s Notebook of Interesting Things. https://aaronschlegel.me/linear-congruential-generator-r.html