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(): <x0, x1, ..., xn>, determine the subsequent xs: <x(n+1), x(n+2), ...>.
2. Given a sequence produced by gf(): <x'0, x'1, ..., x'n>, determine the subsequent x's: <x'(n+1), x'(n+2), ...>.
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 <x0, x1, ..., xn> (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 <x'0, x'1, ..., x'n> (there may be many matches), we can get the rest if there is only one match. The efficiency is determined by the complexity of f() and the cycle T. The effectiveness is determined by T, T' and n.
Since <x'> is supposed to be random, we may expect that we need n=ln(T)/ln(T') numbers to determine the rest.
For the dice example, only 12 numbers are required.
If we have no access to the black box, or T is too large, brute force would be infeasible.
Assume f is LCG. f(x)=(ax+b)%m.
1. After some computation, we may find that m|((x2-x1)^2-(x1-x0)(x3-x2)). With <x0, x1, ..., xn>, we get (n-2) numbers being multiple of m. Taking the GCD will give us an estimation of m. a and b can be computed once we get m.
2. ???. Assume a,b,m<2^32, there will be at most 2^32*2^32*2^32 sequences, each has period <2^32. Thus, with brute force, we may expect to reveal the factors with n=ln(2^128)/ln(6)=48 numbers. However, efficiency is a big problem. Is there a clever way?
Are there efficient ways to reveal factors for other common PRNGs?
