Findings solutions to a modular equation within specified intervals

Question

What are some approaches to find (ideally many/all) pairs of numbers $(x, y)$ with $ x \in [x_{\text{low}}, x_{\text{high}}]$ and $ y \in [y_{\text{low}}, y_{\text{high}}]$ such that the following holds:

$$a \cdot x \equiv y \pmod{m}$$

• Exhaustive search is not feasible since the intervals are each greater than $10^{30}$.
• $m$ is not necessarily prime.

Edit: added a numerical example:

m=100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

a=25392686019781782164356679796166612429399009942400218996555274144660682152509428039692348610084264596008789972113702053939160192781697341

With $x \in [0, 10^{84}]$ and for convenience let's say that $y \in [y_0, y_0 + 10^{84}] $ with

y_0=33732319676131018538972274738642940983980721830265900000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Answer 1

Here is one way to approach the problem: convert it into a Lattice problem (where we have good tools)

That is, consider a two dimension lattice over $\mathbb{Z}$, with the basis vectors $(1, a)$ and $(0, m)$. It is easy to verify that $(x, y)$ is a solution to $ax \equiv y \pmod m$ if and only if $(x, y) = c(1, a) + d(0, m)$ for integers $c, d$, that is, it is a point on the lattice. And so, the restated problem is "what lattice points are in the rectangle $[x_{low}, y_{low}], [x_{high}, y_{high}]$"

Now, this basis is a bad basis; however we have an algorithm LLL which can take that bad basis and turn it into a much better basis $(u, v), (w, z)$. In particular, these two basis vectors can't be closer that $60^\circ$ or greater than $120^\circ$ (otherwise LLL would find a smaller basis)

So, what we do is take the target rectangle $[x_{low}, y_{low}], [x_{high}, y_{high}]$ and transform that into our better basis, this will result in a parallelogram, with one corner being the value $(e, f)$ where $e(u, v) + f(w, z) = x_{low}, y_{low}$ (and note that $e, f$ are unlikely to be integers). And, this parallelogram has internal angles are not extreme; the angles will be between $60^\circ$ and $120^\circ$.

So then the problem comes in finding integral coordinates within that parallelogram; for each such one, we can map it back to the $(x, y)$ coordinates, which is a solution to the original problem. This searching should be straightforward (given that the parallelogram is not extremely long and narrow)

Answer 2

Edit: This is not the right answer since I didn't consider $y$ as unkonwn here, but as I had written it and maybe others make the same mistake, I didn't delete it.

---

There are two cases:

1. $gcd(a,m)=1$
2. $gcd(a,m)=d>1$

solutions:

1. find s and t such that $as+mt=1$ (via extended Euclidean algorithm). Then put $a\equiv ys \mod m$. Check if the answer is in your interval, then accept or reject it.

2. if $d$ does not divide $y$, then there is no solution. otherwise, solve the congruence $a/d x \equiv y/d \mod m/d$ using 1. Consider the result as z. The answer of the main problem of $ax \equiv y \mod m$ are:

$z \mod m$

$z+ m/d\mod m$

$z+2m/d\mod m$

$...$

$z+(d-1)m/d \mod m$