I'm trying to find an integer x that satisfies a modular equation, and can't get my head wrapped around it...
Given two integers $n$ and $m$ in the range $[0, 2^{32})$, I need to calculate an integer $x$ such that
$x n\equiv m\pmod{2^{32}}$
Any suggestions for doing this without checking all $2^{32}$ possible values of $x$ for a match?
Edit: $n$ is known to be a specific large prime. For the case I'm currently trying to solve, $n=1167002411$.
Consider the congruence relation,
$$1167002411x \equiv 1 \pmod {2^{32}}$$
We can rewrite this as an absolute equation (for some integer $y$): $$1167002411x + 2^{32}y = 1$$
Since $1167002411$ and $2^{32}$ are coprime, it follows from Bezout's Identity that there exists integers $(x,y)$ which satisfy the above equation.
By using the Extended Euclidean Algorithm, we can easily (that is, with a computer) come up with the following solution:
$$(x, y) = (3456064387, -939060811)$$
However we are only interested in $x$, so we will take $x = 3456064387$ as the solution. In other words,
$$3456064387\cdot1167002411 \equiv 1 \pmod {2^{32}}$$
You can verify this yourself using Wolfram. Up till this point, what we have done is to essentially compute the inverse of $n$ modulo $2^{32}$.
Now, simply multiply both sides by $m$. We see that
$$(3456064387m)\cdot n \equiv m \pmod {2^{32}}$$
In other words, $x = 3456064387m$ will always be a solution. If this product overflows on your computer, simply take it modulo $2^{32}$.
More generally, given the congruence relation:
$$ax = b \pmod n$$
the solutions for $x$ is given by
$$x \equiv a^{-1}b \pmod n$$
where $a^{-1}$ is the modulo inverse of $a$ mod $n$ (assuming it exists).