# What are the chances of common generators? [closed]

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)$$?

## closed as off-topic by John Omielan, John B, Lee David Chung Lin, nmasanta, SemiclassicalSep 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.

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$$.

• Then how is generator for discrete logarithm modulo composites taken? – VS. Sep 11 at 19:33
• 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. – S. Dolan Sep 11 at 20:40

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}^*$$.

• Then how is generator for discrete logarithm modulo composites taken? – VS. Sep 11 at 19:33
• 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? – kub0x Sep 11 at 19:37
• In my problem when I say multiplicative group I mean modulo $\lambda(n)$. – VS. Sep 11 at 20:25
• 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. – kub0x Sep 11 at 20:47