Let's say I have a noncyclic multiplicative group $G_m = \{j < m, \gcd(j,m) = 1\}$, with multiplication $\bmod m$. This has order $\varphi(m)$, and suppose I can determine its factorization.

Now suppose I have some prime $p_1 \in G_m$ which has order $n_1$ such that $n_1 < \varphi(m)$ (since $G_m$ is noncyclic) and $n_1 \mid \varphi(m)$ (Lagrange's theorem).

  • Given another prime $p_2 \in G_m$, is there a way to tell whether $p_2 \in \left<p_1\right>$, that is, $p_2 = {p_1}^k \pmod m$ for some $k$ --- without trying all possible values of $k$?

  • If $p_2 \notin \left<p_1\right>$, is there a way to determine the order of the multiplicative group $H_{p_1,p_2} = \{{p_1}^{k_1}{p_2}^{k_2} \mod m\}$ without exhaustively trying to enumerate all elements?

I know I can determine the order of $p_1$ or $p_2$ by computing $p_1^{\varphi(m)/j}$ for various primes $j \mid \varphi(m)$; if the result is 1 then I should be able to confirm that $K$ = some product of powers of those primes $j$ is the largest possible value such that $p_1^{\varphi(m)/K} =1$, and therefore the order of $p_1$ is $\varphi(m)/K$.

Not sure how to determine the order of a group that has a generating set of more than one element, though.

  • $\begingroup$ um... huh. That's interesting. You may be right about the difficulty in cyclic groups too... I'm not savvy enough to figure out how to solve my problem, at least not yet. I'm particularly interested in the case of $m=2^n-1$. $\endgroup$ – Jason S Jul 20 '18 at 1:45

Your Answer

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

Browse other questions tagged or ask your own question.