1
$\begingroup$

I arrived to needing an algorithm for the following subproblem while solving a more complex problem.

It seems it should be a very standard algorithm, but my number theory isn't too fresh so I haven't found a solution yet.

Given a prime $p$, and a constant $c$, I want to find $x$ and $y$ such that: $$x * y^{-1} \equiv c \pmod p$$ and $\max(|x|, |y|)$ is either minimized, or at least it is less than the worst-case value for any instance of the problem, which I believe is $\sqrt{p}$.

In my case, $p$ is a $64$-bit prime which is always the same, so arbitrary precomputation on it can be assumed to be $O(1),$ assuming it can be done in reasonable real time.

It seems the extended Euclid algorithm could be useful (since it gives a minimality guarantee), but the presence of the modulus stifled my attempts to apply it.

  • 0
    For future reference: [please see here](http://meta.stackexchange.com/a/70559/161783) for how to typeset common math expressions with LaTeX.2012-07-25
  • 1
    $xy^{-1} \equiv c \pmod{p} \implies x = cy + kp$ for some integer $k.$ If we run the extended Euclidean algorithm on $(p, c),$ we will get the triplet $(x_i, y_i, k_i)$ after every iteration such that $x_i = cy_i + k_i p.$ Can't you pick among the set $\{(x_i, y_i)\}$ whichever pair that satisfies your objective maxima?2012-07-25
  • 0
    If you really just need an algorithm, here's one: compute $cy\pmod p$ for $y=1,2,\dots,\sqrt p$, and take the smallest value as your $x$. But I suppose you want a faster algorithm.2012-07-25
  • 0
    Yes, I need something faster than the $O(\sqrt{p})$ enumeration.2012-07-25
  • 0
    Regarding J.D.'s answer, it isn't immediately obvious to me that the set of triplets contains the answer, though it could be so, not sure.2012-07-25
  • 1
    J.D.'s answer is fleshed out at http://www.numbertheory.org/php/aubry_thue.html2012-07-25
  • 0
    Have you solved this yet, by brute force, for all primes up to, say, 1000?2012-07-25
  • 0
    Thanks! Indeed, the existence theorem is called Aubry's theorem, and one of the steps in the Euclidean algorithm must be the solution. Is there any way to mark those comments as a solution or something like that?2012-07-25
  • 0
    No, there isn't, but there should be :-) You can ping the person who answered the question in a comment (using @username) and ask them to post it as an answer.2012-07-25

0 Answers 0