2
$\begingroup$

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?

| improve this question | |
$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – T.... Dec 15 '16 at 20:34
  • $\begingroup$ @AJ.: you can't; for $n=19 \cdot 59$, the best you can do is a subgroup of size $\phi(n)/2$ $\endgroup$ – poncho Dec 15 '16 at 20:35
  • $\begingroup$ why? but even then how do you get $g$ which generates maximum elements? what is the keyword? when can you get $\phi(n)$ elements? $\endgroup$ – T.... Dec 15 '16 at 20:36
  • $\begingroup$ @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) $\endgroup$ – poncho Dec 15 '16 at 20:42
  • $\begingroup$ still problem remains how to get $g$ generating maximal elements? how to do it in mathematica? $\endgroup$ – T.... Dec 15 '16 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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