Modular Inversion (ModInverse)

Input

An $n$-bit prime $p$ and an $n$-bit positive integer $a$, such that $p$ does not divide $a$.

Problem

Compute $b$ such that $ab \mod p = 1$.

Status

Open (Tompa [1]).

Remarks

ModInverse is reducible to ExtendedGCD. The reduction is to compute $s$ and $t$ such that $as + pt = \gcd(a, p) = 1$. ModInverse is also reducible to ModPower, even restricted to prime moduli. The idea is to compute $a^{p-2} \mod p$ and apply Fermat’s Little Theorem.

Zeugmann considers a slight variant of the problem where $p$ is replaced by a smooth modulus [2]. A number is smooth if all its prime factors are small. In this case Zeugmann gives a logarithmic space uniform Boolean family of circuits that solve the problem in $O(\log n \log \log n)$ depth and $n^{O(1)}$ size. Zeugmann gives analogous results for polynomials over finite fields [3].