0
$\begingroup$

While practising on paper I've realized of a property of multiplicative group of integers mod $n$.

First, let's define $G$ being $p$ a prime and $g$ a primitive root mod n or a generator of a subgroup of $p$ whose order is a factor of $|G|$.

Example:

$p=23$

$|G|=p-1=22$

Then find a valid $g$ whose $Ord_{p}(g)=p-1$ or $Ord_{p}(g)=2$ or $Ord_{p}(g)=11$ being $11$ and $2$ the factors of $22$. We'll define $q$ as a factor of $p$ so $q=11$ in this case.

Using the mechanism of testing a primitive root we find that:

$2^{11}$ $mod$ $23 = 1$ So $Ord_{p}(2)=11$

We found that $2$ isn't a primitive root mod n so it generates a subgroup of order $11$

Now we compute $g^{q-1}$ $mod$ $p$:

$2^{10}$ $mod$ $23 = 12$

Now if $Ord_{p}(2)=Ord_{p}(12)$ then:

$12^{10}$ $mod$ $23 = 2$

Summarizing, this property satisfies that if two generators have the same multiplicative order then if you raise the first generator to $p-2$ or $q-1$ you will obtain the second generator as a congruence.

I want to know if this make sense. Would this method reveal any info of the exponent used by the involved parties?

Thanks for your effort and time!

$\endgroup$
  • 1
    $\begingroup$ Actually, this is true only if your two generators $g, h$ satisfy $g \cdot h = 1$, that is, they are inverses of each other. In that case, they'll have the same order, and both $g^{q-1} = h$ and $h^{q-1} = g$. This won't hold true if the two generators are in the same order (for example, $g=2$ and $h=4$), but $g \cdot h \ne 1$ $\endgroup$ – poncho Jun 2 '15 at 16:15
  • $\begingroup$ Thanks for your comment, I appreciate your help. But if $h=4$ then $4^{q-1}=6$ and $6^{q-1}=4$. There will be always a second generator whose order is the same as the first? And is this behaviour only manifested when raising $g$ to $q-1$ or $p-2$? $\endgroup$ – kub0x Jun 2 '15 at 16:25
  • $\begingroup$ Again, in this case $4 \cdot 6 = 1 \pmod{23}$, that is, $4$ and $6$ are inverses of each other. Yes, except for $g = 1$ and $g=-1$, there will always be a second generator with the same order as the first. And, yes, this behavior happens only for exponents that are modulo -1 to the order of $g$ $\endgroup$ – poncho Jun 2 '15 at 17:04
  • $\begingroup$ If the order of a value $g$ is $q$, then there be precisely $\phi(q)-1$ other values that also have order $q$. This is independent of what $p$ is (other than $q$ is necessarily a divisor of $p-1$). If your case, we have $q=11$, hence there are $\phi(11)-1 = 9$ other values (that is, other than 2) that have order 11 modulo 23. $\endgroup$ – poncho Jun 2 '15 at 17:18
  • $\begingroup$ Thanks a lot @poncho. What I deduct from here is that two generators of the same multiplicative order satisfy the property $g^{q-1}=g'$ & $g'^{q-1}=g$ only if they satisfy the inverse multiplicative mod n property first. $\endgroup$ – kub0x Jun 2 '15 at 17:37

Your Answer

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

Browse other questions tagged or ask your own question.