New problem 216 - hack random number generator
Back to General discussions forum
Here is a new problem Cracking Linear Congruential Generator!
Few days ago we were discussing random numbers with Radovan Markus in another thread - and touched this briefly. After I found I can't at once solve it myself - I thought this may be worth to recap something about modular arithmetics...
Took a fair bit of time to figure out. I never made any code which performed modular division, prior to this problem
and the first method I tried to come up with involved recursion and was kinda overly complicated.
I figured out a concise way to do it after thinking about it for quite a bit.
After solving it I took a look at the Modular Inverse problem that was noted in the problem's description. What I implemented
ended up not involving using GCD nor the extended Euclidean algorithm. However, the solution I made,
as it current is, only really works with M as a power of 2 :P
Thanks for "proof-solving" it!
I never made any code which performed modular division
Funny, but this take fair bit of time for me too. I was trying to think of some iterative approach, but eventually read the word "modular inversion" somewhere at stackoverflow - and suddenly started recollecting I've already seen it, perhaps, among other problems I wrote some time ago... Then things went easy, though I'm sure I don't well understand extended euclidean algorithm - despite being able to implement it by my own notes :)
However, the solution I made, as it current is, only really works with M as a power of 2 :P
It looks cool - I was wondering these last days that some special way of solving this should exist for powers of 2 - but found it too hard to me to figure out. Perhaps I'll try later, with your code as a guidance!
By the way, I was somewhat amused by comments in your solution: you explain in details the main part which is well self-explained by your code - however about the most mysterious part you just say "Which the code above does" :)
P.S. as I understand, some of requirements for LCG lead to M being often either power of 2 or powers of few
other small values, e.g. 134456 = 2^3 * 7^5. Perhaps your approach could be extended to such cases too, though not
sure it is worth trying unless for those who study number theory. I feel my head is too small for this. :o
you explain in details the main part which is well self-explained by your code - however about the most mysterious part you just say "Which the code above does"
Well, I wanted to establish why the modular division helps to solve the problem at hand. Though the hint provided in the problem certainly leads to this modular division that needs to happen.
I had messed around with figuring out how to do the modular division on pencil and paper for quite a bit of time, and given that there was already a problem for Modular Inverse my assumption was that someone who already did that problem and then this one wouldn't need an explanation on Modular Division, but well, as it turns out the Modular Inverse problem was solved in a different way anyways :P
As for how my code above works, I want to avoid revealing too many details for other users viewing this post, but here is a hint as to what's going on in it.
Consider finding a linear combination of [1 7 2],[0 3 9],[0 0 8] to sum to [3 39 92]. You can accomplish this by using the pivot entries in each of these vectors.
Start off by saying, well whatever the answer is, it's gotta involve 3 * [1 7 2] to match the leftmost component. So your current vector sum is [3 21 6], then to match the middle entry you are pretty much forced to add 6 * [0 3 9] to now have the sum [3 39 60] and then all that is left to do is add 4 * [0 0 8] and your overall sum matches the target [3 39 92]
Also consider a certain case... say you are trying to find a linear combination of [9 8 7 0 0 0 0],[0 1 2 0 0 0 0],[0 0 1 0 0 0 0] to sum to [5 8 2 0 0 0 0]. Those 0's don't make a difference, so you can ignore them and reduce the question to a * [9 8 7] + b * [0 1 2] + c * [0 0 1] = [5 8 2] for which values of a,b,c.
Modify these ideas to fit the problem and you'll get my solution :P
The 2nd of these ideas is probably never necessary though if the parity of the output of the LCG always flips. But it corresponds to the first part of my algorithm.