I debated posting this here, in the cryptography SE, or the programming SE. Obviously, I chose here, but I'm not confident in my choice...
I'm attempting to "undo" a function, but I've hit a slight snag.
I have a function $h=x*33+c$. I know $h$, and can constrain $c$ to a range of approximately $[65,\ 120]$. Investigating all of those $c$'s is not computationally viable, the reason being that this function is often applied iteratively, so it has an exponential complexity increase. Instead, I figured I could further narrow what $c$'s I have to investigate by using the equation $y=h\mod{33}$. $y$ would be the remainder. From there, I can investigate only those values of $c$ that satisfy this equation: $y \equiv c\mod{33}$, since subtracting $c$ from $h$ must lead to a number that can be evenly divided by 33.
The problem is, all this math was evaluated under a 32bit computer, which means every math operation is $\mod2^{32}$. Some x's were large enough that the evaluation of the original function caused $h$ to make one (or possibly several) wraps around this modulus point, otherwise my task would be straightforward.
My question is, how can I find the remainder, given that I need to account for this "overall" modulus? I asked a related question about division around a modulus here: https://softwareengineering.stackexchange.com/questions/250811/undoing-an-integer-wraparound# and was told about the multiplicative inverse. Does a similar thing exist for remainder operations?
For example, if we evaluate the function with values $x = 193492627$ and $c = 98$, we get $h = 2090289493$ (because h is $\mod2^{32}$). Is there an operation $\Omega$ such that $ (h\;\Omega\;33)=32$? (The result being $32$ because $98 \equiv 32 \pmod{33}$)
Here's an example of what I can do, in a case where $h$ has not wrapped.
- $h = 177676$
- $y = h\mod{33} = 4$
- Values of $c$ where $4\equiv c\mod{33}$: $70$ and $103$
- I can now pursue only those two values of $c$. (Find the values of $x$ that correspond to them, etc)
Here's an example of the same algorithm above, but in a case where $h$ has wrapped:
- $h = 2090289493$
- $y = h\mod{33} = 28$ <-- Incorrect! Should be 32
Here is an example of the algorithm using the operation $\Omega$ and an $h$ that has wrapped. This is what I'd like to do, but I don't know what operation $\Omega$ represents.
- $h = 2090289493$
- $y = h\ \Omega\ {33} = 32$
- Values of $c$ where $32\equiv c\mod{33}$: $65$ and $98$
- I can now pursue only those two values of $c$.