Why are generators of $Z^{*}_p, p=c \cdot 2^k + 1$ so small?

Question

I was implementing NTT for long integer multiplication and thus searched for generators of several $Z^{*}_p$ groups where $p=c\cdot 2^k + 1$.

I used the algorithm described in Wikipedia which uses the factorization of (p-1).

Here's a list of what I've found.

http://pastebin.com/1iWN3S7F

I wonder, why are these generators so small even though the prime numbers present are relatively large? Is it a general tendency or does it happen due to the special form of $p$?

Thank you!

Answer 1

Because of the special form, $\varphi(\varphi(p))$, the number of primitive roots, is perhaps somewhat larger than usual. But in general there are lots of primitive roots, distributed somewhat randomly. Then an easy heuristic argument shows that if we test small numbers, we are likely to bump into a primitive root quite quickly.