2
$\begingroup$

Say I have a simple affine relationship between two variables $x$ and $y$ in a field $\mathbb{F}_p$ ($p$ is a large security parameter): $ax + by + c = 0$

What algorithm would be appropriate to find all roots $(x,y)$ such that $x < X$ and $y < Y$ for some small $X, Y$ compared to $p$?

Every algorithm I find seems like overkill, dealing with systems of several equations, higher degree or more variables. Would Coppersmith method still be the best here? LLL can be used to find one root but I don't see how to find the other ones.

$\endgroup$
  • 1
    $\begingroup$ Deleted my answer because it was trivial, but you might be able to use the method from section 4 of jscoron.fr/publications/bivariate.pdf to enumerate the 'short' roots. $\endgroup$ – pg1989 Jul 31 '16 at 4:59
  • $\begingroup$ @pg1989 I would have upvoted it nevertheless. #JustSaying ;) $\endgroup$ – e-sushi Jul 31 '16 at 10:39
1
$\begingroup$

All solutions of such an equation in $\mathbb{Z}$ are of the form $x=x_0-\frac{ka}{gcd(a,b)}, y=y_0+\frac{kb}{gcd(a,b)}$ for $k\in \mathbb{Z}$, where $(x_0,y_0)$ is any solution.

Look at these numbers modulo $p$ and you'll have a parameterization of a family of solutions to your equation. This might help you find some small solutions, depending on the size of your parameters $X,Y$.

Now, note that the equation $$ax+by=c+p$$ will also give solutions (or replacing $p$ by any $\theta p$ for $\theta\in \mathbb{Z}$), since when in $\mathbb{F}_p$, the equation is the same. I'll let you think if the solutions are the same.

$\endgroup$

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.