# Findings solutions to a modular equation within specified intervals

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.

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

• It is not important how large your intervals are as long as they are in $mod m$, they are smaller than the main interval of $[0, m-1]$ since you are in $mod m$. As I have written in the answers, the extended Euclidean algorithm gives the efficient answer for $[0, m-1]$. You find at most $d$ answers in which $d=gcd(a,m)$. The time for checking that this $d$ numbers are in the given interval or not is independent of the size of your interval, it depends only on $d$ since they are $d$ numbers. This check is efficient too. So, this edit doesn't change the method.
– m123
Commented Jul 15, 2023 at 12:17
• BTW: are you asking this because you want to know how to do it, or are you asking whether this being hard would be a good security assumption? For the former, I could go into more detail in my answer; the a latter, I believe my answer should be enough to show that it is not a good assumption Commented Jul 16, 2023 at 0:29
• @m123 The main problem is that the intervals are very narrow, so it was not clear I can find any solution efficiently in my case where d=1. Commented Jul 16, 2023 at 8:08
• @poncho I am asking because I want to know how to do it; it came up as part of a larger crypto problem and I was wondering whether there is any efficient route to finding solutions. I was also thinking something along the lines of LLL but couldn't find a valid reformulation of the problem, or maybe Integer Linear Programming but i wasn't able to determine if ILP would work since there is no software that can work with large numbers, only doubles or int64 values at most Commented Jul 16, 2023 at 8:12

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)

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$$

• I do not believe this is a correct answer to the question. For one, (1) always finds a single solution to the modular equation (irresepective of the bounds); obviously, without the bounds, there are $m$ different solutions to that modular equation. Commented Jul 15, 2023 at 2:05
• @poncho: But this is the efficient algorithm introduced in Trape and Washington's book for the same question without intervals. Checking each of the d answers to see if it is in the given interval or not (as I have written in bullet 1), do not change the complexity. Additionally, without the intervals, there aren't $m$ different solutions, there are $d$ solutions.
– m123
Commented Jul 15, 2023 at 11:15
• If $as + mt = 1$ then $as + 0 \equiv 1 \pmod m$ so $s \equiv a^{-1} \pmod m$ . Setting $a \equiv ys \pmod m$ implies $y \equiv a^2 \pmod m$ . Further, for (2), if we use the previous result and when $d=1$ then $ax \equiv a^2 \pmod m$ so $x \equiv a \pmod m$. What am I missing? Commented Jul 15, 2023 at 11:22
• @fandreas: in the first case in which the gcd is 1, it is correct that $s≡a^{-1}(\mod m)$. I didn't get what you mean by "Setting a≡ys(modm) implies $y≡a^2(\mod m)$" . and about your last sentence, the case $d=1$ is the first case, the second is for when you have $d>1$.
– m123
Commented Jul 15, 2023 at 11:57
• @m123: "Additionally, without the intervals, there aren't $m$ different solutions, there are $d$ solutions."; of course, there are $m$ solutions, there are $m$ possible values of $x$, and for each such value, there is exactly one value $y$ for which $ax = y \pmod m$ Commented Jul 15, 2023 at 13:21