Linear Congruential Generator Method | Random Numbers

Summary

This video script delves into the Linear Congruential Generator (LCG), a popular algorithm for generating pseudo-random numbers. It explains the concept of congruence as the foundation for LCG, where a sequence of numbers is generated using a recurrence relation involving a large integer 'm', multiplier 'a', increment 'b', and a seed 'x0'. The script provides an example with specific values for 'm', 'a', 'b', and 'x0', demonstrating how to generate a sequence of pseudo-random numbers. It also touches on the generation of random bit sequences from these numbers and briefly discusses the security implications of using such sequences in cryptographic applications, hinting at the 50-50 vulnerability of the method.

Takeaways

• 🔢 The Linear Congruential Generator (LCG) is a method for generating pseudo-random numbers, which are essential for simulations and cryptography.
• 📚 The concept of congruence is fundamental to understanding LCGs, where 'a is congruent to b mod n' means n divides the difference between a and b.
• 🌰 An example of congruence is 12 being congruent to 0 mod 4, as 4 divides 12.
• 🔑 In LCGs, a large integer m, and two integers a and b are chosen, along with a seed value x₀, to generate a sequence of numbers using the formula: xi ≡ a * xi-1 + b (mod m).
• 🔄 The sequence generated by LCGs is a recurrence relation that allows for the calculation of subsequent numbers based on the previous one.
• 📈 An example provided in the script uses m=123, a=5, b=2, and x₀=73 to demonstrate the generation of pseudo-random numbers.
• 🔄 The script explains that the output of the LCG can be reduced by taking the modulo with respect to the chosen large integer m, ensuring the sequence remains within a manageable range.
• 🤔 The script mentions the possibility of generating random bit sequences from the LCG output, which can be useful for cryptographic applications requiring a stream of zeros and ones.
• 🔒 However, the script also points out that the method of generating bits from LCG is not very secure, as the predictability of the next bit is 50%, making it half secure and half vulnerable.
• 🚀 The script promises to discuss the Blum Blum Shub pseudo-random bit generator in a subsequent video, which is another method for generating random bits for cryptographic purposes.

Q & A

What is the purpose of using pseudo random numbers in simulations and cryptography?

Pseudo random numbers are used in simulations to mimic the randomness required for various processes and in cryptography to enhance security through unpredictability, as generating true random numbers is difficult and costly.

What was the algorithm discussed in the speaker's last video for generating random numbers?

The speaker discussed the mid square algorithm in their last video as a method for generating random numbers.

What is the mathematical concept of congruence, and how is it related to the linear congruential generator?

Congruence is a concept in number theory where two numbers are said to be congruent modulo n if n divides their difference. It is fundamental to the linear congruential generator, which uses a recurrence relation involving multiplication, addition, and modulo operations to generate a sequence of pseudo random numbers.

What are the components of the linear congruential generator formula?

The components of the linear congruential generator formula are a large integer m, two integers a and b, and a seed value x₀. The formula is xi ≡ a * xi-1 + b (mod m).

Why is the linear congruential generator called 'linear'?

The linear congruential generator is called 'linear' because the recurrence relation it uses to generate numbers has a linear form in terms of the seed value and the constants a and b.

What is the significance of choosing a large integer m for the linear congruential generator?

Choosing a large integer m for the linear congruential generator helps to increase the period of the generated sequence, making it less predictable and more suitable for applications like cryptography that require a high level of randomness.

Can you provide an example of how the linear congruential generator formula is applied?

An example given in the script uses m=123, a=5, b=2, and x₀=73. The formula is applied iteratively to generate subsequent numbers in the sequence, such as x1 ≡ 5 * 73 + 2 (mod 123), resulting in x1=121.

How can the generated pseudo random numbers be used to create a bit sequence?

The generated pseudo random numbers can be reduced modulo 2 to create a bit sequence. For example, if a number is odd, it would be congruent to 1 (mod 2), and if it is even, it would be congruent to 0 (mod 2).

What is the security level of the pseudo random bit sequence generated by the linear congruential generator?

The security level of the pseudo random bit sequence generated by the linear congruential generator is considered to be 50% secure and 50% vulnerable, as the probability of correctly guessing the next bit is 50%.

What will be discussed in the speaker's next video?

In the next video, the speaker will be discussing the Blum Blum Shub pseudo random bit generator, which is another method for generating random bits used in cryptographic applications.

Outlines

00:00

