This answer relates to an earlier variant of the question, which at one point gave an example problem with a, c, m known, as follows:
Consider the following in Java that prints 100 random numbers from 0 to 5:
Random r = new Random(); // seeded by system time
for (int i=0; i<100; i++) System.out.println(r.nextInt(6));
where r.nextInt(6) is essentially the following:
seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
// i.e. seed = (seed * multiplier + addend) $\bmod 2 ^ {48}$
int bits = (int)(seed >>> (48 - 31));
return bits % 6;
Yes, it is possible to predict the output of that Linear Congruential Generator variant from its first outputs. For a start, the only unknown is the original value of seed, which is 48 bits. That could be brute-forced, given moderate resources (some CPU.days), and that we have plenty enough outputs (if the output was truly random, we'd have about $100\cdot {log}_2(6) \approx 258$ bits of information). However there are much better attacks possible, succeeding in seconds.
That problem itself has varied. Originally it used a small integer (the final modulus) of 8, instead of 6. We first study that, because it turns out to be easier, and a good intro for the version with 6.
Original problem, ending in return bits % 8
Here seed has 48 bits, bits is its leftmost 31 bits, and the result bits % 8 is the 3 lower bits of that. The top 28 bits of seed never have an opportunity to influence the output of the generator (in a LCG with modulus m a power of two, a bit change in seed never propagates to lower-order bits of seed). Thus for the purpose of predicting the output, seed behaves as a 20-bit (not 48-bit) state. Further, the 3 high bits of that reduced 20-bit state are directly known from the first output.
Now, since everything except the initial state of the RNG is known, brute forcing the remaining 17 bits is almost instant. There are smarter methods that avoid the guesswork.
This illustrates that when the output of a LCG using a power of two as its modulus m is taken modulus some power of two n, the output has a much smaller period than the original LCG (and other weaknesses that may be a disaster even for simulation purposes).
Update: It turns out that Java's nextInt(int n) method special-case what happens when n is a power of two, and then does something very different from what was shown in the original question. That's in order to avoid the effect described above.
Other problem, ending in return bits % 6
Here, all 48 bits of seed have an influence on the output sequence. But there is an easy way to break these 48 bits into two separately attacked segments.
Because the final modulus 6 is even, the low bit of bits is also the low bit of the output, and leaks directly. It is the high bit of the main LCG, reduced to the low 18 bits of seed. That allows recovering the low 18 bits of seed from the low bit of the first outputs (slightly more that 18, I guess). A simple approach is enumerating the $2^{18}$ values of the low 18 bits of seed and, for each, check which gives the correct parity of the first output values. That will recover the low 18 bits of seed well under a second, and is enough to predict the parity of further output. Again, there are smarter methods that avoid the guesswork.
Now we are left with the 30 high bits of seed unknown; that can be brute-forced in seconds. Likely there are smarter methods.
Update: It turns out that Java's nextInt(int n) method does not work exactly as was shown in the original question, even when n is not a power of two; that's in order to remove a bias in the output. However, the simplified description given is good enough that the cryptanalysis described has fair chance to work as is, and can be adapted to work reliably.
Update 2: The above works because m is a power of two, and the final modulus n is divisible by $2^k$ with $k>1$. This allows a separate attack of the $k+r$ lower bits, where $r$ is the number of right bits of seed not used to produce the output ($k=1$, $r=17$ in the above example). If a and/or c and/or $r$ was unknown, it would still be possible to make this separation, and find the $k+r$ lower bits of each of seed, aand c, and the value of $r$, from a number of consecutive outputs considered $\bmod 2^k$, irrespective of the other unknowns.
A more general approach, applicable also to odd n, and perhaps to unknown a and/or c, would be to encode the problem under the formalism of boolean satisfiability, and use one of the many automated solvers available. I can't predict the runtime, though. This flexible approach has broken some mildly serious ciphers, see e.g. this cryptanalysis of A5/1, or this one.
LCGs are seriously bad for cryptographic purposes. They are fine for continuous simulation purposes (where the output is turned into the mantissa of a floating-point number and used as such), but brittle for discrete simulation purposes. In particular, if the LCG uses a power of two as its modulus m, do not take its output modulus an even number and expect the result to behave as a dice with that number of faces: that assumption is incorrect, and many simple tests will show that.
For example, the imbalance between the number of odd and even results in consecutive (simulated) dice throws is exactly zero after $2^{1+r}$ throws. This could be detected with even less samples with a bidirectional Chi-squared test of nextInt(6)%2 or even just nextInt(6). The incredulous can run this test code; it almost always outputs 0 (exceptionally, another single-digit value), when true random would usually give a 3-digit value.
import java.util.Random;
public class diceparity {
public static void main(String[] args) {
final int m = 262144; // number of dice throws
Random rand = new Random();
int s = -m/2; for (int i = m; i != 0; --i)
s += rand.nextInt(6)%2;
System.out.println("Deviation from expected: "+s);
}
}
Also, the parity of throws repeats after 262144 throws (or slightly less).
