# How to determine if $\{n \cdot g^a \mod P\}$ and $\{m \cdot g^a \mod P\}$ generate the same sets? (set size < $P-1$)

given some examples $$k_{n_i},k_{m_i}$$ out of each value set:
$$k_{n_i} \in \{n \cdot g^a \mod P\, \forall a \in \mathbb{N}
$$k_{m_i} \in \{m \cdot g^a \mod P, \forall a \in \mathbb{N}

Each set has size of $$S$$ which is a prime and known. Value $$P$$ is also a prime with $$P = 2 \cdot S \cdot f+1$$. Factor $$f$$ is (product of) prime(s) which is known as well. The Generator $$g$$ is known too. For a given $$k$$ the factors $$n,m$$ and related exponent $$a$$ is unknown.

As shown here for each $$k$$ multiple value pairs $$(n,a)$$ can be computed very fast (pick an $$a$$ and compute $$n=kg^{-a} \mod P$$). That means those sets can be equal with $$n\not=m$$.
Now is there a way to check if they generate the same sets (without computing all combinations?)

• For what set is $g$ a generator? – SEJPM May 7 at 18:12
• same $g$ used in both sets, only the factor is different. $g^S = 1 \mod P$ and $P=2Sf+1$. So $g$ is not a prime root of $P$. It can only generate a subgroup of size $S$. With two different factors $m,n$ it generates two sets with all elements equal or 0 of them. With all possible factors $n'$ a total of $2 \cdot f$ sets can get generated, which don't contain equal elements and all numbers from $1$ to $P-1$ – J. Doe May 7 at 19:18

## 1 Answer

$$G_n = G_m$$ iff $$n^S \equiv m^S \pmod P$$

Proof:

If $$n^S \not\equiv m^S \pmod P$$, then $$\forall e \in G_n : e^S = n^S$$ (as $$e^S = n^S \cdot (g^a)^s = n^S$$); and similarly $$\forall f \in G_m : f^S = m^S$$. Hence $$\forall e \in G_n, f \in G_m: e \ne f$$, and hence $$G_n \ne G_m$$ (and actually the two sets are disjoint).

Other direction (needed because we're asserting equivalence):

If $$n^S \equiv m^S \pmod P$$, then $$(nm^{-1})^S = 1$$, that is $$nm^{-1}$$ is in the subgroup generated by $$g$$, that is, $$g^c = nm^{-1}$$ for some integer $$c$$.

Then, for any member $$e \in G_n$$, we have $$e = n \cdot g^a$$ (for some $$a$$); we have $$n \cdot g^a = n \cdot g^{-c} \cdot g^{a+c} = n \cdot n^{-1}m \cdot g^{a+c} = m \cdot g^{a+c}$$, and hence $$e \in G_m$$. Similarly, we can show that all elements $$f \in G_m$$ are also in $$G_n$$ and hence $$G_n = G_m$$

Extra credit for the reader: find the step where I implicitly assumed that $$P$$ was prime...

• Thanks again. you are my hero answering that many questions. Some hint, those $k_{m_i}, k_{n_i}$ should only be some random elements out of the set and not the sets themselves (edited top post, named them $G_n,G_m$). But that don't change anything. This finally destroyed my use case problem solving idea (link). For that case with 3 generators it should be $n^{QRS} \equiv m^{QRS} \mod P$ – J. Doe May 7 at 22:51