How to open a linear congruential pseudo-random number generator?

Question

Mathematics

For educational purposes, I want to crack the simplest PRNG.
Even those who do not know about the linear congruential generator or about the rpg in principle can help here, because the question is a misunderstanding of the English text and a bit of mathematics.
For you in short: There is such a thing as a pseudo-random number generator. those. random, if easier. They are "pseudo-random" because they are not random, but look like one. One of the implementations of such a generator is:
Xn+1=(aXn+c) mod m
Where Xn is the nth member of the sequence. Variables a, c and m are constants: a is a multiplier, c is an increment, m is a modulus. X0 is the initial value.
My hack conditions:
1. We know that the generator is based on a linear congruential method.
2. We don't know a, c and m.
3. We can get any members of the sequence.
Task: determine a,c,m (with higher probability).
I found several ways in the English version. I need either one of these or another that I don't know.
On this site, they solve it by brute force. The only thing is that not the whole sequence is given there, but every second term. Therefore, as far as I understand, you do not need to do PowerMod. Questions about this method are as follows:
1. Did I understand correctly that the second code is implemented because the first one produced two results, but we need one?
2. Question on modular arithmetic: How did you get that c = X2 - ((X1 * a) % m) (in the first code)?
3. Why m < 10*M_START?
4. What happens in the second code? Right
here- Plumstead's algorithm. And here - the algorithm of J. Marsaglia Please explain, who understood, from a mathematical point of view.
Other references :
Modular arithmetic + division by multiplication + ...
Why 1103515245 is used in rand?
Cracking a linear congruential generator
Design of Cryptographically Strong Generator By Tr...

Answer 1

In brute force, everything is very simple, we generate sequence after sequence and look at the one we want to hack. If everything matches, then it was hacked. Every second member is made for complication.
Plumstead isn't exactly a pony, but it looks like they're getting through the checkmate. waiting for a similar sequence. That is, according to the idea, it is very fast, but inaccurate in the limit, then the run is wrong. Therefore did not penetrate.
And Marsaglia, or rather the guys that refer to him, simply decide the system of comparisons, as far as I understand. And Marsagli himself proved something about these generators there, which made it possible to draw up the system itself.
All this is a cursory glance, but in general, linear generators from the point of view of cryptography are a very bad idea. It's not so much about hacking, but that they don't mimic a random sequence very well, and the linearity itself leaves a lot of freedom for the creativity of cryptanalysts. And about the simplicity of implementation - one can argue here, because the integer remainder of the division is not the simplest operation, there are much more interesting generators based on non-linear binary logic.