Primitive root-finding problem

From Groupprops
Jump to: navigation, search

Definition

Suppose G is a finite group specified by means of a suitable group description rule (typically, an encoding), and we are given a promise that G is a finite cyclic group. In other words, we can think of G as a black-box cyclic group (though there may be more contextual structure known about G). The goal is to obtain an explicit description of a single element g \in G such that G = \langle g \rangle. Such an element is termed a primitive root in some contexts.