2
$\begingroup$

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}<P\}=G_m$
$k_{m_i} \in \{m \cdot g^a \mod P, \forall a \in \mathbb{N}<P\}=G_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?)

$\endgroup$
  • $\begingroup$ For what set is $g$ a generator? $\endgroup$ – SEJPM May 7 at 18:12
  • $\begingroup$ 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$ $\endgroup$ – J. Doe May 7 at 19:18
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – J. Doe May 7 at 22:51

Your Answer

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

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