🔢 Introduction to Linear Congruential Generator

The video script begins with an introduction to the Linear Congruential Generator (LCG), a method used for generating pseudo-random numbers. The presenter explains the necessity of random numbers in simulations and cryptography, and acknowledges the impracticality and high cost of producing truly random numbers. The concept of congruence is introduced as a foundational element for understanding LCG, with examples provided to illustrate how numbers can be congruent modulo n. The script also mentions a previous video on the mid-square algorithm, another method for generating random numbers, and encourages viewers to review additional materials on congruences for a deeper understanding.

05:02

📚 Generating Pseudo-Random Numbers with LCG

This paragraph delves into the specifics of the Linear Congruential Generator algorithm. The presenter outlines the formula for generating numbers in the sequence, which involves a large integer m, multiplier a, increment b, and a seed value x0. The process of generating subsequent numbers in the sequence using the formula x_i ≡ a*x_(i-1) + b (mod m) is explained, with an example given using m=123, a=5, b=2, and x0=73. The example demonstrates how to calculate the next numbers in the sequence and emphasizes the recurrence relation that allows for the generation of a series of pseudo-random numbers.

10:04

🔑 Pseudo-Random Number Generation and Bit Sequences

The third paragraph continues the discussion on LCG, focusing on the generation of pseudo-random numbers and their application in producing bit sequences. The presenter explains how the generated numbers can be reduced modulo 2 to create a sequence of bits, which is crucial for certain cryptographic algorithms like stream ciphers. The example from the previous paragraph is used to demonstrate this process, showing how each generated number corresponds to a bit (1 for odd, 0 for even). The paragraph concludes with a brief mention of the security implications of using such a method, noting that while it is 50% secure, it is also 50% vulnerable, indicating the need for more robust methods in cryptographic applications.

Keywords

💡Linear Congruential Generator

A Linear Congruential Generator (LCG) is an algorithm that generates a sequence of pseudo-random numbers using a linear equation. It is defined by the recurrence relation X(i+1) = (a*X(i) + b) mod m, where a, b, and m are constants, and X(0) is the seed. In the video, the LCG is explained as a method to produce random numbers efficiently for use in simulations and cryptographic algorithms.

💡Pseudo-random Numbers

Pseudo-random numbers are numbers that appear random but are generated by a deterministic process. In the video, they are discussed as a more practical alternative to true random numbers, which are difficult and expensive to produce. The LCG is a common method to generate these pseudo-random numbers.

💡Congruence

Congruence is a concept in number theory where two numbers are said to be congruent modulo a third number if they leave the same remainder when divided by that number. The video explains that this concept is crucial for understanding how the LCG works. For example, 12 is congruent to 0 mod 4 because both 12 and 0 leave the same remainder when divided by 4.

💡Seed

A seed in the context of random number generation is an initial value used to start the sequence. The video uses the example of X(0) = 73 as the starting point for generating the subsequent numbers in the LCG. The choice of seed can significantly affect the sequence of numbers produced.

💡Modulus

The modulus (denoted as mod) is a mathematical operation that finds the remainder when one number is divided by another. In the LCG formula, it is used to ensure the numbers stay within a certain range. For instance, in the example provided, calculations are performed modulo 123.

💡Cryptography

Cryptography is the practice of securing information by transforming it into an unreadable format, only to be converted back to a readable format by someone possessing the key. The video mentions cryptography as one of the applications where pseudo-random numbers generated by LCGs are utilized.

💡Recurrence Relation

A recurrence relation is an equation that recursively defines a sequence of values. Each term is defined as a function of the preceding terms. The LCG formula X(i+1) = (a*X(i) + b) mod m is an example of a linear recurrence relation, generating each new number based on the previous one.

💡Random Bit Sequence

A random bit sequence is a sequence of bits (0s and 1s) that appears random. In the video, after generating pseudo-random numbers using the LCG, these numbers are further transformed into random bit sequences using modulo 2 operations, which are useful in various cryptographic applications.

💡Stream Cipher

A stream cipher is a method of encryption where plaintext digits are combined with a pseudo-random cipher digit stream. In the video, stream ciphers are mentioned as a use case for random bit sequences, highlighting the importance of generating secure random bits.

💡Blum Blum Shub

Blum Blum Shub is a cryptographic pseudo-random number generator considered more secure than LCGs. The video briefly mentions that the next topic will cover Blum Blum Shub, indicating its relevance in producing secure random numbers for cryptographic purposes.

