2
$\begingroup$

I'm new to machine learning, and AI in general (but with 20+ years for programming). I'm wondering if machine learning is a good general approach to find the seed of a random number generator.

Suppose I have a list of 2000 numbers. Is there a machine learning algorithm to correctly guess the next number?

Just to be clear, as there are many random number generator algorithms. I'm taking about rand and srand from the stdlib.

Thanks, Eden

$\endgroup$
2
$\begingroup$

Machine Learning is a bad fit to this problem.

Even simple PRNGs that are not suitable for use in simulators (such as rand()) are varied enough that it is very hard to reverse engineer them statistically using generic techniques - essentially what 90% of ML does is fit a generic model to data statistically by altering parameters. The remaining 10% might do things in specialist manner, such as saving all the data and picking best option.

In theory most ML approaches would eventually solve a PRNG, however that would typically involve iterating through the entire state space of the PRNG multiple times. The statistical relationship between internal state, next state and output of a PRNG is complex by design, so that this is the only "black box" statistical approach, and this is clearly not feasible for any real implementation of a random number generator, which is going to have at least $2^{31}$ states on modern machines. Perhaps older 16-bit PRNGs, with a single value for state might be tractable.

An AI advanced enough to attempt to reverse engineer the output logically based on purely the data and researching how RNGs work is too advanced for current ML techniques to consider.

That leaves approaches that might try to construct a similar RNG, such as Genetic Programming (where the genome is converted to executable code). The trouble with this approach is there is no heuristic for a RNG that measures how close its output is to a target. A single bit of state difference or any tiny but meaningful change in generated RNG design will produce output that has no similarities with the target output whatsoever. Without such a measure you have no fitness function, and no way to attempt a guided search using the many discrete optimisation tools from AI.

Instead the usual approach to "breaking" a PRNG is to analyse the algorithm. Knowing the algorithm of many non-cryptographic PRNGs can allow predicting the internal state of the generator, sometimes in very few steps (for really simple Linear Congruential Generators that might be just a single step!).

$\endgroup$
  • $\begingroup$ Thank you very much! $\endgroup$ – Eden Jan 12 at 19:04

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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