# On keyword for generators of composite moduli

The link says $n$ has a primitive root if and only if $n$ is of certain form ($n=ap^k$ where $a=1$ or $a=2$ if $p$ is an odd prime or else $a=1$ and $k\leq2$ holds).

In particular $n=pq$ or $n=pqr$ where $p,q,r$ are not all equal primes are disallowed.

Yet in here discrete logarithms modulo such $n=pq$ or $n=pqr$ forms are defined and used (by this I mean there is a $g$ that generates $\phi(n)$ elements and this is used as generator).

Since generator $g$ cannot be primitive root what is the keyword for $g$ for these $n=pq$ or $n=pqr$ forms?

I tried this in mathematica with no use. How to search for these generators in mathematica?

The link says $n$ has a primitive root if and only if $n$ is of certain form, either $n = ap^k$ where $a \in \{1, 2\}$, $p$ is an odd prime or $n \in \{2, 4\}$

This is true.

In particular $n = pq$ or $n = prq$ where $n, q, r$ are not all equal primes are disallowed.

Other than the minor nit that $n=pq$ where $p=2$, $q$ is an odd prime does have primitive roots, the obvious question is "what do you mean is disallowed?"

A primitive root is a value $g$ where $g^k \bmod n$ can take on all values in $Z^*_n$; what the statement says is that such a $g$ will exist if $n$ is of the form listed, and no such $g$ will exist if it's not.

Yet in here discrete logarithms modulo such $n=pq$ or $n=pqr$ forms are defined and used.

Well, yes, the problem "given $g, h$, does there exist a $k$ such that $g^k \equiv h \pmod n$ (and if it does exist, what is its value)" is well-formed, even if $n$ is not of the listed form. Now, as there isn't a primitive root, there's no value $g$ for which such a $k$ will exist for every $h$ relatively prime to $n$; however that doesn't make this an invalid question.

Since generator $g$ cannot be primitive root what is the keyword for $g$ for these forms?

Well, I can't think of any better term than "generator". Any value $g$ relatively prime to $n$ will generate some subgroup; the only distinction between "primitive roots" and "everything else" is that primitive roots generate the entire group. I suppose you might insist on a value $g$ which generates as large of a subgroup as possible (which would be, for the forms you listed, of size $\text{lcm}(p-1,q-1)$ or $\text{lcm}(p-1,q-1,r-1)$), however I haven't heard of specific terminology given to elements that generate subgroups of that size.

• Say $n=19*59$ I just want to know how to select a $g$ such that $g^{k}\bmod n$ contains $\phi(n)$ elements in its orbit. What about for $n=19*59*83$ or $n=19^2*53$? – 1.. Dec 15 '16 at 20:34
• @AJ.: you can't; for $n=19 \cdot 59$, the best you can do is a subgroup of size $\phi(n)/2$ – poncho Dec 15 '16 at 20:35
• why? but even then how do you get $g$ which generates maximum elements? what is the keyword? when can you get $\phi(n)$ elements? – 1.. Dec 15 '16 at 20:36
• @AJ.: why? Well, the group structure of $Z^*_{19\cdot59}$ is isomorphic to the group $Z/18 \times Z/58 = Z/9 \times Z/2 \times Z/29 \times Z/2$. The problem is the subgroup $Z/2 \times Z/2$; it's noncyclic, as there's no element within that subgroup that generates the entire subgroup (and hence there can't be an element that generates the entire group) – poncho Dec 15 '16 at 20:42
• still problem remains how to get $g$ generating maximal elements? how to do it in mathematica? – 1.. Dec 15 '16 at 20:43