Highlights

Introduction to Linear Congruential Generator for generating random numbers.

Explanation of why random numbers are essential for simulations and cryptography.

Differentiation between true random numbers and pseudo random numbers due to computational feasibility.

Introduction to the concept of congruence as a foundation for the algorithm.

Definition of congruence with an example involving numbers 12 and 4.

Illustration of congruence with different numbers like 11 and 3 modulo 4.

Explanation of how congruence can be used to generate a sequence of numbers.

Description of the Linear Congruential Generator formula and its parameters m, a, b, and x0.

Example calculation using the Linear Congruential Generator with specific values for m, a, b, and x0.

Process of generating subsequent numbers in the sequence using the formula.

Discussion on the use of the generated numbers in cryptographic applications.

Generation of pseudo random numbers and their limitations in security.

Conversion of generated numbers into a bit sequence for use in cryptographic algorithms.

Analysis of the security level of the generated bit sequence and its vulnerability.

Introduction to the Blum Blum Shub pseudo random bit generator for the next video.

Summary of the Linear Congruential Generator's method and its practical applications.

Transcripts

in this video i'll be explaining linear

congruential generator for generating

random numbers

in my last video i have explained why

random numbers are required we do

require them for the various simulation

processes

and also in various cryptography

algorithms

so in my last video i have taken up

random numbers which are specifically

pseudo random numbers because it is

difficult to generate the

true random numbers and the experiment

cost us a huge

so rather than doing this we create or

we generate the random number through

certain computer algorithms

and the last algorithm that i have

talked about generating random number is

mid square algorithm now in this linear

congruential generating function

i will be requiring a concept of

congruence

which i have explained in my number

three videos i've added the link in the

description

so for an easy recall of what is

congruence

we can say that a is congruent to b

modulo n whenever n

divides a minus b so this line i will

read it as

n divides a minus b so for example

i can consider here let's take 12

and in the model i i will consider say

for example

4 so now i want to keep something here

so i can say 12 is congruent to 0 mod 4

because whenever we

subtract these two so rather we take a

minus b

or b minus a it doesn't matter because

if n divides some integer it also

divides negation of the integer

so if 4 divide 12 this is

a fine congress i can also say if i have

11 here

11 is congruent to either minus 1

because you can take minus 1 on this

side

and so this will become mod 4

so here you can say 4 divide 11

minus of minus 1 that is 12. in that

case also this congress is true

or i can also say that 11 this is

congruent to

3 mod 4 so because 11

minus 3 this is 8 and 4 divides 8.

now so this doesn't give us a unique

answer but yeah in case we want a

positive integer here so this would be

considered as a remainder whenever we

divide

this 4 by 11. so in that case you may

consider this as a unique

but we can also see a relation between

these two integer

and here we can see that minus 1 is also

congruent to 3

either you take this minus 1 on this

side it will become plus 1 or we take

3 on this side it will become minus 4

and so it is congruent to

4. so this is the normal concept of the

congruences

and there are various videos associated

with the congruences that you can look

for the further properties

now i'm going to use this type of

concept to explain what is linear

congruential generator so let m be the

large

integer i am just considering a large

integers

now for the random numbers we require

in case you are taking a cryptographic

application you do require the large

number so here i'm just taking m to be

large integers

and choose two integers a and b

so we selected two integers a and

b and i select a seed which i call it as

x naught and we defined a sequence

which sequence is related using the

congruence symbol so here we can take x

i is congruent to a times x i minus 1

plus b mod n this is something similar

as we can generate some sort of

recurrence relations or some sort of

rule which allows us to if i know one

number i can generate the other number

so as you can see

that we know the seed x naught and i can

generate the next number so

if you just fit this first seed into

this i will get the next number

so x1 this is congruent to a times x

naught plus b

times mod m and as you can see that a

and

b are already selected and we already

know once we know what is x naught we

can find what is

x 1 and similarly i can generate x 2

which is congruent to a

times x 1 plus b mod m and we continue

doing like this so it depends upon how

many integers or how many random numbers

do we require to

generate now let us take an example

corresponding to this consider this

example and in this example i have

selected let m is equal to 123

and a is equal to 5 and let b is equal

to 2 and we can choose

any random seed as well which is x

naught equal to 73

and here i will use the previous formula

we can see that x i

this is congruent to a times x i minus 1

plus b times mod m in fact this is more

