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, 2017 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, 2017 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, 2017 at 22:58

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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