1
$\begingroup$

Let $p$ be a prime number with $N$ bits, let $a,b,c$ be constants. The problem is to find solutions to the equivalent $a x + b y \equiv c \pmod p$ with both having at most $N/2$ bits.

What algorithmic approaches can solve this problem? Does it have any known hardness reduction?

$\endgroup$
6
$\begingroup$

You can use lattice reduction to solve this problem.

Pick a large constant $S\in\mathbb Z$ and consider the lattice spanned by the rows of the following matrix: $$ L = \begin{pmatrix} S a & -1 & 0 & 0 \\ S b & 0 & -1 & 0 \\ S c & 0 & 0 & S \\ S p & 0 & 0 & 0 \\ \end{pmatrix} $$

Now the crucial thing to notice is that some pair $(x,y)\in\mathbb Z^2$ is a solution to your modular equation if and only if $(0,x,y,S)$ is a vector in this lattice.

Moreover, some vector of the form $\vec v=(Sz,x,y,\pm S)$ must be part of a short basis, since $\begin{pmatrix}S c & 0 & 0 & S\end{pmatrix}$ is the only row of $L$ that is non-zero in the last column. Due to the large scaling factor $S$ in the first column, the vector $\vec v$ will in fact satisfy $z=0$, and therefore you can find a short solution by computing a reduced basis of $L$.

Here's a sage transcript that demonstrates this:

sage: p = next_prime(2**32)
sage: N = 1+floor(log(p,2)) # bit length
sage: S = 10**N
sage: a, b, c = randrange(p), randrange(p), randrange(p)
sage: a, b, c
(2206104035, 3690588304, 373686466)
sage: L = matrix(ZZ, [[S*a,-1,0,0], [S*b,0,-1,0], [S*c,0,0,S], [S*p,0,0,0]])
sage: L
[22061040350000000000                   -1                    0                    0]
[36905883040000000000                    0                   -1                    0]
[ 3736864660000000000                    0                    0          10000000000]
[42949673110000000000                    0                    0                    0]
sage: L.LLL()
[           0        49124        -7835            0]
[           0       -31049       -82479            0]
[-10000000000         2330       -37438            0]
[           0         4276       -42601  10000000000]
sage: (4276*a -42601*b) % p == c
True
$\endgroup$
  • $\begingroup$ Can this approach be used with a system of modular equations? $\endgroup$ – seba Nov 2 at 12:28
  • $\begingroup$ In fact, more interestingly: can you find solutions in which $x$ and $y$ are positive? $\endgroup$ – seba Nov 3 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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