1
$\begingroup$
  1. Supposing $n=\prod_{i=1}^tp_i$ is odd and may not be square-free and $g$ generates each of multiplicative groups mod $\lambda(p_i)$ then what are the chances that $g$ generates multiplicative group mod $\lambda(n)$?

  2. What are the chances there is a $g$ that generates each of multiplicative groups mod $\lambda(p_i)$?

$\endgroup$

closed as off-topic by John Omielan, John B, Lee David Chung Lin, nmasanta, Semiclassical Sep 12 at 4:40

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – John Omielan, John B, Lee David Chung Lin, nmasanta, Semiclassical
If this question can be reworded to fit the rules in the help center, please edit the question.

0
$\begingroup$

I may have misunderstood your question so let me know if this is not what you meant.

Question (1)

Your $n$ appears to be a product of distinct primes. For such an $n$ with $t>1$, the only cyclic multiplicative group mod $n$ is the one with $n=2p$ where $p$ is an odd prime.

The chance is $0$ unless $n=2p$ and is $1$ if $n=2p$.

Question (2)

Each multiplicative group mod $p_i$ is cyclic and so has a generator $g_i$.

By the Chinese Remainder Theorem there is an integer $g$ which is congruent to $g_i$ mod $p_i$ for all $i$. Therefore there is always such a $g$.

$\endgroup$
  • $\begingroup$ Then how is generator for discrete logarithm modulo composites taken? $\endgroup$ – VS. Sep 11 at 19:33
  • $\begingroup$ Discrete logarithms are logarithms defined with regard to multiplicative cyclic groups. If you don't have a cyclic group then you don't have a generator. $\endgroup$ – S. Dolan Sep 11 at 20:40
0
$\begingroup$

Note that $n=\prod_{i=1}^{t}p_i$ is a composite modulus thus it's order is equal to $\varphi(n)=\prod_{i=1}^{t}(p_i-1)$

Recall that $Z_{n}^*$ is cyclic $\iff \varphi(n) = \lambda(n)$ this is $lcm((p_1-1),\cdots,(p_t-1)) = \prod_{i=1}^{t}(p_i-1)$, which results false as $Z_{n}^*$ is cyclic when $n=p$ or $n=2p$. In the end, no generator exists for your $Z_{n}^*$.

$\endgroup$
  • $\begingroup$ Then how is generator for discrete logarithm modulo composites taken? $\endgroup$ – VS. Sep 11 at 19:33
  • $\begingroup$ Take $n=pq$ where $p,q \in \mathbb{P}$. Then there exists an element $g$ with order $\lambda(n) = lcm(p-1, q-1)$ Prove that $Ord_{Z_{n}^*}(g) < \varphi(n)$. Then $g$ clearly generates a subset of elements but not the whole set of elements of $Z_{n}^*$. Do you want this definition to be included in my answer? $\endgroup$ – kub0x Sep 11 at 19:37
  • $\begingroup$ In my problem when I say multiplicative group I mean modulo $\lambda(n)$. $\endgroup$ – VS. Sep 11 at 20:25
  • $\begingroup$ Then you should change the description of your question. Generally the multiplication operation on $Z_{n}^*$ is reduced $mod \quad n$. If you mean $mod \quad \lambda(n)$ it doesn't really matter, as it wouldnt satisfy $\lambda(\lambda(n)) = \varphi(\lambda(n))$ so there does not exist a generator by my previous comment's axiom. $\endgroup$ – kub0x Sep 11 at 20:47

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