like a linear congruence so that is why

the name is linear congruential method

so if somebody is very much interested

you can see my video on

what is a linear congress i've added the

link in the description

the linear congress is something like a

times x is congruent to b

mod n and there we can also talk when

this congruence is solvable or not

so this is something similar uh the only

difference is you can take

this b on the other side so it becomes a

x uh minus b

which is congruent to 0 mod n and then

we associate that for what value of x

what is the result that we get here so

in this case uh because

i'm not associating two different

numbers but here this is x i

and x i plus 1. so if you just consider

this a and

b as fixed quantity and here we consider

this as a variable

so the output that we expect here is

something which is

maybe we call it as a random number so

now once

looking this as a concept of the linear

congress extension we know what is a c

let's try to find the random numbers x 1

this is

congruent to a which is 5 and the seed

that is 73 so the first will go seed

plus 2 time which is the value for b

now solve this up which is congruent to

5 into 73 that is 365

plus 2 so this will be congruent to 367

and here we are taking modulo with

respect to 123

but now you can see this 367 is larger

than 123 so you divide

367 by 123 whatever be the remainder

so here you will get say if you are

dividing a number by

b you get some quotient plus remainder

so now we are dividing it by 123. so

whatever is the quotient

so this number a is 367 and i'm going to

get certain quotient plus the remainder

so this means

i'm going to replace this by the

remainder so that

so the remainder here is 121 so that

when this

remainder is brought here and subtracted

from here 123 will divide the difference

this is what the congress means so we

have 123.

now x1 is considered as 121.

similarly let's generate x2 number which

is 5

into now instead of this seed which is

73 i'm going to use the next number

which is generated that is 121

so we have here 121 plus 2

and again repeat the same process i am

going to first multiply 5 into 121

plus 2. so we get 607 mod

123 which is further congruent to 115

mod 123 so you can note that if i divide

607 by 123 the remainder that i get

correspondingly

is 115 so 107 minus 115 divided by 123

is i get the output as

4 so this means now i get this as a

quotient this becomes my quotient

correspondingly

so this is least remainder and similarly

we can generate

x3 which is 5 into 105 the next

seed plus 2 which is in the same format

i am just writing now the reduced number

that is 85 model of 123

and then we can generate x4 which is

congruent to 5

into 85 plus 2 which is further

congruent to 58

in the reduced list mod 123. now these

number which i have generated here

so the initial x naught that was 73

then we generated 121 then we generated

115

85 58 these are we call it as random

number and

in a specific notation you may call this

as a pseudo random number

because they are not truly random number

we have generated these through a

formula which is this

so now you may use a different linear

congruential formulas

correspondingly once you understand the

concept of generating numbers

we can use a different recurrence

relations also to generate the

random numbers now in various situation

we require random bit sequence instead

of the random numbers

so suppose that we have generated the

random number in the same order

i have taken x naught as 73 we got

x 1 which is 121 and then we got

x2 as a 115 we got

x3 as 85 and we got x4 as

58. so corresponding to this what we can

do is we can further associate

to generate the bits of the sequence

that is 0 and once

we can take the condition with respect

to modulo 2.

so if i take x naught which is 73

and 73 is congruent to 1

mod 2. so you can see that because 73 is

an odd number

so i have to so the remainder will be 1

so to get the sequence in terms of the

bits so if we further take this with

respect to modulo 2.

now in the same way if i want to

generate with respect to x1

this is 121 and 121 is also congruent to

1 mod 2.

now continue doing like this so x2 which

is 115

this is also congruent to 1 mod

2 and then x3 which is 85 and 85 is

further congruent to 1

mod 2 and then we got x 4

which is even that is 58 58 is congruent

to 0

mod 2. so had we generated certain more

numbers in this

row we could uh correspondingly generate

some more numbers in this one so what

are the random bits that we have

generated

so we got random bits as 1 1

1 1 0 and continue like this sequence

so now again uh if we want to generate

the random numbers in the bit sequence

because there are very

various crypto graphic algorithms such

as stream cipher where we do require

zeros and one

so you can generate the random bits in

this order

as well but again this is uh this is not

very secure

because we consider that uh if we look

at from the attack point of view

uh there is a possibility that the

probability of depicting the future bits

or the next bit

is half so that means this method would

be considered as 50

secure and 50 vulnerable

so but that's it for this particular

method and in the next

video i'll be talking about blum blum

shop pseudo random bit generator