Predicting random numbers based on past output

Question

I've been working on a program to predict random numbers based on previous digits. However, I only get access to numbers from 0-53 inclusive, and one only comes every 30 seconds or so, therefore gathering hundreds or thousands of sequential data points is nigh impossible. I also don't know the algorithm being used, although right now I am assuming it is the Mersenne Twister.

With all that being said, here is the code that I am using:

import random
from multiprocessing import Process, Pool
import time
start = time.time()
data = [5, 49, 9, 2, 8]
datalength = len(data)
def actual():
 for i in range(9999999999):
 l1 = []
 random.seed(i)
 append = l1.append
 for i2 in range(datalength):
 x = random.randrange(0, 54)
 try:
 if data[x] == i2:
 append(x)
 except IndexError:
 break
def next_100(x):
 l1 = []
 random.seed(x)
 for i in range(datalength):
 x = random.randrange(0, 54)
 for i in range(100):
 l1.append(random.randrange(0, 54))
 return l1
with Pool(processes=3) as pool:
 result = pool.apply_async(actual).get()
z = next_100(result)
print('The next 100 should be: {0}'.format(z))
print('It took {0} seconds'.format(round(time.time()-start)))

I have 2 questions:

1. Is there a better algorithm than I am currently using? (that works with my limited knowledge)

2. If not, how else can I optimize this? Right now, I can't really guess more than 100 million seeds in a reasonable amount of time. Seed 100 million takes ~23 minutes, and 1 billion should take about 230 minutes, which is way more time than I have.

• Oscar Smith: ýour algorithm is trying to solve an impossible problem. A Mersenne Twister can be seeded with 2^64 different values, and no matter how fast your program is, you will not be able to check any significant fraction of them.
• Ethan Stancliff: Forgive me for asking, but aren't there only 4.2 billion possible values? My data is based on this (bishopfox.com/blog/2014/08/…) link, although there is a real chance I am misinterpreting something.
• Oscar Smith: oh, it depends whether it is seeded with a 32 or 64 bit int. If it's 32 bit, you have a chance.

Answer 1

You need to find or create a Mersenne Twister rainbow table. In other words, pre-compute all (or some subset) possible outputs, store them (time-space tradeoff), and compare the series you receive to the stored series.

The article quoted in https://stackoverflow.com/questions/6618836/how-if-at-all-does-a-predictable-random-number-generator-get-more-secure-after suggests the number of values you need to store may be much smaller.