Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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. –  Dilip Sarwate May 6 '12 at 19:48

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
1  
It is conjectured that the least primitive root of a prime $p$ is $O((\ln p)(\ln \ln p)).$ –  Chris K. Caldwell May 6 '12 at 22:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.