Generating Pseudorandom Numbers Using Congruence Theory In Python
Pseudorandom Numbers
A sequence of random numbers, chosen from the interval between 1 and some fixed integer $M$, is a sequence of numbers $x_0, x_1, \ldots $ such that for each $i$, the values of $x_i$ has a $1/M$ chance of being any given number between 1 and $M$, independent of what values $x_0, x_1, \ldots ,x_{i-1}$ took on.
For example, $M$ could be 6 and $x_i$ could be the number of dots showing on the $i^{th}$ throw of a fair die.
Random numbers are useful in many contexts related to computing. For example, cryptography requires numbers that attackers can't guess. We can't just use the same numbers over and over. Thus it is crucial to generate these numbers in a very unpredictable way so that attackers can't guess them.
We generally group the random numbers generated by computers into two types, depending on how they're generated: True random numbers and pseudorandom numbers. To generate a true random number, the computer measures some type of physical phenomenon that takes place outside the computer system. For example, the computer could measure the radioactive decay of an atom, the atmospheric noise or simply use the exact time one press keys on a keyboard as a source of unpredictable data.
Since a computer is not a random device, but rather a deterministic machine, it cannot compute random numbers on its own. It needs some kind of data from the physical world for that as discussed above. To circumvent this problem, a strategy adopted by computer scientists has been for the computer to generate sequences of numbers that look random, even though in fact they are not random. Such numbers are called pseudorandom numbers.
Among all the methods used to compute pseudorandom numbers, the most widely used and understood is the multiplicative congruential method developed by D.H. Lehmer in 1948.
The method developed by Lehmer is as follows:
- Pick a number $M$, the modulus.
- Pick a starting number $X_0$, the seed value.
- Pick a multiplier $A$.
- Generate the sequence as follows:
$X_1$ is the remainder obtained on dividing $AX_0$ by $M$; that is $AX_0 \pmod M$
$X_2$ is the remainder obtained on dividing $AX_1$ by $M$; that is $AX_1 \pmod M$
$\vdots$
$X_{n+1}$ is the remainder obtained on dividing $AX_n$ by $M$; that is $AX_n \pmod M$
Thus each of $X_0, X_1, X_2, \ldots$ is a number between 0 and $M$, and each $X_n$ satisfies
$X_{n+1} \equiv AX_n \pmod M$
To implement Lehmer's method in practice to get a good sequence of pseudorandom numbers, one should use a large modulus $M$. A large modulus $M$ commonly used is $M = 2^{31} - 1$ and the multiplier $A$ widely used is $A =7^5$. The python code that implement the Lehmer's method of pseudorandom number generation is given below for $M = 2^{31} - 1, A = 7^{5}$ and $X_0 = 621317$. The program displays the first 100 numbers in the pseudorandom sequence.
Program
def pseudo(a,m,x0):
list1 = []
for i in range(100):
x0 = (a*x0)%m
list1.append(x0)
print(list1)
m,a,x0 = 2**31-1,7**5,621317
pseudo(a,m,x0)
Output
[1852540231, 1425748211, 927649051, 266322937, 733681811,
139096403, 1331037285, 406498196, 869699065, 1258483973,
773694908, 476836171, 1924039040, 515388754, 1337240127,
1578448634, 1120700247, 29983492, 1421376646, 469200094,
286028074, 1205437732, 431235926, 24899657, 1876707681,
1733671078, 751685450, 2078546496, 1014472523, 1367020528,
1733958490, 1287251640, 1088053602, 1093634609, 404338790,
1083784422, 208486700, 1490138643, 805881587, 272471080,
986306156, 421292699, 412807934, 1690766928, 1216141792,
2093229645, 833538361, 1243403946, 726751465, 1772371766,
506603625, 1861948667, 639542185, 629850060, 943062357,
1619719239, 1118540501, 238354469, 966558828, 1387916288,
741678702, 1398857326, 2091594373, 1266809268, 1110490918,
240482749, 229338789, 1911364005, 86956562, 1190057574,
1782441707, 100893899, 1359163010, 669155931, 131872978,
186017542, 1808122009, 65516566, 1625297498, 383059046,
2064896063, 1372395321, 1873791267, 2109624861, 1510026857,
59645353, 1732068369, 1732242698, 367222907, 47396471, 2023538707,
2064014657, 1590990208, 1453537059, 1970865988, 1556888988,
1692466268, 1859661761, 858218689, 1581332771]
Now we can visualize the first 1000 pseudorandom numbers generated using the above algorithm by a python library called matplotlib.
Program
import matplotlib.pyplot as plt
def pseudo(a,m,x0):
x = []
y = []
for i in range(1000):
x0 = (a*x0)% m
x.append(i)
y.append(x0)
return(x,y)
m,a,x0 = 2**31 - 1, 7**5, 621317
x,y = pseudo(a,m,x0)
plt.plot(x,y,"o")
plt.show()
Output
 |
| The Scatter Plot of the First 1000 Pseudorandom Number |
Note. For the sake of programming, $X_0$ is removed from the first position of the list. But we can see that $X_0$ appears again later at some point in the list. In fact, after $X_0$ each element in the list starts repeating itself.
0 comments:
Post a Comment