Modular Powering (ModPower)

Input

Positive $n$-bit integers $a$, $b$, and $c$.

Problem

Compute $a^b \mod c$.

Status

Open (Cook [1]).

Remarks

The complexity of the problem is open even for finding a single bit of the desired output. The problem is in $\NC$ for smooth $c$, that is, for $c$ having only small prime factors (von zur Gathen [2]). Zeugmann improves on the circuit depth required to solve this problem in [3]. He presents logarithmic space uniform Boolean circuits of depth $O(\log n \log \log n)$ and polynomial size. Similar results for polynomials are given in [4]. Zeugmann also considers the problem of taking discrete roots and shows that for smooth modulus this problem can be solved using logarithmic space uniform Boolean circuits of depth $O(\log n \log \log n)$ and polynomial size [3].

In the special case when $c$ is a prime (the antithesis of smooth), the problem is open. ModInverse, is reducible to this restricted case. The analogous problems when $a$ and $c$ are $n^\text{th}$ degree polynomials over a finite field of small characteristic, Modular Polynomial Exponentiation and Polynomial Exponentiation, are in $\NC^2$ (Fich and Tompa [5]). They are open for finite fields having large (superpolynomial) characteristic. Note that ModPower can be reduced to the polynomial version with exponential characteristic simply by considering degree $0$ polynomials.