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
    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