Thanks Gerhard and Lucia. I think you want $D(p^k)=(-1)^k2$ for $p\equiv 3\pmod 4$. D.H. Lehmer's paper is nice: my proofs are simpler but less general too.

@Massimo A cyclic group of order $q-1$, such as the multiplicative group ${\mathbb F}_q\setminus\{0\}$, has $\phi(q-1)$ generators. Note that $\phi(\phi(q))=\phi(q-1)$ when $q$ is prime.

@Noam There are $\phi(q-1)$ choices for the primitive element $r$. Could it be that the smallest value of $\deg(f)$, as $r$ varies, is ${\rm O}(\log q)$?

Burnside proved that the Sylow $p$-subgroups of $H$ are cyclic or generalized quaternion. He also incorrectly stated that $H$ must be nilpotent. See John Thompson's 1959 paper on fixed-point free automorphisms of prime order.