2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ ý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. \$\endgroup\$ Oct 6 '17 at 22:36
  • \$\begingroup\$ 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. \$\endgroup\$ Oct 6 '17 at 22:49
  • \$\begingroup\$ oh, it depends whether it is seeded with a 32 or 64 bit int. If it's 32 bit, you have a chance. \$\endgroup\$ Oct 6 '17 at 22:58
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.