According to the Wikipedia description of Feldman's VSS scheme

First, a cyclic group G of prime order p, along with a generator g of G, is chosen publicly as a system parameter. (Typically, one takes a subgroup of (Zq)*, where q is a prime such that p divides q-1.)

Why is it necessary to use a generator g in this process?
What is the procedure to be followed to implement a method which produces this generator for a given prime order group Zp?


The multiplicative group $\mathbf{Z}_p^*$ of non-zero integers modulo $p$ is cyclic of order $p-1$, so it has exactly one subgroup of order $k$ for each divisor $k$ of $p-1$.

To obtain an element $g$ of $G$, take any element $a$ of $\mathbf{Z}_p^*$ and let $g = a^{(p-1)/q} \bmod p$. Then $g$ is an element of $G$ because $$g^q = \left(a^{(p-1)/q}\right)^q = a^{p-1} = 1 \pmod p.$$

The order of $g$ is a divisor of the order of $G$, so it is a divisor of $q$, and since $q$ is prime, it equals either $1$ or $q$.

| improve this answer | |

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