Take the 2-minute tour ×

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.

share|improve this question
For future reference: please see here for how to typeset common math expressions with LaTeX. –  Zev Chonoles Jul 25 '12 at 5:55
$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? –  user2468 Jul 25 '12 at 5:59
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. –  Gerry Myerson Jul 25 '12 at 6:00
Yes, I need something faster than the $O(\sqrt{p})$ enumeration. –  JohnLi Jul 25 '12 at 6:06
J.D.'s answer is fleshed out at numbertheory.org/php/aubry_thue.html –  Gerry Myerson Jul 25 '12 at 6:17

Your Answer



Browse other questions tagged or ask your own question.