Determining Primitive Roots

The “Primitive Root Theorem” has been a historic stepping stone in the theory of natural integer numbers. The theorem asserts the existence of a “primitive root” (or “generator”) $q$ for every prime number $p$. Such a primitive root generates all remainders modulo $p$ as powers of $q$ modulo $p$. The numerous proofs offered in the literature have, however, one thing in common: They are not constructive, that is, they ascertain the existence without exhibiting an actual primitive root. In fact, some texts actually comment on this situation. Computational procedures in the literature are typically based on some criterion as to whether an integer $q$ constitutes a primitive root. They then proceed by trial and error, success being guaranteed by the primitive root theorem.

We propose to prove the primitive root theorem by actually constructing a primitive root for a given prime $p$. This procedure uses only elementary results of Group Theory and Number Theory such as prime factorization of $p-1$. For computational purposes we also propose an algorithm that does not utilize prime factorization.

Primitive roots are of cryptological interest. At issue there, however, are very large prime numbers which are well beyond the computational range of our algorithm as it stands.

This is joint work with John C. Witzgall.

Speaker Bio: Christoph Witzgall received his Ph.D. in Mathematics from the University of Munich, Germany, in 1958. After postdoctoral work at the Technical University of Munich and Princeton University he joined NIST – then NBS – in 1962, where he now serves as an emeritus of the Applied and Computational Mathematics Division.

Presentation Slides: PPTX

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.