# Question about the proof of the change of base formula for the discrete logarithm

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

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.

• I don't quite understand, why does $\gamma \cdot k = q-1$?
– Jan
Dec 20 '20 at 19:43
• $\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$ Dec 20 '20 at 19:45
• 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}$?
– Jan
Dec 20 '20 at 20:16
• Ok, that should be the fix. sorry for the mess. I thought I found a shorter, but not. Dec 20 '20 at 20:38
• $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 Dec 20 '20 at 20:52

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.