What is $\operatorname{max}(x)$ given that $ x \equiv n^p \pmod{q}$?

Question

Look at this:

$$ x \equiv n^p \pmod{q} $$

What is $\operatorname{max}(x)$?

Answer 1

If $q$ is a prime, then as $n$ ranges over $q$, this will define a finite field. Hence the maximum value it could be over $\mathbb{Z}/q\mathbb{Z}$ is $q-1$. However, this doesn't really help for a non-specific $n$.

Likely, if you are trying to calculate this in a program, the easiest way would be to directly calculate $n^{p} \ (mod \ q)$ utilizing exponentiation by squaring, and the fact that you only need to keep track of $q$ digits. This will give you a solution in $log \ p$ time. This may or may not be feasible depending on the exact size of $p$ and $q$.

Answer 2

It's somewhat meaningless to ask what is $\max(x)$ since if $n^p\equiv x\pmod{q}$, then $n^p\equiv (x+kq)\pmod{q}$ for all $k\in\mathbb{Z}$, so there's no upper limit.

Assuming that you are limiting $x$ to be in the range $[0,q-1)$, then the answer depends on $n,p$. If $n$ is what's called a primitive root modulo $q$, then the powers of $n$ hit every element in $(0,q-1)$ in turn. It's possible that $n^p\equiv q-1$, your worst nightmare. Even if $n$ is not a primitive root modulo $q$, that doesn't really help much, as its powers are more or less evenly scattered among $(0,q-1)$, so the largest it gets is only slightly smaller than $q$.