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.

Improve this question
$\endgroup$
2
  • 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
    Commented Jul 31, 2016 at 4:59
  • $\begingroup$ @pg1989 I would have upvoted it nevertheless. #JustSaying ;) $\endgroup$
    – e-sushi
    Commented Jul 31, 2016 at 10:39

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

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.