3
$\begingroup$

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!

  • 1
    The generators are "small" because you are looking at the _smallest_ $r$ that generates $\mathbb Z_p^*$. A group can have _many_ generators. Note that if $\alpha$ is a generator of a cylic group of order $n$, then so is $\alpha^{-1} = \alpha^{n-1}$. More generally, $\alpha^k$ is a generator whenever $\gcd(n,k) = 1$. So small as well as large numbers can be generators. Since multiplication by small numbers is easier, it should come as no surprise that people tend to gravitate towards "small" generators in their choice.2012-05-06

1 Answers 1

3

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.

  • 1
    It is conjectured that the least primitive root of a prime $p$ is $O((\ln p)(\ln \ln p)).$2012-05-06