How many unique elements are generated by a variation on the equation in DSA for r? How many unique elements are generated from the following equation?

$$i = (g^x \bmod p) \bmod n $$

where:


$g$ has order $q$
$q$ and $p$ are prime numbers
$q\mathop{|}p-1$
$n$ is integer number more than 2 (could be even or odd number)


In part $g^x \bmod p$, it will generate $q$ unique numbers. But I am getting confused when the value is modulus-ed by $n$. Can someone help me?
If $n &gt; p$, then this will yield $q$ distinct results, since $g^x$ takes on exactly $q$ distinct values all below $p &lt; n$ and ‘modulusing’ by $n$ has no effect in that case.  This is the largest number of values it can take on, no matter what $n$ and $p$ are.

Suppose $q = 2$ and $n = g &lt; p$.  Then there are two distinct values of $g^x$, namely 1 and $g$, and two distinct values of $(g^x \bmod p) \bmod n$, namely 1 and 0.  This is the smallest number of distinct values it can take on, no matter what any of the parameters are.

It can also take on intermediate numbers of values.  For example, with $g = 2, p = 17, n = 13$, we have $q = \operatorname{ord}(g) = 8$, and $(g^x \bmod p) \bmod n \in \{0,1,2,3,4,8,9\}$, which has 7 possibilities, which lies between $2$ and $q$.

It's possible there is some nice formula relating $p$, $n$, $q$, and the cardinality of $\{(g^x \bmod p) \bmod n \mathrel| x \in \mathbb Z\}$, but it's not obvious to the tiny brain in this feathery skull—which is spending more brain cycles wondering: Why do you want to know the number of possible values this can take on?  It is not actually the formula for $r$ in DSA, unless $n = q$.

On the other hand, if $n = q$, one might be wondering about the security of DSA.  Curiously, if one follows the references, what appears to be the standard reference for reduction of DSA security to discrete log security has only this to say on the subject:


  Indeed, it is very unlikely that the $“x \mapsto (g^x \bmod p) \bmod q”$ map has $(\log q)$-multi-collision.


(§6.1 ‘DSA–II Variant’, p. 289)

Here ‘$(\log q)$-multi-collision’ means a set of about $\log q$ (exactly which integer near that real number is not clear) elements sharing a common image under that map; the paper demonstrates a reduction of DSA forgery to calculation of discrete logarithms under the model of the message hash function as a random oracle and under the assumption that the map $x \mapsto (g^x \bmod p) \bmod q$ is $(\log q)$-multi-collision-free.  If, indeed, it is $(\log q)$-multi-collision-free, then since there are $q$ possible inputs in the domain and $q$ possible outputs in the codomain, there are at least $q/\log q$ possible values of $(g^x \bmod p) \bmod q$.

Thus, I'm afraid I must leave it as an exercise for the reader to trawl the number theory literature for wisdom on the question of the cardinality of the image of $x \mapsto (g^x \bmod p) \bmod q$, since the field of cryptography seems to lack an answer.