I was wondering what computational/algorithmic techniques can be used to solve a modular congruence when we are looking for a pair of small values.
The specific problem is like this (the numbers are just an example which can be solved with brute force, I'm curious about solving much larger versions of the same problem):
$$123\underline{\phantom{000}} = 456789 \cdot \underline{\phantom{000}} \pmod {1000003}$$
it's a congruence of 6 digit long numbers, modulo a prime. With simple algebra this is equivalent to solving:
$$x + 543214\cdot y \equiv 877003 \pmod {1000003}$$
with $x,y < 999$.
What I found is that I can just loop over all possible $x$ (or $y$) and compute the $y$ value and check if it's small. Are there more efficient methods? I looked up things like "short integer solution problem" on wikipedia but I don't know if it's applicable.