Is there any way to guess a computer generated random number?Initiation:
When playing fly-chess on the net. I start thinking is it possible to predicate the next dice.
Notation:
Given a PRNG, it must have a cycle. Let the function being f(), and the period being T.
Usually, the output of the PRNG are normalized. Let the normalization function being g(), and the cardinality of the normalized numbers being T'.
eg. To simulate a dice, let f() being the c function rand(), let g(x)=x%6. T~=2^31, T'=6.
Problem definition:
1. Given a sequence produced by f(): , determine the subsequent xs: .
2. Given a sequence produced by gf(): , determine the subsequent x's: .
If we have access to the black box. i.e. f() or gf().
Brute force is possible.
1. We may call f() until it matches (there is one and only one match), then we can get the rest easily. The efficiency is determined by the complexity of f() and the cycle T.
2. We may call gf() until it matches (there may be many matches), we can get the r (more...)
so have you written a program attack fly-chess? that would be fun.