Score:1

Crypto

Findings solutions to a modular equation within specified intervals

fandreas

7/14/24, 6:27 PM

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

2 + 4

modular-arithmetic

m123

7/15/24, 12:17 PM

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.

poncho

7/16/24, 12:29 AM

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

fandreas

7/16/24, 8:08 AM

@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.

fandreas

7/16/24, 8:12 AM

@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

Score:1

Crypto

poncho

7/15/24, 6:59 PM

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)

+ 0

Score:-2

Crypto

m123

7/14/24, 11:12 PM

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:

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

solutions:

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

+ 6

poncho

7/15/24, 2:05 AM

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.

m123

7/15/24, 11:15 AM

@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.

fandreas

7/15/24, 11:22 AM

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?

m123

7/15/24, 11:57 AM

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

poncho

7/15/24, 1:21 PM

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

m123

7/15/24, 2:06 PM

@poncho: Aha, I got what you mean. You mean both $x$ and $y$ are unknown here. I didn't consider $y$ as unkown. you are right.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Findings solutions to a modular equation within specified intervals

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.