Small generator for classical Schnorr signatures? I'm implementing classical Schnorr signatures for real-world use. By &quot;classical,&quot; I mean that the operations occur in a finite group, with no elliptic curves.
I'm following Schnorr signature and Schnorr group at Wikipedia, and some academic papers.
After choosing $p=qr+1$ with $p$ and $q$ prime I need to calculate a suitable &quot;generator&quot; $g$.
As explained on the Wikipedia page, I set $h=2$ and try to see if $h^r \textrm{mod } p$ is different from 1 (it always has been so far) and that value becomes $g$.
The trouble is, $g$ is (logarithmically) about as large a number as $p$ when chosen this way.
Is there a way to choose a smaller $g$ so that less parameter data needs to be passed around?
If I understand correctly, any $g$ s.t. $g^q=1 \textrm{ mod }p$ ought to work (provided, of course, $g \ne 1$). It's easy to see why $2^r$ works; it's because $(2^r)^q=2^{rq}=2^{p-1}$ which is 1 by Fermat's little theorem.
But can a smaller $g$ be derived somehow?
FIPS 186-4 appendix A.2 gives an algorithm to generate $g$. They are not talking about Schnor signatures but apparently DSA uses just the same kind of finite cyclic groups.

The algorithm really just tries random $1 &lt; h &lt; p-1$ until it finds an $h$ that fulfills $h^r \not\equiv 1 \pmod{p}$. Apparently the probability to find such an $h$ is not too small.

Fermat's little theorem states that $a^{p-1} \equiv 1 \pmod{p}$ for any prime $p$ and $a \in \mathbb{Z}^+$ with $p \nmid a$.

Thus, with $h&lt;p$ you automatically get $p \nmid h$ and therefore $g^q \equiv h^{rq} \equiv h^{p-1} \equiv 1 \pmod{p}$.

I guess the goal cannot be to find a $g$ with a small bit width to save data. As you calculate $g = h^r \text{ mod } p$ with $r$ being random (uniformly distributed), the possible values for $g$ should be uniformly distributed as well.