The Middle-square method is a really old PRNG algorithm from 1949. It was discovered by John von Neumann.
The Algorithm
In [1]:
def ms_next(seed, seed_len): seed = seed * seed seed = str(seed).zfill(seed_len * 2) mid = int(seed_len / 2) seed = seed[mid:-mid] return int(seed)
In [2]:
def ms_numbers(seed, seed_len): while True: seed = ms_next(seed, seed_len) yield seed
In [3]:
for i, num in zip(range(5), ms_numbers(123456, 6)): print(i, num)
Out:
0 241383 1 265752 2 624125 3 532015 4 39960
Increasing seed space
Let’s seed it with /dev/urandom.
In [4]:
import os def rand_digit(): while True: d = os.urandom(1)[0] if d > 250: continue return d % 10 seed_len = 50 seed = "" for _ in range(seed_len): seed += str(rand_digit()) seed = int(seed) seed
Out [4]:
7378710975714809271419972422814068416462491488115
Let’s see if we can turn these numbers into random bits.
In [5]:
def ms_bits(seed, seed_len): for num in ms_numbers(seed, seed_len): yield num & 1 def ms_bytes(seed, seed_len): bits = ms_bits(seed, seed_len) while True: b = 0 for _ in range(8): b <<= 1 b |= next(bits) yield b bits = "" for i, bit in enumerate(ms_bits(seed, seed_len)): if i == 40: break bits += str(bit) print(bits)
Out:
1100101111000110001001111100001001101011
Estimating randomness quality
In [6]:
import subprocess ent = subprocess.Popen(["ent"], stdin=subprocess.PIPE, stdout=subprocess.PIPE) buf = b"" for i, byte in enumerate(ms_bytes(seed, seed_len)): buf += bytes([byte]) if i == 500_000: break ent.stdin.write(buf) ent.stdin.close() print(ent.stdout.read().decode('ascii'))
Out:
Entropy = 7.999652 bits per byte. Optimum compression would reduce the size of this 500001 byte file by 0 percent. Chi square distribution for 500001 samples is 241.47, and randomly would exceed this value 71.91 percent of the times. Arithmetic mean value of data bytes is 127.6098 (127.5 = random). Monte Carlo value for Pi is 3.138780555 (error 0.09 percent). Serial correlation coefficient is -0.002272 (totally uncorrelated = 0.0).
Not too bad.
Useful links and references
- https://en.wikipedia.org/wiki/Middle-square_method