Question

Alice is using a linear congruential generator, axi + b mod 11, to generate pseudo-random numbers. Eve sees three numbers in a row, 3, 5, 0, that are generated from Alice’s function. What are the values of a and b?

Answer 1

Given,

Linear congruential generator used is ( aX_i + b ) ( mod 11 )

So,

X_i+1 = ( aX_i + b ) ( mod 11 )

Multiplier is a.

Seed element is X₀.

b is increment.

The modulus is 11,

With modulus 11, the value of X_I+1 ranges from 0 to 11.

The 3 numbers which are seen in a row are 3, 5, 0.

Let,

3 = ( aX_r + b ) ( mod 11 )------------------ eq 1

The next number is 5.

So,

5 = (3a+b) ( mod 11 ) ------------------ eq 2

The next number is 0.

0 = (5a+b) ( mod 11 ) -------------------- eq 3

Subtract eq3 from eq 2,

5-0 = ( 3a + b ) ( mod 11 ) -   (5a+b) ( mod 11 )

5 = (-2 * a) ( mod 11 )

= ( 9 * a ) ( mod 11 ) since 11 - 2 is 9.

So,

we get :

5 = 9a ( mod 11 )

Multiplicative inverse of 9 with respect to mod 11 is 5.

5*5 = a ( mod 11 )

25 mod 11 = a

a = 3

Put the value of a in eq 2 :

5 = (9+b) ( mod 11 )

5 mod 11 = 9 + b

5 = 9 + b

b = -4

So, the values are a = 3 and b = -4.