1
$\begingroup$

I was looking at the proof of a change of base formula for the discrete logarithm in this paper (page 6, 4th bullet indent).

In the intruduction, the paper states:

Let $F_q$ be a finite field of order $q$, where $q=p^n$ ($p$ prime), and let $F_q^* = F_q -\{0\}$. Given $g$, a primitive element of $F_q$, and an arbitrary $y\in F_q^*$, the discrete logarithm of $y$ base $g$ is defined as $$ \log_g y = x \iff g^x=y \text{ in } F_q \text{ and } 0\leq x\leq q-2.$$

And then the author of the paper proves the change of base formula for the discrete logarithm:

Suppose $\Gamma$ is another primitive element of $F_q$ and we know $\log_g \Gamma = \gamma$.
$\Gamma$ and $g$ both primitive $\implies \gcd(\gamma , q-1)=1$
$\implies \exists \overline\gamma$ such that $\gamma \overline\gamma \equiv 1 \pmod{q-1} \implies g=\Gamma ^{\overline\gamma}$ in $F_q$.
Therefore $\log_g y = x \iff y = g^x = \Gamma ^{\overline\gamma x}$ in $F_q \iff \log_\Gamma y \equiv \overline\gamma x \pmod{q-1}$.
Multiplying the last congruence by $\gamma$ gives $\log_g y \equiv \log_g \Gamma \cdot \log_\Gamma y \pmod{q-1}$.

My question is, why does the following holds (from the beginning of the proof): $$ g \text{ and } \Gamma \text{ both primitive element of } F_q \text{ and } \log_g \Gamma =\gamma \implies \gcd(\gamma , q-1)=1 $$

$\endgroup$
3
$\begingroup$

Prove that:

$$g \text{ and } \Gamma \text{ both primitive element of } F_q^* \text{ and } \log_g \Gamma =\gamma \implies \gcd(\gamma , q-1)=1$$

A primitive element in finite field means it is a generator, i.e. $\langle g\rangle = GF(q) = F_q^* $.

Let $g \text{ and } \Gamma$ be both primitive elements of $ GF(q)$. By using the contrapositive we will reach the opposite.

Assume that $\gcd(\gamma , q-1) = d \neq 1$ where $\log_g \Gamma =\gamma$.

We can say that $\gamma = d \cdot k$ for some non-negative integer $k$ and $q-1 = d \cdot t$. $(q-1) \cdot t = \lambda \cdot k$. Therefore; $\lambda = \frac{(q-1)\cdot t}{k}$

$\log_g \Gamma =\gamma$ means $\Gamma = g^\gamma$ now,

\begin{align} \Gamma &= g^\frac{(q-1)\cdot t}{k} && ;\text{replace } \lambda \text { with } \frac{(q-1)\cdot t}{k}\\ \Gamma^{k} &= g^{(q-1)\cdot t} && ;\text{take } kth \text{ power}\\ \Gamma^{k} &= 1^t \\ \end{align}

Clearly, $k < q-1$ but we found a power $k$ of generator $\Gamma$ such that $\Gamma^{k} = 1$ this mean $\Gamma$ is not a primitive element. This proves the statement.

$\endgroup$
6
  • $\begingroup$ I don't quite understand, why does $\gamma \cdot k = q-1$? $\endgroup$
    – Jan
    Dec 20 '20 at 19:43
  • $\begingroup$ $\gcd(\gamma , q-1) = d $ means that $d|\gamma$ and $d|q-1$ (actually more than that it is the greates of the common divisors) than by the division thee must be a $k$ such that $k \cdot d = q-1$ $\endgroup$
    – kelalaka
    Dec 20 '20 at 19:45
  • $\begingroup$ Yeah I get that $k\cdot d=q-1$, but you wrote $\Gamma ^k = g^{\gamma \cdot k} \implies \Gamma ^k = g^{q-1}$, so my question is, how did you get $g^{q-1}$ from $g^{\gamma \cdot k}$? $\endgroup$
    – Jan
    Dec 20 '20 at 20:16
  • 1
    $\begingroup$ Ok, that should be the fix. sorry for the mess. I thought I found a shorter, but not. $\endgroup$
    – kelalaka
    Dec 20 '20 at 20:38
  • 1
    $\begingroup$ $F_q$ is a field, therefore every element has a multiplicative inverse, except the zero . Since $g$ is a generator, the order of any other element must divide the order of the generator, Lagrange Theorem on Group Theory. What you consider the group $Z_{q-1}$ then with the GCD we can say that there exist an inverse $\endgroup$
    – kelalaka
    Dec 20 '20 at 20:52
0
$\begingroup$

Let $a$ be an element of a group and $o(a)$ be the order of $a$ in group. It is an easy to prove problem that $o(a^r) = \frac{o(a)}{gcd(o(a),r)}$. Therfore $a$ and $a^r$ generate same group iff $gcd(o(a),r)=1$. Now you can set the group by $F^{\ast}$ with $q-1$ element and $a$ a generator of it.

$\endgroup$

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.