1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – m123
    Jul 15, 2023 at 12:17
  • $\begingroup$ 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 $\endgroup$
    – poncho
    Jul 16, 2023 at 0:29
  • $\begingroup$ @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. $\endgroup$
    – fandreas
    Jul 16, 2023 at 8:08
  • $\begingroup$ @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 $\endgroup$
    – fandreas
    Jul 16, 2023 at 8:12

2 Answers 2

1
$\begingroup$

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)

$\endgroup$
-2
$\begingroup$

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$

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – poncho
    Jul 15, 2023 at 2:05
  • $\begingroup$ @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. $\endgroup$
    – m123
    Jul 15, 2023 at 11:15
  • $\begingroup$ 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? $\endgroup$
    – fandreas
    Jul 15, 2023 at 11:22
  • $\begingroup$ @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$. $\endgroup$
    – m123
    Jul 15, 2023 at 11:57
  • $\begingroup$ @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$ $\endgroup$
    – poncho
    Jul 15, 2023 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.