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.