\chapter{The Discrete Logarithm Problem over Finite Fields}

\section{Statement of the problem}
We start by defining the discrete logarithm problem over finite fields.
\begin{definition}
Let $\F_q$ be a finite field of characteristic $p$ and $g\in \F_q$ be a primitive element.
Then for each $\alpha\in \F_q^*$, there exists an integer $n$ such that $g^n=\alpha$, which is denoted by $\log_{g}(\alpha)$. 
The discrete logarithm problem over finite fields is determining $log_{g}(\alpha)$ given $\alpha$.
\end{definition}

\begin{example}
Let $p=11$ be a prime number. One can check that 2 is a primitive root of $\Z/11\Z$,
i.e., $(\Z/11\Z)^*=\langle 2 \rangle$. It is easy to compute the power of 2 modulo 11 using modular exponentiation.
The result is shown in Table \ref{tab:expmod11}.

%\vspace{5mm}
\begin{table}[h]
\centering
\begin{tabular} {|l|l|l|l|l|l|l|l|l|l|l|}
\hline
x                       & 1   & 2  & 3 & 4 &  5  & 6  &  7 & 8 & 9 & 10   \\ \hline
$2^x \pmod{11}$ 		& 2   & 4  & 8 & 5 &  10 & 9  & 7  & 3 & 6 & 1    \\ 
\hline
\end{tabular}
\caption {Modular exponentiation in $\Z/11\Z$} \label{tab:expmod11}
\end{table}
%\vspace{5mm}





\iffalse
\hspace{5mm}
\centering
\begin{figure} \label{fig41}
\begin{tikzpicture}[scale=0.7]
\draw[<->, thick] (0,11) node (yaxis) [above] {$2^x$}
	|- (11,0) node (xaxis) [right] {$x$};
\draw [color=blue, fill=blue] (1, 2) circle (0.1);
\node at (1, 2.5) {(1, 2)};
\draw [color=blue, fill=blue] (2, 4) circle (0.1);
\node at (2, 4.5) {(2, 4)};
\draw [color=blue, fill=blue] (3, 8) circle (0.1);
\node at (3, 8.5) {(3, 8)};
\draw [color=blue, fill=blue] (4, 5) circle (0.1);
\node at (4, 5.5) {(4, 5)};
\draw [color=blue, fill=blue] (5, 10) circle (0.1);
\node at (5, 10.5) {(5, 10)};
\draw [color=blue, fill=blue] (6, 9) circle (0.1);
\node at (6, 9.5) {(6, 9)};
\draw [color=blue, fill=blue] (7, 7) circle (0.1);
\node at (7, 7.5) {(7, 7)};
\draw [color=blue, fill=blue] (8, 3) circle (0.1);
\node at (8, 3.5) {(8, 3)};
\draw [color=blue, fill=blue] (9, 6) circle (0.1);
\node at (9, 6.5) {(9, 6)};
\draw [color=blue, fill=blue] (10, 1) circle (0.1);
\node at (10, 1.5) {(10, 1)};
\end{tikzpicture}
\caption{$2^x$} 
\end{figure}
\end{center}
\hspace{5mm} 
\fi


Conversely, we can compute the discrete logarithms of elements based on $2$.
The result is shown in Table \ref{tab:logmod11}.

%\vspace{5mm}
\begin{table}[h]
\centering
\begin{tabular} {|l|l|l|l|l|l|l|l|l|l|l|}
\hline
x                           & 1   & 2   & 3 & 4 &  5  & 6  &  7  & 8 & 9 & 10   \\ \hline
$\log_2(x) \pmod{11}$ 		& 10   & 1  & 8 & 2 &  4  & 9  &  7  & 3 & 6 & 5    \\ 
\hline
\end{tabular}
\caption{Discrete logarithms in $\Z/11\Z$} \label{tab:logmod11}
\end{table}
%\vspace{5mm}
\end{example}

\iffalse
\hspace{5mm}
\begin{center}
\begin{figure} \label{fig42}
\begin{tikzpicture} [scale=0.7]
\draw[<->, thick] (0,11) node (yaxis) [above] {$log_2(x)$}
	|- (11,0) node (xaxis) [right] {$x$};
\draw [color=blue, fill=blue] (1, 10) circle (0.1);
\node at (1, 10.5) {(1, 10)};
\draw [color=blue, fill=blue] (2, 1) circle (0.1);
\node at (2, 1.5) {(2, 1)};
\draw [color=blue, fill=blue] (3, 8) circle (0.1);
\node at (3, 8.5) {(3, 8)};
\draw [color=blue, fill=blue] (4, 2) circle (0.1);
\node at (4, 2.5) {(4, 2)};
\draw [color=blue, fill=blue] (5, 4) circle (0.1);
\node at (5, 4.5) {(5, 4)};
\draw [color=blue, fill=blue] (6, 9) circle (0.1);
\node at (6, 9.5) {(6, 9)};
\draw [color=blue, fill=blue] (7, 7) circle (0.1);
\node at (7, 7.5) {(7, 7)};
\draw [color=blue, fill=blue] (8, 3) circle (0.1);
\node at (8, 3.5) {(8, 3)};
\draw [color=blue, fill=blue] (9, 6) circle (0.1);
\node at (9, 6.5) {(9, 6)};
\draw [color=blue, fill=blue] (10, 1) circle (0.1);
\node at (10, 1.5) {(10, 1)};
\end{tikzpicture}
\caption{$log_2(x)$} 
\end{figure}
\end{center}
\hspace{5mm} 
\fi


\begin{example}
Consider $\F_{2^3}=\F_{2}[x]/(f(x))$, where $f(x)=x^3+x+1\in\F_{2}[x]$ is irreducible.
Let $g$ be a root of $f(x)$. We compute the power of $g$ using modular exponentiation
and discrete logarithms of $\alpha\in \F_{2^3}^*$.
The results are shown in Table \ref{tab:expinf8} and Table \ref{tab:loginf8}, respectively.

%\vspace{5mm}
\begin{table}[h]
\centering
\begin{tabular} {|c|c|}
\hline
x   &  $g^x$     \\ \hline
1   &  $g$	\\ \hline
2   &  $g^2$ \\ \hline
3   &  $g+1$ \\ \hline
4   &  $g^2+g$ \\ \hline
5   &  $g^2+g+1$ \\ \hline
6   &  $g^2+1$ \\ \hline
7   &  $1$ \\ 
\hline
\end{tabular}
\caption{Modular exponentiation in $\F_{2^3}$} \label{tab:expinf8}
\end{table}

\begin{table}
\centering
\begin{tabular} {|c|c|}
\hline
$\alpha$ & $\log_g(\alpha)$ \\ \hline
$g$	 &  1\\ \hline
$g^2$ & 2 \\ \hline
$g+1$ & 3\\ \hline
$g^2+g$ & 4\\ \hline
$g^2+g+1$ & 5 \\ \hline
$g^2+1$ & 6 \\ \hline
$1$ & 7 \\ 
\hline
\end{tabular}
\caption{Discrete logarithms in $\F_{2^3}$} \label{tab:loginf8}
\end{table}
%\vspace{5mm} 
\end{example}

From the above examples, we can see that computing exponentiations and discrete logarithms are inverse operations.
If the field size is not too large then both computations are easy.
However, in the general case, computing exponentiation is easy and computing discrete logarithms is hard
in the sense that we have a polynomial-time algorithm for the former problem (such as exponentiating by squaring)
but no such an algorithm for the latter problem. Because of this property, the discrete logarithm problem over 
finite fields is considered a candidate of one-way function
used to construct cryptographic schemes. For example
Diffie and Hellman proposed a key exchange protocol \cite{DiffieHe76} based on the hardness of discrete logarithm problem
over finite fields.
ElGamal proposed a cryptosystem \cite{ElGamal85} based on the hardness of discrete logarithm problem over finite fields .




\begin{remark}
Parts of the content in this chapter are joint work with Qi Cheng and Daqing Wan and previously appeared in \cite{CWZ13}.
\end{remark}

\section{Related work}
Denote
\[L_{N}(\alpha)=\exp(O((\log N)^\alpha (\log\log N)^{1-\alpha})),\]
\[L_{N,c}(\alpha)=\exp((c+o(1))((\log N)^\alpha (\log\log N)^{1-\alpha})).\]
\subsection{Generic attacks}
Consider the problem of solving discrete logarithms over a cyclic group $G$ with $|G|=N$.
Let $g$ be a primitive element of $G$.
In the first step, we assume $G$ is a general group, that is, we do not have additional information on 
the structure of $G$. 

Shanks \cite{Shanks71} proposed the well known baby-step giant-step algorithm, which is deterministic. 
The basis idea of the algorithm is that we can write $\log_g(\alpha)=i_0m+j_0$, where $m=\lceil{\sqrt{N}}\rceil$ and $0 \leqslant i_0 \leqslant m-1, 0\leqslant j_0 \leqslant m$.
The algorithm consists of two steps:
\begin{itemize}
\item Giant-step: compute a list of $L=\{\alpha g^{-j} \mid 0\leqslant j \leqslant m\}$ and sort the list,
\item Baby-step: for each $0\leqslant i \leqslant m-1$, compute $g^{im}$; if $g^{i_0m}=\alpha g^{-j_0}\in L$, stop and return $i_0,j_0$.
\end{itemize}
From the baby-step, we get the relation $g^{i_0m}=\alpha g^{-j_0}$, which implies
\[
i_0m = \log_g(\alpha)-j_0.
\]
Thus we have 
\[
\log_g(\alpha)=i_0m+j_0.
\]
The running time of Shanks' algorithm is $O(\sqrt{N})$.
The space requirement is $O(\sqrt{N})$.

Pollard \cite{Pollard78} proposed two probabilistic algorithms, namely, the so called kangaroo method and rho method.
Both of the algorithms run in expected time $O(\sqrt{N})$ with less space. 


\subsection{Index calculus method}
In \cite{Odlyzko84} and \cite{Odlyzko00}, the author attributed the basic ideas of index calculus method to
Western and Miller \cite{WesternMi68} and Kraitchik \cite{McCurley90}. And the author attributed the invention of
the index calculus method to Adleman \cite{Adleman79}, Merkle \cite{Merkle79}, and Pollard \cite{Pollard78}.
This algorithm is a probabilistic one. It is based on the fundamental property of discrete logarithms that
\[
\log\prod_{i=1}^{n}\alpha_i = \sum_{i=1}^{n}\log\alpha_i.
\]
If we get one relation about a set of variables $\alpha_1,\ldots,\alpha_m$ of the form
\[
\prod_{i=1}^{m}\alpha_i^{e_i} = 1,
\]
then it implies
\[
\sum_{i=1}^{m}e_i\log_g{\alpha_i}=0.
\]
If we get sufficiently many such relations, we can solve the linear system to get the 
discrete logarithms $\log_g{\alpha_i}$ for $1\leqslant i\leqslant m$.
In the index calculus method, this set is called a factor base. 
The concept of smoothness also plays an important role in the calculus method.


The general framework consists of three phases:
\begin{itemize}
\item Phase 1. Finding relations among the logarithms of elements in the factor base (such as via guessing and checking),
\item Phase 2. Solving the linear equations to get the logarithms of elements in the factor base,
\item Phase 3. Finding individual logarithm by reducing it to the factor base.
\end{itemize}

Historically, Adleman \cite{Adleman79} published the first subexponential time algorithm for the discrete logarithm over finite fields.
The original algorithm solves this problem in a prime field, that is, the field size is a prime. 
The asymptotic running time
is $L(1/2)$. Adleman's algorithm relies on similar ideas used by Morrison and Brillhart \cite{MorrisonBr75} for factoring integers.
They both make use of the concepts of a factor base and smoothness of an element over the factor base.
We describe a modified version of Adleman's algorithm briefly according to the general framework. Suppose we are going to solve the discrete logarithm
in $\F_q$ where $q$ is a prime and $q-1=\prod_{i=1}^{i=n}p_i^{e_i}$. Suppose $\F_q^*=\langle g \rangle$ and we want to compute $\log_g(\alpha)$.
The plan is to solve $\log_{g}(\alpha)\pmod {p_j^{e_j}},1\leqslant j \leqslant n$ first,
then calculate $\log_{g}(\alpha)\pmod {q-1}$ using Sun Zi Theorem (Chinese Remainder Theorem).
\begin{enumerate}
\item Choose a bound $B=L(1/2,c)$, where $c$ is a small constant. The factor base includes all positive prime numbers less than $B$.
Randomly guess an integer $e$ and test whether $g^e$ is $B$-smooth. If so, we get
\[
g^e = \prod_{p<B}p^{e_p},
\]
which implies 
\[
e = \sum_{p<B}e_p\log_g(p).
\]
Repeat this until enough linear equations are collected.
\item Solve the linear equations using Gaussian elimination over $\Z_{p_j^{e_j}}$.
Thus we get the discrete logarithms of elements in the factor base.
\item To compute the target $\log_g(\alpha)$, we repeat choosing a random integer $m$ until $\alpha g^m$ is $B$-smooth.
If so, then we can compute $\log_g(\alpha)$ from the knowledge of the discrete logarithms of elements in the factor base.
\end{enumerate}

Hellman and Reyneri \cite{HellmanRe82} generalized Adleman's algorithm to a field of fixed characteristic $p\in\Z$.
The asymptotic running time of their algorithm is $L(1/2)$.
In a field of composite order $|\F_q|=p^k$, the elements are represented as polynomials. In this case, Hellman and Reyneri \cite{HellmanRe82}
make use of smoothness of a polynomial.
Consider the field $\F_{2^k}=\F_2[x]/(f(x))$ for example, where $f(x)\in\F_2[x]$ is irreducible with degree $k$. 
Suppose $\F_{2^k}^*=\langle g \rangle$ and we want to determine $\log_g(\alpha)$.
We still follow the general framework to describe the modified algorithm.
\begin{enumerate}
\item Choose a polynomial degree bound $B=L(1/2,c)$, where $c$ is a small constant. The factor base consists of all irreducible 
polynomials with degree less than $B$. Randomly guess an integer $0 < e < 2^k-1$ and test whether $g^e$ is $B$-smooth. If so, we get
\[
g^e = \prod_{\deg(p_i(x))< B}{p_i(x)^{e_{p_i(x)}}},
\]
which gives the relation
\[
e = \sum_{\deg{p_i(x)}<B}e_{p_i(x)}\log_g(p_i(x)).
\]
Continue the procedure until we collect enough relations.
\item Solve the linear system over $\Z/(2^k-1)\Z$ to find the discrete logarithms of elements in the factor base.
\item To compute the target $\log_g(\alpha)$, we repeat choosing a random integer $m$ until $\alpha g^m$ is $B$-smooth.
If so, then we can compute $\log_g(\alpha)$ from the knowledge of the discrete logarithms of elements in the factor base.
\end{enumerate}

To improve the time complexity of Adleman's algorithm, one can speed up the process of finding relations,
which plays an essential role in the algorithm.
Blake, Mullin, and Vanstone \cite{BMV84} proposed to do so using the idea of systematic equations. 
Generalizing the concept of systematic equations, Coppersmith \cite{Coppersmith84} developed the first algorithm with 
asymptotic time $L(1/3)$ for a field of characteristic $2$.
Coppersmith's algorithm takes advantage of the Frobenius map and the special representation of the field.
Explicitly, let $\F_{2^n}=\F_2[x]/(P(x))$, where $P(x)=x^n+Q(x)$ is irreducible over $\F_2$ of degree $n$ and $Q(x)$ is a low degree polynomial.
He chooses $k$ a power of $2$ near $\sqrt{n}$ and computes $n=rk-s$, where $0\leqslant s < k$.
Coppersmith then generates his systematic equations through the following way: firstly, he chooses a pair of low
degree polynomials $A(x)$ and $B(x)$ such that $\gcd(A(x),B(x))=1$. Let $C(x)=x^rA(x)+B(x)$ and $D(x)=C(x)^k$.
Then, he reduces the following:
\[
\begin{aligned}
D(x) & = C(x)^k \mod P(x) \\
     & = x^{rk}A(x)^k+B(x)^k \mod P(x)\\
     & = x^sQ(x)A(x)^k+B(x)^k \mod P(x).
\end{aligned}
\]
Both sides of the systematic equation have degrees $O(\sqrt{n})$. Thus the probability for both sides
to be smooth is much higher than $gx^e$ for a randomly chosen $0\leqslant e < 2^k-1$.

Semaev \cite{Semaev98} generalized Coppersmith's algorithm to any field of fixed characteristic.


Adleman and Demarrais \cite{AdlemanDe93} developed the first subexponential algorithm for discrete logarithms
over all finite fields $\F_{p^n}$ with expected running time $L(1/2)$. Their algorithm consists of two subroutines,
both of which are some variations of the index calculus method.
\begin{itemize}
\item If $n<p$, they represent the field $\F_{p^n}$ as $\mathcal{O}/(p)$, where $\mathcal{O}$ is some number ring and
$(p)$ is the prime ideal generated by $p$. An element $\alpha\in \mathcal{O}$ is smooth if
the prime ideals in the factorization of $(\alpha)$ have norms below a given bound.
\item When $n\geqslant p$, they represent $\F_{p^n}$ by $\F_p[x]/(f(x))$, where $f(x)\in \F_p[x]$ is irreducible with degree $n$.
The element $g(x)\in \F_p[x]/(f(x))$ is smooth if its irreducible factors all have degree less than a given bound.
\end{itemize}





\subsection{Number field sieve and function field sieve}
The  state-of-the-art general-purpose methods for 
solving the discrete logarithm problem over finite fields 
are the number field sieve and 
the function field sieve, which originated from 
the index-calculus algorithm. All these algorithms run
in subexponential time. 
%where $0 < \alpha < 1$. 
For a finite field $\F_q$,
successful efforts have been made to reduce the heuristic 
complexity of these algorithms 
from $L_{q} (1/2)$ to $L_{q} (1/3)$.

The number field sieve technique was originally developed to factor big integers $N$ \cite{BLP93, LLMP90}.
%Special NFS and generalized NFS.
The generalized number field sieve is the state-of-the-art general-purpose algorithm for factorization. 

Inspired by the technique of number field sieve to factor large integers,
Gordon \cite{Gordon93} introduced the idea of using the number field sieve
to solve discrete logarithms in a finite field $\F_p$ of prime order.
The asymptotic running time of Gordon's algorithm is $L_p(1/3)$.

Let $m$ be an integer and $f(x)\in\Z[x]$ be an irreducible monic polynomial such that $(p,\Delta_f)=1$ and 
$f(m) \equiv 0 \pmod p$. Also, let $\alpha\in \mathbf{C}$ be a root of $f(x)$, which is used to construct
a number field $K=\Q(\alpha)$. Let $\mathcal{O}_K$ be the ring of algebraic integers in $K$.
Choosing $\mathfrak{p}=(p,\alpha-m)$, Gordon represents the filed as
\[
\F_p \cong \mathcal{O}/\mathfrak{p}.
\]


Subsequently, the number field sieve method was investigated further by \cite{JL03,Schirokauer93,Schirokauer05,SWD96,Weber95,Weber96}.

Adleman \cite{Adleman94} firstly applied the function field sieve to solve discrete logarithms in a field of 
small characteristic, which is an analogous of the number field sieve.
Later, Adleman and Huang \cite{AdlemanHu99} made an improvement on the function field sieve. 
Function field sieve was further studied in \cite{GHPSV04, JouxLe02}.

Joux and Lercier \cite{JouxLe06} developed some variations of function field sieve, which applies to
$\F_{q^n}$ where $q$ is a medium-sized prime power. The expected running time is $L(1/3)$.
Their key idea is to speed up the sieving stage by an efficient representation of the field.

Joux, Lercier, Smart and Vercauteren \cite{JLSV06} studied several variations of the number field sieve,
which applies to the case $\F_{p^n}$, where $p$ is a medium to large prime. The asymptotic 
running time is $L(1/3)$ if $n$ is not too big. 

Remarkably, the combination of the above two algorithms solve the discrete logarithms in $\F_{p^n}$
in all cases with heuristic time complexity $L_{p^n}(1/3)$. 


\subsection{Recent breakthroughs}
Joux \cite{Joux13b} designed the first algorithm with heuristic running time $L(1/4)$ to compute discrete 
logarithms in a field of small characteristic. Joux's approach combines the features of 
of Coppersmith's algorithm \cite{Coppersmith84} and Joux-Lercier's method \cite{JouxLe06} and Joux's
pinpointing technique \cite{Joux13a}.
Joux's $L(1/4)$ algorithm relies on three basic ideas as follows:
\begin{enumerate}
\item Joux represents the field $\F_{q^k}$ as $\F_q[x]/(f(x))$ where $f(x)$ is an irreducible factor
of $h_1(x)x^q-h_0(x)$, where $h_0(x)$ and $h_1(x)$ are of low degree. The advantage of this 
representation is that in such a field one has the relation
\[
x^q = \frac{h_0(x)}{h_1(x)}.
\]
\item Observing the well known fact that 
\[
X^q-X = \prod_{\alpha\in\F_q}(X-\alpha),
\]
Joux uses this equation as his source systematic equation.
\item To amplify the initial systematic equations, Joux makes use of the following homographies:
\[
X\rightarrow \frac{aX+b}{cX+d}.
\]
\end{enumerate}

Also, Gologlu, Granger, McGuire, and Zumbragel \cite{GGMZ13} made an improvement in the case when 
characteristic is 2. 

Finally, these sequence of breakthrough results  \cite{GGMZ13, Joux13a, Joux13b} 
recently on the discrete logarithm problem over finite fields culminated 
in a discovery of a quasi-polynomial algorithm 
for small characteristic fields, which we call BGJT-algorithm \cite{BGJT13v1,BGJT13v2}.
For a finite field $ \F_{q^{2 k}} $ with $ k < q $,
their algorithm runs in heuristic time  $ q^{O(\log k)} $. 
This result, if correct, essentially removes the discrete logarithm
over small characteristic  fields from hard problems in cryptography.

\section{Right cosets of $PGL_2(\F_q)$ in $PGL_2(\F_{q^2})$}
Both \cite{BGJT13v2} and \cite{Joux13b} need to compute the right cosets of $PGL_2(\F_q)$ in $PGL_2(\F_{q^2})$
as the preliminary. In this section, we presents an classification of such right cosets.


\begin{proposition}\label{coset}
Let $b\in\F_{q^2},c\in\F_{q^2}\setminus\F_q$ be variables. Given 
\begin{equation} \label{wvequ}
v=\frac{b^q-b}{c-c^q}\in \F_q, w=\frac{1-bc^q}{c-c^q}\in \F_{q^2}, 
\end{equation}
let $(b_1,c_1),(b_2,c_2)$ be any two pairs satisfying (\ref{wvequ}).
%there are $q+1$ many corresponding $(b,c)$ pairs. 
Let 
\[A_1=\left( \begin{array}{cc} 1 & b_1 \\ c_1 & 1 \end{array} \right), A_2=\left( \begin{array}{cc} 1 & b_2 \\ c_2 & 1 \end{array} \right).
\]
If both $A_1$ and $A_2$ are not singular, then they are in the same right coset of $PGL_2(\F_q)$ in $PGL_2(\F_{q^2})$.
\end{proposition}
\begin{proof}
From (\ref{wvequ}), we deduce
\[
\left\{\begin{array}{l}
(c-\frac{w^q}{v})^{q+1}=(\frac{w^q}{v})^{q+1}-\frac{1}{v} \\
b=-vc+w+w^q.
\end{array}\right.
\] 
Without loss of generality, assume $\gamma^{q+1}=(\frac{w^q}{v})^{q+1}-\frac{1}{v},\zeta_1^{q+1}=\zeta_2^{q+1}=1$ and
\[
c_1=\frac{w^q}{v}+\zeta_1\gamma, c_2=\frac{w^q}{v}+\zeta_2\gamma,
\]
where $\zeta_1,\zeta_2$ are two distinct $(q+1)$-th roots of unity.
Hence
\[
b_1=-vc_1+w+w^q=w-v\zeta_1\gamma,
\]
\[
b_2=-vc_2+w+w^q=w-v\zeta_2\gamma .
\]
It follows that
\[
A_1=\left( \begin{array}{cc} 1 & w-v\zeta_1\gamma \\ \frac{w^q}{v}+\zeta_1\gamma & 1 \end{array} \right), 
A_2=\left( \begin{array}{cc} 1 & w-v\zeta_2\gamma \\ \frac{w^q}{v}+\zeta_2\gamma & 1 \end{array} \right).
\]
Since $A_2$ is not singular, we deduce
\[
A_2^{-1}=\frac{1}{\det(A_2)}\left( \begin{array}{cc} 1 & -w+v\zeta_2\gamma \\ -\frac{w^q}{v}-\zeta_2\gamma & 1 \end{array} \right).
\]
Thus,
\[
\begin{aligned}
A_1A_2^{-1} &= \frac{1}{\det(A_2)} \left( \begin{array}{cc} (v\zeta_1\gamma-w)(\frac{w^q}{v}+\zeta_2\gamma)+1  & -v(\zeta_1\gamma-\zeta_2\gamma) \\ \zeta_1\gamma-\zeta_2\gamma &  (v\zeta_2\gamma-w)(\frac{w^q}{v}+\zeta_1\gamma)+1\end{array} \right) \\
		&=\frac{1}{\det(A_2)} \left( \begin{array}{cc} m_{11} & m_{12} \\ m_{21} & m_{22} \end{array} \right).
\end{aligned}
\]
Note that $m_{12}=-vm_{21},m_{11}-m_{22}= (w^q+w)m_{21}$. The last step is to prove $\frac{m_{11}}{m_{21}}\in \F_q$.
Let $\delta=\frac{m_{11}}{m_{21}}$.
Note that
\[
\begin{aligned}
\delta\in \F_q &\iff \delta=\delta^q \\
			   &\iff m_{11}m_{21}^q=m_{11}^qm_{21} \\
			   &\iff m_{11}m_{21}^q\in \F_q.
\end{aligned}
\] 
Since $\gamma^{q+1}=(\frac{w^q}{v})^{q+1}-\frac{1}{v}=\frac{w^{q+1}-v}{v^2}$, we have $\frac{w^{q+1}}{v}=v\gamma^{q+1}+1$. 
Hence 
\[
m_{11} = w^q\zeta_1\gamma+v\zeta_1\gamma\zeta_2\gamma-w\zeta_2\gamma-v\gamma^{q+1}.
\]
Thus
\[
m_{11}m_{21}^q  = \gamma^{q+1}\{ (w^q+w)-(w\zeta_1^q\zeta_2+w^q\zeta_1\zeta_2^q) + v(\zeta_2\gamma+\zeta_2^q\gamma^q) -v(\zeta_1\gamma+\zeta_1^q\gamma^q)\}.
\]
Since 
\[
\gamma^{q+1}\in\F_q,
\]
\[
w^q+w\in\F_q,w\zeta_1^q\zeta_2+w^q\zeta_1\zeta_2^q\in\F_q,
\]
\[
\zeta_2\gamma+\zeta_2^q\gamma^q\in\F_q,\zeta_1\gamma+\zeta_1^q\gamma^q\in\F_q,
\]
we deduce $m_{11}m_{21}^q\in \F_q$, which implies $\frac{m_{11}}{m_{21}}\in \F_q$ and $\frac{m_{22}}{m_{21}}\in \F_q$.
Thus 
\[
\begin{aligned}
A_1A_2^{-1} &=\frac{\zeta_1\gamma-\zeta_2\gamma}{\det(A_2)}\left( \begin{array}{cc}\frac{m_{11}}{m_{21}} & -v \\ 1 & \frac{m_{22}}{m_{21}} \end{array} \right)  \\
			&\in PGL_2(q),
\end{aligned}
\]
which implies that $A_1$ and $A_2$ are in the same right coset of of $PGL_2(\F_q)$ in $PGL_2(\F_{q^2})$.
\end{proof}

\begin{remark}
Following an approach similar to this one, one can also prove that $A_1$ and $A_2$ are in the same left coset of of $PGL_2(\F_q)$ in $PGL_2(\F_{q^2})$.
\end{remark}

\begin{proposition}
Let $\F_{q^2}^*=\langle g \rangle$. Each representative of a right coset of $PGL_2(\F_q)$ in $PGL_2(\F_{q^2})$ is equivalent to one of the following four types:
\begin{enumerate}
\item  $\left( \begin{array}{cc} 1 & b \\ c & 1 \end{array} \right)$, where $b,c\in \F_{q^2}$.
\item  $\left( \begin{array}{cc} 1 & b_1 \\ g & d_2g \end{array} \right)$, where $b_1,d_2\in \F_q$.
\item  $\left( \begin{array}{cc} 0 & 1 \\ c & d \end{array} \right)$, where $c,d\in \F_{q^2}$.
\item  $\left( \begin{array}{cc} 1 & 0 \\ c & d \end{array} \right)$, where $c,d\in \F_{q^2}$.
\end{enumerate}
\end{proposition}
\begin{proof}
We determine the equivalence relation case by case. 
Let 
\[
\left( \begin{array}{cc} a & b \\ c & d \end{array} \right)= \left( \begin{array}{cc} a_1+a_2g & b_1+b_2g \\ c_1+c_2g & d_1+d_2g \end{array} \right)
\]
be a representative of a right coset of $PGL_2(\F_q)$ in $PGL_2(\F_{q^2})$,
where 
\[
a_1,a_2,b_1,b_2,c_1,c_2,d_1,d_2\in\F_q.
\]

First of all, if $a=0$, then the matrix can be reduced to type (3) after dividing $b$ since $b\neq 0$.
In the following, we assume $a \neq 0$.
Without loss of generality, we assume $a=1$ and consider the matrix 
\[
\left( \begin{array}{cc} 1 & b_1+b_2g \\ c_1+c_2g & d_1+d_2g \end{array} \right).
\]
We have the following cases:

\noindent
\textbf{Case I. $b_2\neq 0$}

Subtracting $\frac{d_2}{b_2}$ times the first row from the second row, the matrix becomes
\[
\left( \begin{array}{cc} 1 & b \\ c' & d_1' \end{array} \right),
\]
where $c'\in \F_{q^2}, d_1'\in \F_q$.
\begin{enumerate}
\item If $d_1'=0$, the matrix is equivalent to type (4).
\item If $d_1'\neq 0$, the matrix is equivalent to type (1) since we can divide the second row by $d_1'$.
\end{enumerate}

\noindent
\textbf{Case II. $b_2=0$}

If $b_1=0$, then the matrix is equivalent to type (4).

If $b_1\neq 0$, then the matrix becomes 
\[
\left( \begin{array}{cc} 1 & b_1 \\ c'=c_1'+c_2'g & d_2g \end{array} \right)
\]
after subtracting $d_1/b_1$ times first row from the second row.
\begin{enumerate}
\item If $d_2=0$, then the matrix can be reduced to type (4).

\item  Assume $d_2\neq 0$.
\begin{enumerate}
\item If $c_1'=0,c_2'=0$, then the matrix can be reduced to type (3).
\item If $c_1'=0,c_2'\neq 0$, then the matrix can be reduced to type (2) by dividing the second row by $c_2'$.
\item If $c_1'\neq 0$, subtracting $\frac{1}{c_1'}$ times the second row from the first row, we get 
\[
\left( \begin{array}{cc} -\frac{c_2'}{c_1'}g & b' \\ c' & d_2g \end{array} \right).
\]
Dividing the matrix by $g$, we get
\[
\left( \begin{array}{cc} -\frac{c_2'}{c_1'} & b'g^{-1} \\ c'g^{-1} & d_2 \end{array} \right).
\]
\begin{enumerate}
\item If $c_2'=0$, the matrix can be reduced to type (3).
\item If $c_2'\neq 0$, dividing the first row by $-\frac{b_2'}{b_1'}$ and the second row by $d_2$, 
the matrix is reduced to type (1).
\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{proof}


\begin{proposition}
Let 
\[
\left( \begin{array}{cc} 0 & 1 \\ c & d \end{array} \right)
=
\left( \begin{array}{cc} 0 & 1 \\ c_1+c_2g & d_1+d_2g \end{array} \right)
\]
be one representative of a right coset of $PGL_2(\F_q)$ in $PGL_2(\F_{q^2})$,
where $c_1,c_2,d_1,d_2\in\F_q$.
Then it is equivalent to one of the following types:
\begin{enumerate}
\item  $\left( \begin{array}{cc} 0 & 1 \\ g &  \beta_2g \end{array} \right)$, where $\beta_2 \in \F_q$.
\item  $\left( \begin{array}{cc} 0 & 1 \\ 1+\alpha_2g & \beta_2g \end{array} \right)$, where $\alpha_2,\beta_2\in \F_q$.
\end{enumerate}
\end{proposition}

\begin{proof} There are two cases to consider.
\begin{enumerate}
\item Assume $c_1 = 0$. If $d_1 \neq 0$, subtracting $d_1$ times the first row from the second row, we get
\[
\left( \begin{array}{cc} 0 & 1 \\ c_2g & d_2g \end{array} \right).
\]
If $d_1=0$, then the matrix is of the above form already.
Since $c_2\neq 0$, after dividing the second row by $c_2$, the matrix is reduced to type (1).

\item Assume $c_1 \neq 0$. If $d_1 \neq 0$, subtracting $d_1$ times the first row from the second row, we get
\[
\left( \begin{array}{cc} 0 & 1 \\ c_1+c_2g & d_2g \end{array} \right).
\]
If $d_1=0$, then the matrix is of the above form already.
Dividing the second row by $c_1$, we get
\[
\left( \begin{array}{cc} 0 & 1 \\ 1+c_2g & \frac{d_2}{c_1}g \end{array} \right).
\]
Thus the matrix is reduced to type (2).
\end{enumerate}
\end{proof}

Similarly, we have the following conclusion.
\begin{proposition}
Let 
\[
\left( \begin{array}{cc} 1 & 0 \\ c & d \end{array} \right)
=
\left( \begin{array}{cc} 1 & 0 \\ c_1+c_2g & d_1+d_2g \end{array} \right)
\]
be one representative of a right coset of $PGL_2(\F_q)$ in $PGL_2(\F_{q^2})$.
Then it is equivalent to one of the following types:
\begin{enumerate}
\item $\left( \begin{array}{cc} 1 & 0 \\ \alpha_2g & g \end{array} \right)$, where $\alpha_2 \in \F_q$.
\item $\left( \begin{array}{cc} 1 & 0 \\  \alpha_2g & 1+\beta_2g  \end{array} \right)$, where $\alpha_2,\beta_2\in \F_q$.
\end{enumerate}
\end{proposition}






\section{Where does the computation of the original BGJT algorithm really happen? }

Suppose that we need to compute discrete logarithm in the field 
$ \F_{q^{2k}} $, where $q > k>1$. 
A main technique in \cite{BGJT13v1}, which bases on smooth polynomials,
is to find a nice ring generator
$ \zeta $ of $ \F_{q^{2k}}=\F_{q^2}[\zeta]$ over $  \F_{q^2} $ 
satisfying \[ x^q = h_0(x)/h_1(x),  \] 
where $ h_1 $ and $ h_0 $ are polynomials of very small degree.
In many places of the computation, polynomial degrees can be dropped 
quickly by replacing $ x^q $ with $ h_0 (x)/h_1 (x) $, which
allows an effective attack based on smoothness. 

The main issue with this approach is that
the computation really takes place in the ring
$ \F_{q^2}[x]/(x^q h_1 (x) - h_0 (x)) $, where in the analysis of \cite{BGJT13v1},
the computation is assumed to be in $ \F_{q^2}[x]/ (f(x)) $, 
where $f(x)$ is the minimal polynomial of $ \zeta $ over $ \F_{q^2} $.   
Since $f(x)$ divides $   x^q h_1 (x) - h_0 (x)$,  there is a natural surjective ring homomorphism   
\[ \F_{q^2}[x]/(x^q h_1 (x) - h_0 (x)) \rightarrow  \F_{q^2}[x]/ (f(x)). \] 
But  the 
former ring, which is a direct sum of the latter field (if $f(x)$ is a simple factor of 
$x^q h_1 (x) - h_0 (x)$) and a few other  rings,
 is much larger in many cases. 
The computation thus
can be affected by the other rings, rendering
 several conjectures in \cite{BGJT13v1, Joux13b}  problematic.


Interestingly, for the Kummer extension of the form
$  \F_{q^2}[x]/ (x^{q-1} - a) $, everything is fine. This is because 
the difference between the ring $ \F_{q^2}[x]/ (x^q - ax) $ 
and the field is rather small.
The discrete logarithm of $x$, which is a  zero divisor in the former ring,
can be computed easily in the latter field, since it  belongs to a subgroup
of a small order (dividing $(q-1) (q^2-1)$)  in the  field. This is consistent with 
all announced practical  implementations. 
%It is 
%enough to seperate the latter from the former.

However, in case of more difficult non-Kummer extensions,  we discover that there are multiple problems.
\begin{enumerate} 
\item First, if $x^q h_1(x)-h_0(x)$ has linear factors over $\F_{q^2}$,  the discrete logarithms of
these linear factors cannot be computed in polynomial time,
invalidating a basic assumption in \cite{BGJT13v1}. One can verify that
most of polynomials given in \cite[Table 1]{Joux13b} have linear factors.
\item Second, even at the stage of finding discrete logarithms of linear elements, 
we show that there are additional serious restrictions on the choice of $h_0(x)$ and $h_1(x)$. 
For example, if  $x^q h_1(x)-h_0(x)$ has another irreducible factor over $\F_{q^2}$ of degree $k_i$  satisfying 
$\gcd(k_i,k)>1$, we do not see how the algorithm can work. 
We propose to select $h_0(x)$ and $h_1(x)$ 
such that $x^qh_1(x)-h_0(x)$ has only one irreducible factor $f(x)$ over $\F_{q^2}$ of degree $k$, 
and all other irreducible factors over $\F_{q^2}$ have degrees bigger than one and relatively prime to $k$. Under these assumptions, 
we give an algorithm which will find the discrete logarithm of any linear 
element in polynomial time, under a heuristic assumption supported by our theoretical results 
and numerical data. 
\item For a non-linear element, a clever idea, the so-called
QPA-descent,  was proposed in
\cite{BGJT13v1} to reduce its degree, until its relation to linear factors 
can be found. 
While the above two problems about linear factors can be fixed under 
our newly improved heuristic 
assumptions, another serious problem
is  that there are  {\em traps} in the QPA-descent.
For these traps, the QPA-descent described in \cite{BGJT13v1} 
will not work at all.
They will also block the descent of other elements,
hence severely affecting the usefulness of the new algorithm.
\end{enumerate}
%We  propose a descent strategy that avoids the traps,
%without altering the quasi-polynomial time complexity. 
%The modified algorithm is also heuristic.
%We have done a few numerical studies to confirm the 
%heuristic. 

%In summary, for  large non-Kummer
%fields,  we believe that the problem can be significantly 
%more subtle than previously thought and 
%further study needs to be conducted in order 
%to fully understand the effect of the new algorithm.


% To find the discrete logarithm of the factor base, we propose not to
% include the linear factors
% of $x^q h_1(x) - h_0 (x)$ in factor base.

% And we propose to add a few relation specific to the field.
% Is it possible to add relations specifically 
% targeting the field? It is not easy in general, 
% since for the algorithm to
% work, it is essential that 
% we replace $ x^q $ by $ h_0 (x)/h_1 (x) $. 


\section{Finding primitive elements and discrete logarithms of linear factors}
\subsection{Using SNF of relation matrices to determine group structures}
Firstly, we recall the definition of the finitely generated group \cite{DummitFo04}.

\begin{definition}
Let $G$ be a group written multiplicatively. It is finitely generated if
there exists $\{g_1,\ldots,g_n\}\subset G$ such that for any $\alpha\in G$,
there exist $e_1,\ldots,e_m\in \Z$ such that
\[
\alpha = \prod_{i=n}^{m}g_i^{e_i}.
\] 
\end{definition}


The following is the well known fundamental theorem of finitely generated abelian groups \cite{DummitFo04}:

\begin{theorem} \label{strutFiniteGenerate}
Let $G$ be a finitely generated abelian group. Then there is an isomorphism
\[
G \cong \Z ^{r}\times \Z/n_1\Z \times \Z/n_2\Z \times \cdots \times \Z/n_{s}\Z,
\]
where $r,s\geqslant 0$, $n_1\geqslant 2$ and $n_i|n_{i+1}$ for $1\leqslant i \leqslant s-1$.
Furthermore, the $r$ and $n_i$ are uniquely determined by $G$.
The integer $r$ is called the free rank or Betti number
of $G$ and $n_1,n_2,\ldots,n_s$ are called the invariant factors of $G$. The isomorphic expression
of $G$ is called the invariant factor decomposition of $G$.
\end{theorem}

Let $G$ be a finite abelian group of order $|N|$. Enge \cite{Enge01} developed an algorithm to determine the 
structure of $G$. The basic idea is to compute the SNF of the relation lattice.
We describe this method briefly. Let the factor base $S=\{g_1,g_2,\ldots,g_n\}$ be sufficiently large 
such that it generates $G$. Consider the group homomorphism
\[
\phi : \Z^n \rightarrow G
\]
given by
\[
(e_1,e_2,\ldots,e_n) \mapsto \prod_{i=1}^{n}g_i^{e_i}.
\]
Since $S$ generates $G$, $\phi$ is surjective and its kernel $\Gamma$ is a full-dimensional lattice of determinant $N$
such that $G\cong \Z^n/\Gamma$. Thus the object of determining the structure of $G$ is reduced to determining 
the structure of $\Z^n/\Gamma$.

Enge's algorithm thus consists of two phases:
\begin{enumerate}
\item Collecting relations to construct a relation matrix $A$ which approaches $\Gamma$ well by some criterion. 
\item Computing the SNF of $A$ to find the invariant factors of $G$ and the generators. 
\end{enumerate}

\subsection{Finding the discrete logarithm of the linear factors}

We first review the new algorithm in \cite{BGJT13v1,BGJT13v2}. 
Suppose that the discrete logarithm
is sought over the field $\F_{q^{2k}}$ with $k < q$.
%is assumed to be prime for simplicity. 
For other small characteristic fields,
for example, $\F_{p^k} $ ( $ p < k $  ), 
one first embeds it into a slightly larger field:
\[ \F_{p^k} \rightarrow \F_{q^k} \rightarrow  \F_{q^{2k}} 
\]
where $q= p^{\ceil{\log_p k}}$. A quasi-polynomial time
algorithm for  $  \F_{q^{2k}} $ implies a quasi-polynomial
time algorithm for $\F_{p^k} $.
We  assume that
\[ \F_{q^{2k}} = \F_{q^2}[\zeta] \]
where $ \zeta^q = \frac{h_0 (\zeta) }{h_1 (\zeta)}  $.
Here $h_0   $ and $ h_1 $ are polynomials over $ \F_{q^2} $ 
relatively prime to each other, and
of a constant degree. 
In particular, $\deg(h_0) < q +\deg(h_1)$. 
To find such a nice ring generator $\zeta$, one searches over 
all the polynomials
$h_0(x)$ and $h_1(x)$ of a constant degree in $\F_{q^2}[x]$, until
 $h_1(x) x^q - h_0 (x)$ has an irreducible factor $ f(x) $ 
of degree $k$ with multiplicity one.  Let the factorization be
\begin{equation} \label{ringpolfac}
 x^q h_1 (x) - h_0 (x) = f(x) \prod_{i=1}^l  (f_i (x))^{a_i} 
\end{equation}
where the polynomials $f(x)$ and $f_i(x)$'s are irreducible and 
pair-wise prime.
Denote the degree of $f_i (x)$ by $k_i$.

\begin{remark}
In practice, it is enough to search 
only a  quadratic polynomial $ h_0 $ (not necessarily monic)
and a monic linear polynomial $ h_1 $ in $\F_{q^2}[x] $.  
However, proving the existence of such polynomials for any 
constant degree such that  $x^q h_1 (x) - h_0 (x)$ has the 
desired factorization pattern
seems to be out of reach by current techniques.
\end{remark}

For simplicity we assume that $ h_1(x) $ is monic and linear.
Most of the known algorithms start by  computing the
discrete logarithms of elements in a special set called a factor base,
which usually contains  small integers, or low degree polynomials.
In the new approach \cite{BGJT13v1, BGJT13v2, Joux13b},
the factor base consists of  the linear polynomials 
$ \zeta + \alpha  $ for all $ \alpha \in \F_{q^2} $, and
an algorithm is designed to compute the discrete logarithms of 
all the elements in the factor base. It is conjectured that
this algorithm runs in polynomial time.
%To compute the discrete logarithms of elements in the factor base,
One starts the algorithm with the identity:
\[ \prod_{\alpha \in \F_q } (x-\alpha) = x^q - x.  \]
Then apply the M$\ddot{o}$bius transformation
\[ x \mapsto \frac{a x + b}{cx +d} \]
where the matrix $ m = \begin{pmatrix} a & b \\ c & d
\end{pmatrix} \in \F_{q^2}^{2 \times 2}$ is nonsingular.
We have 
\[ \prod_{\alpha \in \F_q } (\frac{a x + b}{cx +d} -\alpha) 
= (\frac{a x + b}{cx +d})^q - \frac{a x + b}{cx +d}.  \]
Clearing the denominator:
\begin{eqnarray*}
&&(cx +d) \prod_{\alpha \in \F_q } ((a x + b) -\alpha (cx +d)) \\
&=& (a x + b)^q (cx +d) - (a x + b) (cx +d)^q \\
&=& (a^q x^q + b^q) (cx+d) - (ax+b)(c^q x^q + d^q).  
\end{eqnarray*}
Multiplying both sides by $h_1(x)$ and replacing $x^qh_1(x)$ by $h_0(x)$, we obtain 
%\begin{eqnarray*}
%&&(cx +d) \prod_{\alpha \in \F_q } ( (a x + b) - \alpha (cx +d))\\
%&=&  (a^q \frac{h_0(x)}{h_1(x)} + b^q) (cx+d)
%- (ax+b)(c^q \frac{h_0(x)}{h_1(x)} + d^q) \\
%$&& \pmod { x^q h_1(x) - h_0(x)}
%$\end{eqnarray*}
%That is
\begin{eqnarray*} 
&& h_1 (x) (cx +d) \prod_{\alpha \in \F_q } ( (a x + b) - \alpha (cx +d))\\
&=&  (a^q {h_0(x)} + b^q h_1 (x) ) (cx+d)
- (ax+b)(c^q {h_0(x)} + d^q h_1(x) )  \\
&& \pmod { x^q h_1(x) - h_0(x)}.
\end{eqnarray*}
If the right-hand side  can be 
factored into a product of linear factors over $ \F_{q^2} $,
we obtain a relation of the form 
\begin{equation}\label{mrelation}
\lambda^{e_0} \prod_{i=1}^{q^2} (x + \alpha_i)^{e_i} =\prod_{i=1}^{q^2} (x + \alpha_i)^{e'_i}\pmod { x^q h_1(x) - h_0(x)} ,
\end{equation}
where $\lambda$ is a multiplicative generator of $\F_{q^2}$,
 $ \alpha_1 = 0, \alpha_2, \alpha_3, \dotsc, \alpha_{q^2}  $
is a natural ordering of elements in $ \F_{q^2} $, and $ e_i $'s
and $ e'_i $'s are non-negative integers.

 
Following the same notations in \cite{BGJT13v1}, 
let $\P_q$ be a set of representatives of 
the right cosets of $PGL_2(\F_q)$ in $PGL_2(\F_{q^2})$. 
Note that the cardinality of $\P_q$ is $q^3+q$.
It was shown in \cite{BGJT13v1, Joux13b} that the matrices in
the same coset produce the same relation (\ref{mrelation}).


Suppose that  for some $1 \leqslant g \leqslant q^2 $, 
$ \zeta+\alpha_g $ is a known multiplicative
generator of $ \F_{q^2}[\zeta] = \F_{q^2}[x]/(f(x)) $.  
Since  (\ref{mrelation}) also holds modulo $f(x)$, 
taking the discrete logarithm
with respect to the base $ \zeta + \alpha_g $,
we obtain 
\begin{equation}\label{arelation}
e_0  \log_{\zeta+\alpha_g} \lambda + \sum_{1\leqslant i\leqslant q^2, i\not= g} 
(e_i-e'_i) \log_{\zeta+\alpha_g} (\zeta+\alpha_i) \equiv e'_g - e_g  
\pmod{q^{2k}-1}.  
\end{equation} 
The above equation gives us a linear relation among the discrete 
logarithm of linear factors.
One hopes to collect enough relations such that the linear system formed 
by those relations is non-singular over $ \Z/(q^{2k}-1)\Z $.
It allows us to solve $\log_{\zeta+\alpha_g} (\zeta+\alpha_i)  $  
for all the $ \zeta +\alpha_i $ 
in the factor base. 


However, 
%we can show
%\begin{theorem}
%there exists polynomials $ h_0 $ and $ h_1 $, such that 
if for some $ 1\leqslant z \leqslant q^2  $, 
\[ (x + \alpha_z) | x^q h_1(x) - h_0 (x),\]
the algorithm will unlikely compute
$ \log_{\zeta+\alpha_g} (\zeta+\alpha_z) $. 
%In the other words, 
%the relation will not have full rank $ q^2 $ .
%\end{theorem}
%\begin{proof}
It is because that $ x+\alpha_z $ is zero or nilpotent 
(without loss of generality let $ f_1 = x+\alpha_z $) in 
the $\F_{q^2}[x]/( (x+\alpha_z)^{a_1}) $ component of the ring
\[ \F_{q^2}[x]/(x^q h_1 (x) - h_0 (x)) 
=\F_{q^2}[x]/(f(x)) \oplus  \bigoplus_{i=1}^l \F_{q^2}[x]/(f_i(x)^{a_i}).\] 
Hence in   (\ref{mrelation}), if $ e_z > 0 $,
$ e'_z $ is positive as well.    Most likely we will have $ e_z = e'_z $,
so the coefficient for
$ \log_{\zeta +\alpha_g} (\zeta + \alpha_z) $ 
in (\ref{arelation}) will always be $ 0 $.
%undefined at that  component. 

\begin{remark}
If $ e'_z > e_z \geqslant 1 $, it is possible to
compute $ \log_{\zeta +\alpha_g} (\zeta + \alpha_z) $.
However, this requires the low degree polynomial in the right
hand side of (\ref{mrelation}) to have the factor $ (x+\alpha_z)^2 $, which
is unlikely.
Our numerical data confirm that it
never happens when $ q $ is sufficiently large.
\end{remark}


To compute the discrete logarithm of $\zeta + \alpha_z$,
we have to use additional relations which hold for the 
field $\F_{q^2}[\zeta]$ but may not hold for the bigger ring 
$ \F_{q^2}[x]/(x^q h_1 (x) - h_0 (x)) $.
The equation \[ (\zeta+\alpha_z )^{q^{2k}-1} = 1  \] is
such an example. 
But this does not help in computing its discrete logarithm 
in the field $\F_{q^2}[\zeta]$, if it is the only relation
involving $ \zeta + \alpha_z $.

In general, it is hard to find useful additional relations 
for $ x+\alpha_z $, since for the algorithm to
 work, it is essential that  we replace $ x^q $ by $h_0(x)/h_1(x)$ 
(not replace $f(x)$ by zero) in the relation generating stage. 
Hence it is not clear that  the discrete logarithm of $\zeta + \alpha_z$ can be
computed in polynomial time, invalidating a conjecture in
\cite{BGJT13v1}. 
%We will show in a later section  that
%it may be computed in quasi-polynomial time,
%under some heuristics.
\begin{remark}
An exception is in the case of a Kummer extension,
where the zero divisor $ x $ in the ring has
a small order in the field.
\end{remark}

\subsection{The tale of two lattices}

To fix the above problem in a non-Kummer case, 
we can either change our factor base
to not include the linear factors of $x^q h_1 (x) - h_0 (x)$,
or we can search for $h_0$ and $h_1$ such that
$x^q h_1 (x) - h_0 (x)$  does not have linear factors.
In the following discussion, we will assume that 
$ x^q h_1 (x) - h_0 (x)  $ has no linear factor for simplicity. That is, 
$$k_i:= \deg(f_i) \geqslant 2 \ (1\leqslant i\leqslant l).$$
In this case, the linear factors $x +\alpha_i$'s are invertible in the ring 
$\F_{q^2} [x]/ (x^q h_1(x) - h_0 (x))$ and equation (\ref{mrelation}) reduces to 
\begin{equation}\label{mmrelation}
\lambda^{e_0} \prod_{i=1}^{q^2} (x + \alpha_i)^{e_i-e'_i} = 1 \pmod { x^q h_1(x) - h_0(x)}. 
\end{equation}
%Let $g(x) =\gcd(x^qh_1(x)-h_0(x), x^{q^{2k}-1} -1)$. Its irreducible factorization over $\F_{q^2}$ is given by 
%$$g(x) = f(x) \prod_{1\leqslant i\leqslant l, k_i|k} f_i(x).$$
We define two fundamental lattices in $\Z^{q^2+1}$:
\begin{eqnarray*} 
\L_1 &=& \{ (e_0, e_1, \dotsc, e_{q^2}) | \lambda^{e_0} \prod_{i=1}^{q^2} (x + \alpha_i)^{e_i} =1
\pmod{ f (x)} \}, \\
\L_2 &=& \{ (e_0, e_1, \dotsc, e_{q^2}) | \lambda^{e_0} \prod_{i=1}^{q^2} 
(x + \alpha_1)^{e_i} =1
\pmod{ x^q h_1 (x) - h_0 (x) } \}.  
\end{eqnarray*}
It is easy to see that 
$\L_2 \subseteq \L_1$.  
Consider the group homomorphism 
\[ \psi_1: \Z^{q^2 + 1} \rightarrow  (\F_{q^2} [x]/ (f(x)))^*
\]
given by 
\[
(e_0, e_1, \dotsc, e_{q^2}) \mapsto \lambda^{e_0} \prod_{i=1}^{q^2} 
(x + \alpha_i)^{e_i}.
\]
The group homomorphism $\psi_2$ is defined in the same way, except that  
modulo $f(x)$ is replaced by modulo  $(x^q h_1(x) - h_0(x))$. 

Cheng and Wan proved Theorem \ref{ThSurjective} and Theorem \ref{ThIsomorphism} in \cite{CLZ13}.
We include their proofs for the sake of completeness.

\begin{theorem}\label{ThSurjective} 
If $\deg(h_1)\leqslant 2$, then 
the maps $ \psi_1 $ and $\psi_2$ are  surjective.

\end{theorem}

\begin{proof} It is enough to prove that $\psi_2$ is surjective. If not, the image $H$ of $\psi_2$ 
would be a proper subgroup of $(\F_{q^2} [x]/ (x^q h_1(x) - h_0 (x)))^*$. We can then choose 
a non-trivial character $\chi$ of $(\F_{q^2} [x]/ (x^q h_1(x) - h_0 (x)))^*$ which is trivial on the 
subgroup $H$. Since $\chi$ is trivial on $H$ which contains $\F_{q^2}^*$, we can use the Weil bound as given in  Theorem 2.1 in \cite{Wan97}
and deduce that 
$$1+q^2 =|1 +\sum_{\alpha \in \F_{q^2}}\chi(x +\alpha)| \leqslant (q+\deg(h_1)-2)\sqrt{q^2} \leqslant q^2.$$
This is a contradiction. It follows that $\psi_2$ must be surjective. 
\end{proof}


% The ideas of using the $\F_{q^2}$ relation
% of $  (x+\alpha_1)^{\frac{q^{2k}-1}{q^2-1} } $ and $
% (x+\alpha_1)^{\frac{q^{2k}-1}{q^2-1} } $ works?
Note that in the application of computing discrete logarithms,
it is important that $ \psi_1 $ is surjective. 
% if $\deg(h_1) \geqslant 3$, the Weil's bound 
% does not imply that $\psi_2$ is surjective. This may be another reason that 
% we assume that $\deg(h_1)\leqslant 2$. 
As a corollary, we obtain 

\begin{corollary}  If $\deg(h_1)\leqslant 2$, then 
\begin{itemize}
\item the group $\Z^{q^2 +1}/ \L_1   $ is isomorphic to  the cyclic group $\Z/(q^{2k}-1)\Z$,
\item the group $\Z^{q^2 +1}/ \L_2   $ is  isomorphic to
\[ \Z/(q^{2k}-1)\Z \oplus \bigoplus_{i=1}^l \Z/(q^{2k_i} - 1)\Z  \bigoplus (\text{a  finite  $p$-group}). \]
\end{itemize}
\end{corollary}

In particular, the group $\Z^{q^2 +1}/ \L_2   $ is not cyclic when 
$ l \geqslant 1  $. The relation generation stage only gives lattice vectors in $\L_2$, which 
is far from the $\L_1$ if $l\geqslant 1$. Thus, we need to add more relations to $\L_2$ in order 
to get close to $\L_1$. 

Since $\lambda^{q^2-1} = 1$, the vector $(q^2-1, 0,\dotsc, 0)$ is automatically in $\L_2$.  
Let $\L_2^*$ be the lattice in $\Z^{q^2 + 1}$ 
generated by $\L_2$ and the following $q^2$ vectors 
$$(0, q^{2k}-1, 0, \dotsc, 0), \dotsc, (0,0, \dotsc, 0, q^{2k}-1),$$
corresponding to the relations $(x+\alpha_i)^{q^{2k}-1} =1 $ 
modulo $f(x)$ for $\alpha_i \in \F_{q^2}$. 
It is clear that 
$$\L_2^* = \L_2 + (q^{2k}-1)\Z^{q^2+1}.$$
The next result gives the group structure for the quotient $\Z^{q^2 +1}/ \L_2^* $.  

\begin{theorem}\label{ThIsomorphism}
%Assume that $ k $ is prime.  
For $deg(h_1) \leqslant 2$, there is a group isomorphism 
$$\Z^{q^2 + 1}/\L_2^*\cong \Z/(q^{2k}-1)\Z \oplus \bigoplus_{1\leqslant i\leqslant l} 
\Z/(q^{2\gcd(k,k_i)} - 1)\Z.   $$
\end{theorem}

\begin{proof} Recall that 
\[ \Z^{q^2+1}/\L_2 \cong A \stackrel{\mathrm{def}}{=} \Z/(q^{2k}-1)\Z 
\oplus \bigoplus_{i=1}^l \Z/(q^{2k_i} - 1)\Z  \bigoplus (\text{a  
finite  $p$-group}). \]
It is clear that 
\[ A/(q^{2k}-1)A \cong \Z/(q^{2k}-1)\Z \oplus 
\bigoplus_{1\leqslant i\leqslant l}\Z/(q^{2\gcd(k_i,k)} - 1)\Z . \]
The kernel of the surjective composed homomorphism 
$$\Z^{q^2+1}\longrightarrow \Z^{q^2+1}/\L_2 \cong A \longrightarrow A/(q^{2k}-1)A$$
is precisely $\L_2 + (q^{2k}-1)\Z^{q^2+1}=\L_2^*$. The desired isomorphism follows. 

\end{proof}




If $\gcd(k_i,k)>1$ for some $i$, then $\L_2^*$ is still far from $\L_1$.  
We would like $\L_2^*$ to be as close to $\L_1$ as possible in a smooth sense.  
For us, the more interesting case is the following 
\begin{corollary} 
Let $deg(h_1) \leqslant 2$. If $\gcd(k_i, k)=1$ for all $1\leqslant i\leqslant l$, 
we have an isomorphism 
$$\Z^{q^2+1}/\L_2^* \cong \Z/(q^{2k}-1)\Z \oplus 
(\Z/(q^{2} - 1)\Z)^l . $$
\end{corollary}

This corollary shows that under the same assumption, the lattice $\L_2^*$ is a smooth approximation of $\L_1$ 
in the sense that the quotient $\L_1/\L_2^*$ is a direct sum of small order cyclic groups. 

The  algorithm to compute the discrete logarithms 
in the factor base essentially samples vectors from the lattice $\L_2$.
Let $\r_1, \r_2, \dotsc $ be the vectors in $ \L_2$ 
obtained by the relation-finding algorithm, i.e., 
from the relations in (\ref{mmrelation}). 
Let $ \hat{\L_2} $ be the lattice generated by those vectors.
Let $ \hat{\L_1} $ be the lattice generated by $ \hat{\L_2}  $
and the following $q^2+1$ vectors: 
$$(q^2-1, 0, \dotsc, 0), (0, q^{2k}-1, 0, \dotsc, 0), \dotsc, (0,0, \dotsc, 0, q^{2k}-1). $$
Computing 
the Hermite (or Smith) Normal Form of $ \hat{\L_1} $ is equivalent to
solving the linear system $ \hat{\L_2} $ in the ring $ \Z/(q^{2k}-1)\Z $. 
It is in general difficult to find bases for 
the two lattices $\L_1$ and $\L_2$ directly.  
One can think that $ \hat{\L_1} $ and $ \hat{\L_2} $ 
are the approximations of $ \L_1 $ and $ \L_2 $, respectively. These approximations can be computed  
by the polynomial time algorithm.
% Solving 
% the linear system  over  the ring $ \Z/(q^{2k}-1)\Z $,
% is equivalent to computing the Smith Normal Form of 
% $ \hat{\L_2}^* $.
 Obviously,
\[ \hat{\L_2} 
\begin{array}{c}
\subseteq \L_2 \subseteq\\
\subseteq \hat{\L_1} \subseteq
\end{array}
\L_2^* \subseteq \L_1.  \] 
%$ (q^{2 k} -1) u_i  $
These inclusions induce surjective group homomorphisms 
\[\Z^{q^2 +1}/ \hat{\L_2}
\begin{array}{c}
\rightarrow \Z^{q^2 +1}/ \L_2 \rightarrow \\
\rightarrow \Z^{q^2 +1}/ \hat{\L_1} \rightarrow 
\end{array}
\Z^{q^2+1}/\L_2^* \rightarrow \Z^{q^2 +1}/ \L_1.
\]
If $\Z^{q^2 + 1} /\hat{\L_2}$ is cyclic, then its quotient $\Z^{q^2 + 1} /\L_2$ 
will be cyclic.  
This is false if $l \geqslant 1$ as we have seen before.  
Similarly,  $ \Z^{q^2 +1}/ \hat{\L_1} $ is not cyclic as its quotient  $\Z^{q^2 + 1} /\L_2^*$ 
is not cyclic if $l \geqslant 1$. Hence the conjecture in \cite{HuangNa13} 
also needs modification. It seems reasonable to hope that $\hat{\L_1}$ is a good approximation 
to $\L_2^*$ in the sense that the quotient $\L_2^*/\hat{\L_1}$ is a direct sum of small order 
cyclic groups. In the interesting case where $ \gcd(k,k_i) =1 $ 
for all $ 1\leqslant i\leqslant l $, our numerical data suggest the following heuristic is highly plausible. 

\begin{heuristic}\label{HSmith}
Assume that $ x^q h_1(x) - h_0(x) $ does not
have linear factors, and $ \gcd(k,k_i) =1 $ 
for all $ 1\leqslant i\leqslant l $. 
Then in the SNF of $ \hat{\L_1} $, the diagonal
elements are
\[ 1, 1, \dotsc, 1, s_1, \dotsc, s_t, q^{2k}-1,  \] 
where for $ 1\leqslant i\leqslant t $,  $ s_i > 1 $ and $s_i | q^2 -1$.
\end{heuristic}

\begin{example}
Let $q=16,k=11$ and $\F_{q^2}=\langle \lambda \rangle$.

In the first step, we choose the appropriate $h_0(x)$ and $h_1(x)$ as follows:
\[
h_0(x)=\lambda*x^2 + \lambda^4*x + 1,
\]
\[
h_1(x)=x + \lambda.
\]
Thus we have the polynomial
\[
h_1(x) * x^{16} - h_0(x) = x^{17} + \lambda*x^{16} + \lambda*x^2 + \lambda^4*x + 1.
\]
The two irreducible factors of $h_1(x) * x^{16} - h_0(x)$ over $\F_{q^2}$ are of degree $11$ and $6$, respectively.

After collecting the relations and generating the SNF, the SNF is given by $[A|B]$, where $B$ is a zero matrix 
and 
\[
A=
\begin{bmatrix}
1 \\
  & \ddots \\
  &     &  1 \\
  &     &   & 15 \\
  &     &   &    & 15 \\
  &     &   &    &     & 255 \\
  &     &   &    &     &     & 309485009821345068724781055
\end{bmatrix}_{257\times 257}.
\]
Note that $16^{2\times 11}-1=309485009821345068724781055$.
\end{example}

\begin{example}
Let $q=16,k=13$ and $\F_{q^2}=\langle \lambda \rangle$. 

In the first step, we choose the appropriate $h_0(x)$ and $h_(x)$ as follows:
\[
h_0(x)=\lambda*x^2 + \lambda^7*x + 1,
\]
\[
h_1(x)=x + \lambda.
\]
Thus we have the polynomial
\[
h_1(x) * x^{16} - h_0(x) = x^{17} + \lambda*x^{16} + \lambda*x^2 + \lambda^7*x + 1.
\]
The two irreducible factors of $h_1(x) * x^{16} - h_0(x)$ over $\F_{q^2}$ are of degree $13$ and $4$, respectively.

After collecting the relations and generating the SNF, the SNF is given by $[A|B]$, where $B$ is a zero matrix 
and
\[
A=
\begin{bmatrix}
1 \\
  & \ddots \\
  &     &  1 \\
  &     &   & 15 \\
  &     &   &    & 15 \\
  &     &   &    &     & 15 \\
  &     &   &    &     &    & 15 \\
  &     &   &    &     &    &    &  255 \\
  &     &   &    &     &    &    &      &  20282409603651670423947251286015
\end{bmatrix}_{257\times 257}.
\]
Note that $16^{2\times 13}-1=20282409603651670423947251286015$.
\end{example}

Assuming the heuristics, 
$ \Z^{q^2 +1}/ \hat{\L_1} $  is not much bigger than 
$ \Z^{q^2 +1}/ \L_1 $, namely,
%  the discrete logarithms for the 
%factor base, as well as a multiplicative generator, 
%can still be found with some extra effort.
\[ \Z^{q^2+1}/\hat{\L_1} \cong \Z/s_1\Z \oplus \Z/s_2\Z \oplus \cdots 
\oplus \Z/s_t \Z \oplus \Z/(q^{2k}-1)\Z. \] 
We can  find a generator for each component,
as a product of linear polynomials from the computation 
of the SNF. 
Suppose that for $ 1\leqslant i\leqslant t $,
the generator for the $ i $-th  component is
\[ \lambda^{e_{i0}} \prod_{ 1\leqslant j \leqslant q^2} (x+\alpha_j)^{e_{ij}}. \] 
Since $ s_i | q^2 -1 $, the above generator belongs to $ \F_{q^2} $
in $ \F_{q^2}[x]/(f(x))$. Assuming that it is $ \lambda^{e'_{i0}}$, 
we have 
%hence there exists a number $ 0\leqslant e_{i0} \leqslant q^2-1 $   such that
\[ \lambda^{e_{i0} - e'_{i0}} \prod_{ 1\leqslant j \leqslant q^2} (x+\alpha_j)^{e_{ij}} 
 = 1 \pmod{ f(x) }.  \]  
There are $ t $ such relations. Adding them  to $ \hat{\L_1} $,
we will  finally arrive at the lattice $ \L_1 $.
It allows us to find a  generator for
$ (\F_{q^2}[x]/(f(x)))^* $, and to solve the discrete logarithms 
for the factor base, with respect to this generator. 



\subsection{Huang-Narayanan's method to determine primitive elements}
%In the case of $G=\F_q^{\times}$ even high order is hard \cite{Cheng ect.}

In the case of $G=\F_{p^k}^{\times}$, where $p$ is a small prime, Huang and Narayanan \cite{HuangNa13} designed a polynomial-time 
algorithm to determine the primitive element of $G$ based on a result of F.R.K Chung \cite{Chung89} and 
Joux's relation generation method \cite{Joux13b}.

Firstly,  Huang and Narayanan embed the field $\F_{p^k}$ to $\F_{q^{2k}}$, where $q=p^m$ and $m = \lceil \log_p(k) \rceil$.
The field $\F_{q^{2k}}$ is represented in the same way as in \cite{Joux13b}. That is, one searches for appropriate 
polynomials $h_0(x),h_1(x)\in\F_{q^2}[x]$ of low degree such that the factorization of $h_1(x)x^q-h_0(x)$ over
$\F_{q^2}[x]$ has an irreducible factor $I(x)$ of degree $k$. Let $\zeta$ be a root of $I(x)$. The field
$\F_{q^{2k}}$ is represented by $\F_{q^2}[\zeta]$.
They remark that an isomorphism between two explicit representations of a field of size $p^n$ can be computed 
deterministically in time polynomial in $n$ and $\log(p)$, which is due to Lenstra \cite{Lenstra91}.

From a result of F.R.K Chung \cite{Chung89},
let $l$ be a prime power and $t$ be a positive integer satisfying $(t-1)^2 < l$ and the field $\F_{l^t}=\F_{l}[\alpha]$.
Then the set $\F_l+\alpha$ generates $\F_{l^t}^{\times}$. In the current case, Chung's result implies that
$\F_{q^{2k}}^*$ is generated by $S=\F_{q^2}+\zeta$ since $k<q$ by construction.
In practice, $S$ is extended to the bigger set $F=S\cup \{h_1(x)\} \cup \{\lambda\}$, where $\F_{q^2}=\langle \lambda \rangle$.

Similarly as in \cite{Enge01}, Huang and Narayanan also make use of the fact that 
\[
\F_{q^{2k}}^{\times} \cong \Z^{|F|}/\Gamma,
\] 
where $\Gamma$ is the relation lattice satisfied by elements of $F$.
Thus one can determine the generator of $\F_{q^{2k}}^{\times}$ by computing the SNF of a relation matrix
$M$, which approaches $\Gamma$ well.

To collect the needed relations, Huang and Narayanan propose to construct the relation matrix $M$ via 
Joux's relation generation algorithm \cite{Joux13b}.

\subsection{Finding the discrete logarithms of linear polynomials by SNF}
Following the same notation as in the last section, suppose $M$ is a good approximation of $\Gamma$ such that the 
SNF $D =U*M*V$ determines the structure of $\F_{q^{2k}}^{\times} $ correctly. 
Suppose the relation is represented as columns of $M$ and $M$ is an $m \times n$ matrix. 
Then $U$ is an $m \times m$ matrix and $V$ is an $n \times n$ matrix.
$D$ has the form $[D_1 | D_2]$, where 
\[
D_1=
\begin{bmatrix}
1 \\
& 1 \\
& & \ddots \\
& &  &1 \\
& & &  & q^{2k}-1
\end{bmatrix}_{m \times m}
\]
and $D_2$ is a zero matrix.

We observe that we can not only find the primitive element $\gamma$
from the information of $U^{-1}$, but also the discrete logarithms of elements in $F$ based on the found primitive element.
Suppose the corresponding elements of $i$-th row of $M$ and $D$ are $a_i$ and $b_i$, respectively.
Since 
\[
D = U*M*V,
\] 
\[
M = U^{-1}*D*V^{-1},
\]
each $a_i$ can be written as a product of $b_j$ and vice versa.
Notice that $b_i=1$ for all $1\leqslant i \leqslant m-1$, thus we have the expression
\[
a_i = \gamma^{e_i},
\]
which implies that $\log_{\gamma}(a_i)=e_i$, where $e_i$ is the $i$-th element of the last row of $U$.

\subsection{Examples}
\begin{example}
In this example, we want to find the primitive element of $\F_{16^{2\times 11}}$ and the discrete logarithms of linear polynomials.

In the first step, we define $\F_{16^2}^*=\langle \lambda \rangle$ and search for 
$h_0(x),h_1(x)\in \F_{16^2}[x]$ such that $h_1(x)*x^{16}-h_0(x)$ satisfies the conditions in Heuristic \ref{HSmith}.
Choose
\[
h_0(x) = \lambda*x^2 + \lambda^4*x + 1, h_1(x) = x + \lambda.
\]
We have
\[
h_1(x) * x^{16} - h_0(x) = x^{17} + \lambda*x^{16} + \lambda*x^2 + \lambda^4*x + 1.
\]
There are two irreducible factors of $h_1(x)*x^{16}-h_1(x)$ over $\F_{16^2}$:
\begin{equation*}
\begin{split}
f_1(x) & = x^6 + (\lambda^6 + \lambda^4 + \lambda^2 + 1)*x^5 + (\lambda^7 + \lambda^6 + \lambda^4 + 1)*x^4 \\
         & \quad  + (\lambda^7 + \lambda^5 + \lambda^4 + \lambda^2 + \lambda)*x^3 + \lambda^4*x^2  \\
         & \quad  + (\lambda^7 + \lambda^4 + \lambda^3 + \lambda^2 + \lambda + 1)*x + \lambda^7 + \lambda^4 + \lambda^3 + 1,
\end{split} 
\end{equation*}
\begin{equation*}
\begin{split}
f_2(x) & =  x^{11} + (\lambda^6 + \lambda^4 + \lambda^2 + \lambda + 1)*x^{10} + (\lambda^7 + \lambda^5 + \lambda^4 + \lambda^3 + g)*x^9 \\
         & \quad + (\lambda^7 + \lambda^6 + \lambda^5 + \lambda^4 + \lambda)*x^8 + (\lambda^7 + \lambda^6 + \lambda^5 + \lambda^2 + \lambda + 1)*x^7 \\
         & \quad + (\lambda^7 + \lambda^5 + \lambda^4 + \lambda^2 + 1)*x^6 + (\lambda^5 + \lambda^2 + 1)*x^5 \\
         & \quad + (\lambda^6 + \lambda^5 + \lambda^3)*x^4 + (\lambda^7 + \lambda^6 + \lambda^4 + \lambda^2 + 1)*x^3 \\
         & \quad + (\lambda^7 + \lambda^6 + \lambda^4 + 1)*x^2 + (\lambda^7 + \lambda^6 + \lambda^4)*x \\
         & \quad + \lambda^7 + \lambda^6 + \lambda^4 + \lambda^3 + \lambda^2.
\end{split}
\end{equation*}
We construct $\F_{16^{2\times 11}}$ as $\F_{16^2}[\zeta]$, where $\zeta$ is a root of irreducible polynomial $f_2(x)\in\F_{16^2}[x]$.

In the second stage, we choose the factor base $F = \{\lambda\}\cup S$, where $S=\F_{16^2}+\zeta$.
And we collect the relations among the elements in the factor base to construct the relation matrix $M$. 
There are two types of relations to consider.
\begin{itemize}
\item The first type is according to Joux's relation generation method. We collect all the M$\ddot{o}$bius twist relations from the systematic 
equation, that is, we run over all right cosets of $PGL_2(\F_{16})$ in $PGL_2(\F_{16^2})$ from our classification.
\item The second type makes use of the following observation: $\lambda^{255} = 1$ and for each $\alpha_i\in \F_{16^2}$, there exists an $e_i$ such that
\[
\lambda^{e_i} = (\zeta + \alpha_i)^{\frac{16^{2\times 11}-1}{16^2-1}}.
\]
\end{itemize}
Finally, we compute the SNF of $M$. In other words, we compute 
\[
D = U*M*V.
\] 
We have $D = [D_1 | D_2]$, where $D_2$ is a zero matrix and  
\[
D_1=
\begin{bmatrix}
1 \\
& 1 \\
& & \ddots \\
& &  &1 \\
& & &  & 309485009821345068724781055
\end{bmatrix}_{257 \times 257}.
\]
Since $309485009821345068724781055=16^{22}-1$,
we claim that we have found the primitive element of $\F_{16^{22}}^*$,
which can be recovered from the last column of $U^{-1}$ as follows
\begin{center}
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
\end{center}
The corresponding element is 
\[
\gamma = \zeta+\lambda^{166}.
\]
Furthermore, the discrete logarithms of elements in the factor base can be retrieved from the last row of $U$.
The result is in Appendix A.

For instance, we can verify that 
\begin{itemize}
\item $\log_{\gamma}(\lambda) = 209964339996441948585831853, \gamma^{\log(\lambda)} = \lambda$,
\item $\log_{\gamma}(\zeta)= 60710879082065564476318181,  \gamma^{\log_{\gamma}(\zeta)} = \zeta$,
\item $\log_{\gamma}(\zeta+\lambda^{55}) = 115063015500116530915979577, \gamma^{\log_{\gamma}(\zeta+\lambda^{55})} = \zeta + \lambda^{55}$,
\item $\log_{\gamma}(\zeta+\lambda^{197}) = 187986527916727874578311046, \gamma^{\log_{\gamma}(\zeta+\lambda^{197})} = \zeta + \lambda^{197}$,
\item $\log_{\gamma}(\zeta+\lambda^{255}) = 267444368200903281347884604, \gamma^{\log_{\gamma}(\zeta+\lambda^{255})} = \zeta + \lambda^{255}$.
\end{itemize}
\end{example}


\begin{example}
In this example, we want to find the primitive element of $\F_{16^{2\times 11}}$ and the discrete logarithms of linear polynomials following another approach.

In the first step, we define $\F_{16^2}^*=\langle \lambda \rangle$ and search for $h_0(x),h_1(x)\in \F_{16^2}[x]$ such that $h_1(x)*x^{16}-h_0(x)$ satisfies the conditions in Heuristic \ref{HSmith}.
Choose
\[
h_0(x) = \lambda*x^2 + \lambda^4*x + 1, h_1(x) = x + \lambda.
\]
We have
\[
h_1(x) * x^{16} - h_0(x) = x^{17} + \lambda*x^{16} + \lambda*x^2 + \lambda^4*x + 1.
\]
There are two irreducible factors of $h_1(x)*x^{16}-h_1(x)$ over $\F_{16^2}$:
\begin{equation*}
\begin{split}
f_1(x) & =   x^6 + (\lambda^6 + \lambda^4 + \lambda^2 + 1)*x^5 + (\lambda^7 + \lambda^6 + \lambda^4 + 1)*x^4 \\
         & \quad + (\lambda^7 + \lambda^5 + \lambda^4 + \lambda^2 + \lambda)*x^3 + \lambda^4*x^2  \\
         & \quad + (\lambda^7 + \lambda^4 + \lambda^3 + \lambda^2 + \lambda + 1)*x + \lambda^7 + \lambda^4 + \lambda^3 + 1,
\end{split} 
\end{equation*}
\begin{equation*}
\begin{split}
f_2(x) & =  x^{11} + (\lambda^6 + \lambda^4 + \lambda^2 + \lambda + 1)*x^{10} + (\lambda^7 + \lambda^5 + \lambda^4 + \lambda^3 + g)*x^9 \\
         & \quad + (\lambda^7 + \lambda^6 + \lambda^5 + \lambda^4 + \lambda)*x^8 + (\lambda^7 + \lambda^6 + \lambda^5 + \lambda^2 + \lambda + 1)*x^7 \\
         & \quad + (\lambda^7 + \lambda^5 + \lambda^4 + \lambda^2 + 1)*x^6 + (\lambda^5 + \lambda^2 + 1)*x^5 \\
         & \quad + (\lambda^6 + \lambda^5 + \lambda^3)*x^4 + (\lambda^7 + \lambda^6 + \lambda^4 + \lambda^2 + 1)*x^3 \\
         & \quad + (\lambda^7 + \lambda^6 + \lambda^4 + 1)*x^2 + (\lambda^7 + \lambda^6 + \lambda^4)*x \\
         & \quad + \lambda^7 + \lambda^6 + \lambda^4 + \lambda^3 + \lambda^2.
\end{split}
\end{equation*}
We construct $\F_{16^{2\times 11}}$ as $\F_{16^2}[\zeta]$, where $\zeta$ is a root of irreducible polynomial $f_2(x)\in\F_{16^2}[x]$.

In the second stage, we choose the factor base $F = \{\lambda\}\cup S$, where $S=\F_{16^2}+\zeta$.
And we collect the relations among the elements in the factor base to construct the relation matrix $M$. 
There are there types of relations to consider.
\begin{enumerate}
\item  Generate $150$ relations by Joux's method.
\item  Generate Frobenius relations. That is, for each $\alpha\in \F_{16^2}$,
we have
\[
(\zeta + \alpha)^{16} = \zeta^{16} + \alpha^q = \frac{h_0(\zeta)}{h_1(\zeta)} + \alpha^{16}, 
\] 
which implies
\[
h_1(\zeta)*(\zeta+\alpha)^{16} = h_0(\zeta)+ \alpha^{16}*h_1(\zeta).
\]
If the polynomial in the right-hand side factorizes into linear polynomial products, then we get a relation.
In practice, we get $128$ Frobenius relations.
\item The last type of relation makes use of the following observation: $\lambda^{255} = 1$ and for each $\alpha_i\in \F_{16^2}$, there exists an $e_i$ such that
\[
\lambda^{e_i} = (\zeta + \alpha_i)^{\frac{16^{2\times 11}-1}{16^2-1}}.
\]
\end{enumerate}

We compute the SNF of $M$ to get 
\[
D = U*M*V.
\] 
Since the diagonal element of $D$ are 
\[
1,1,\ldots,1,309485009821345068724781055(=16^{22}-1),
\]
we claim that we have found the primitive element,
which can be recovered from the message of the last column of $U^{-1}$ as follows:

\begin{center}
[-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -21441445124877501493350844, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)].
\end{center}

The corresponding element is 
\[
\gamma = \lambda^{-1}*(\zeta+\lambda^{177})^{-21441445124877501493350844}.
\]
Furthermore, the discrete logarithms of elements in the factor base can be read from the last row of $U$.
The result is in Appendix B.


We verify the following instances:
\begin{itemize}
\item $\log_{\gamma}(\lambda) = 245160674446712564244728522, \gamma^{\log(\lambda)} = \lambda$,
\item $\log_{\gamma}(\zeta)= 255670351189335847080296839,  \gamma^{\log_{\gamma}(\zeta)} = \zeta$,
\item $\log_{\gamma}(\zeta+\lambda^{100}) = 68291259138980224088221968, \gamma^{\log_{\gamma}(\zeta+\lambda^{100})} = \zeta + \lambda^{100}$,
\item $\log_{\gamma}(\zeta+\lambda^{177}) = 3, \gamma^{\log_{\gamma}(\zeta+\lambda^{177})} = \zeta + \lambda^{177}$,
\item $\log_{\gamma}(\zeta+\lambda^{186}) = 49529503067517771000507583, \gamma^{\log_{\gamma}(\zeta+\lambda^{186})} = \zeta + \lambda^{186}$.
\end{itemize}
\end{example}

\begin{example}
In this example, we want to find the primitive element and discrete logarithms of linear polynomials in $\F_{16^{2\times 12}}$.
 
In the first step, we define $\F_{16^2}^*=\langle \lambda \rangle$ and search for $h_0(x),h_1(x)\in \F_{16^2}[x]$ such that $h_1(x)*x^{16}-h_0(x)$ satisfies the conditions in Heuristic \ref{HSmith}.
Choose
\[
h_0(x) = \lambda*x^2 + (\lambda^6 + \lambda^5 + \lambda^4 + \lambda^2)*x + 1, h_1(x) = x + \lambda.
\]
We have
\[
h_1(x) * x^{16} - h_0(x) = x^{17} + \lambda*x^{16} + \lambda*x^2 + (\lambda^6 + \lambda^5 + \lambda^4 + \lambda^2)*x + 1.
\]
There are two irreducible factors of $h_1(x)*x^{16}-h_1(x)$ over $\F_{16^2}$:
\begin{equation*}
\begin{split}
f_1(x) & =  x^5 + (\lambda^7 + \lambda^5 + \lambda^4 + \lambda)*x^4 + (\lambda^7 + \lambda^5 + \lambda^3 + 1)*x^3 \\
          & \quad + (\lambda^7 + \lambda^5 + \lambda^4 + \lambda^3)*x + \lambda^7 + \lambda^6 + \lambda^5 + \lambda^4 + \lambda^3 + \lambda, 
\end{split}
\end{equation*}
\begin{equation*}
\begin{split}
f_2(x) & =  x^{12} + (\lambda^7 + \lambda^5 + \lambda^4)*x^{11} + (\lambda^7 + \lambda^5 + \lambda^3 + \lambda^2 + \lambda)*x^{10} \\
         & \quad + (\lambda^6 + \lambda^5 + \lambda^4 + \lambda^2 + \lambda)*x^9 + (\lambda^7 + \lambda^6 + \lambda^4 + \lambda^3 + \lambda)*x^8 \\
         & \quad + (\lambda^7 + \lambda^5 + \lambda^4 + \lambda^2)*x^7 + (\lambda^7 + \lambda^6 + \lambda^4 + 1)*x^6 \\
         & \quad + (\lambda^7 + \lambda^4 + \lambda + 1)*x^5 +(\lambda^6 + \lambda^4 + \lambda^2)*x^4 \\
         & \quad + (\lambda^7 + \lambda^2)*x^3 + (\lambda^7 + \lambda^5 + \lambda^4 + \lambda^3 + \lambda^2 + \lambda)*x^2 \\
         & \quad + (\lambda^6 + \lambda^3 + \lambda^2)*x + \lambda^7 + \lambda^6 + \lambda^5 + \lambda^3.
\end{split}
\end{equation*}
We construct $\F_{16^{2\times 12}}$ as $\F_{16^2}[\zeta]$, where $\zeta$ is a root of irreducible polynomial $f_2(x)\in\F_{16^2}[x]$.

In the second stage, we choose the factor base $F = \{\lambda\}\cup S$, where $S=\F_{16^2}+\zeta$.
And we collect the relations among the elements in the factor base to construct the relation matrix $M$. There are two types of relations to consider.
\begin{itemize}
\item The first type is according to Joux's relation generation method. We collect all the M$\ddot{o}$bius twist relations from the systematic 
equation, that is, we run over all cosets of $PGL_2(\F_{16})$ in $PGL_2(\F_{16^2})$ from our classification.

\item The second type makes use of the following observation: $\lambda^{255} = 1$ and for each $\alpha_i\in \F_{16^2}$, there exists an $e_i$ such that
\[
\lambda^{e_i} = (\zeta + \alpha_i)^{\frac{16^{24}-1}{16^2-1}}.
\]
\end{itemize}
Next, we compute the SNF of $M$. Equivalently, we compute 
\[
D = U*M*V.
\] 
Since the diagonal element of $D$ are 
\[
1,1,\ldots,1,3,3,3,3,79228162514264337593543950335(=16^{24}-1),
\]
the relations are not sufficient to determine the actual structure of $\F_{16^{24}}^{*}$.
However, it is not far away from it since we have only four small none-one components.
Observe that $3|16^2-1$, thus these four elements actually lie in $\F_{16^2}$.
Thus we can add these relations as follows.
\begin{enumerate}
\item The element $\beta_{252}$ corresponding to the 252-th diagonal element can be found from the 252-th column of $U^{-1}$, which is
\begin{center}
[-15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -476053333298771011871190636, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
\end{center}
Thus, 
\[
\beta_{252} = \lambda^{-15}*(z+\lambda^{16})^{-42}*(z+\lambda^{100})^{e}*(z+\lambda^{168})*(z+\lambda^{189})^{-5},
\]
where $e=-476053333298771011871190636$.
Since $\beta_{252} = \lambda^{255}$, we add 
the following column vector to the relation matrix:
\begin{center}
[-15-255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -476053333298771011871190636, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
\end{center}
\item The element $\beta_{253}$ corresponding to the 253-th diagonal element can be found from the 253-th column of $U^{-1}$, which is
\begin{center}
[-3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -23930764333874738583871355, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
\end{center}
Thus,
\[
\beta_{253} = \lambda^{-3}*(z+\lambda^{16})^{-9}*(z+\lambda^{100})^{e}*(z+\lambda^{188})*(z+\lambda^{189})^{-1},
\]
where $e=-23930764333874738583871355$.
Since $\beta_{253} = \lambda^{170}$, we add the following column vector to the relation matrix:
\begin{center}
[-3-170, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -23930764333874738583871355, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
\end{center}
\item The element $\beta_{254}$ corresponding to the 254-th diagonal element can be found from the 254-th column of $U^{-1}$, which is
\begin{center}
[-30, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -71, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -951546016174340776180350742, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
\end{center}
Thus,
\[
\beta_{254} = \lambda^{-30}*(z+\lambda^{16})^{-71}*(z+g^{100})^{-951546016174340776180350742}*(z+\lambda^{189})^{-10}. 
\]
Since $\beta_{254} = \lambda^{170}$, we add the following column vector to the relation matrix:
\begin{center}
[-30-170, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -71, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -951546016174340776180350742, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
\end{center} 
\item The element $\beta_{255}$ corresponding to the 255-th diagonal element can be found from the 255-th column of $U^{-1}$, which is
\begin{center}
[585, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1365, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18624550419619218520589158924, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 195, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
\end{center}
Thus,
\[
\beta_{255} = \lambda^{585}*(z+\lambda^{16})^{1365}*(z+\lambda^{100})^{18624550419619218520589158924}*(z+\lambda^{189})^{195}.
\]
Since $\beta_{255} = \lambda^{170}$, we add the following column vector to the relation matrix:
\begin{center}
[585-170, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1365, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18624550419619218520589158924, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 195, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
\end{center}
\end{enumerate}

Now, we compute the SNF of the new relation matrix $M'$, which consists of $M$ and the four augmented relations, to get
\[
D' = U'*M'*V'.
\]
Since the diagonal elements of $D'$ are 
\[
1,1,\ldots,1,79228162514264337593543950335=16^{24}-1,
\]
we claim that we have found the primitive element,
which can be recovered from the message of the last column of $U'^{-1}$ as follows:
\begin{center}
[22, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 88, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 152674035219163120011070411, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
\end{center}
The corresponding element is 
\[
\gamma = \lambda^{22}*(z+\lambda^{16})^{88}*(z+\lambda^{100})^{152674035219163120011070411}.
\]
Furthermore, the discrete logarithms of elements in the factor base can be read from the last row of $U'$.
The result is in Appendix C.

For instance, we can verify that 
\begin{itemize}
\item $\log_{\gamma}(\lambda) = 78917463837737810779451621118, \gamma^{\log(\lambda)} = \lambda$,
\item $\log_{\gamma}(\zeta)= 62833090349644629822148545739,  \gamma^{\log_{\gamma}(\zeta)} = \zeta$,
\item $\log_{\gamma}(\zeta+\lambda^{73}) = 6599517810135817353279741095, \gamma^{\log_{\gamma}(\zeta+\lambda^{73})} = \zeta + \lambda^{73}$,
\item $\log_{\gamma}(\zeta+\lambda^{172}) = 23893826286552840662073779336, \gamma^{\log_{\gamma}(\zeta+\lambda^{172})} = \zeta + \lambda^{172}$,
\item $\log_{\gamma}(\zeta+\lambda^{251}) = 76944331067097277203580421182, \gamma^{\log_{\gamma}(\zeta+\lambda^{251})} = \zeta + \lambda^{251}$.
\end{itemize}
\end{example}



\section{Traps to the original BGJT-algorithm and a solution}


\subsection{The trap to the QPA-descent}

Now we review the QPA-descent.
Suppose that we need to compute the discrete logarithm
of $ W(\zeta) \in \F_{q^{2k}}[\zeta] $, where $ W $  is
a polynomial over $ \F_{q^2} $ of degree $ w >1 $. 
The QPA-descent, firstly proposed in \cite{BGJT13v1}, 
is to represent $ W(\zeta) $ 
as a product of elements of smaller degree, e.g., $ \leqslant w/2 $,
in the field $ \F_{q^2} [x]/ (f(x))  $. To do this,
one again starts with the identity:
\[ \prod_{\alpha \in \F_q } (x-\alpha) = x^q - x.  \]
Then apply the  transformation
\[ x \mapsto \frac{a W(x) + b}{c W(x) +d} \]
where the matrix $ m = \begin{pmatrix} a & b \\ c & d
\end{pmatrix} \in \F_{q^2}^{2 \times 2}$ is nonsingular.
We have 
\[ \prod_{\alpha \in \F_q } (\frac{a W(x) + b}{c W(x) +d} -\alpha) 
= (\frac{a W(x) + b}{c W(x) +d})^q - \frac{a W(x) + b}{c W(x) +d}.  \]
Clearing the denominator:
\begin{eqnarray*}
&&(c W(x) +d) \prod_{\alpha \in \F_q } ((a W(x) + b) -\alpha (c W( x) +d)) \\
&=& (a W(x) + b)^q (c W(x) +d) - (a W(x) + b) (c W(x) +d)^q \\
&=& (a^q \tilde{W}(x^q) + b^q) (cW(x)+d) - 
(a W(x)+b)(c^q \tilde{W}(x^q) + d^q),  
\end{eqnarray*}
where $ \tilde{W} (x) $ is a polynomial obtained by raising the coefficients of 
$ W(x) $ to the $q$-th power.
%Multiplying both sides by $h_1^w (x)$ and 
Replacing $x^q $ with $h_0(x)/h_1(x)$, 
we obtain 
\begin{eqnarray*}
&&  (c W(x) +d) \prod_{\alpha \in \F_q } ( (a W( x) + b) - \alpha (c W(x) +d))\\
&=&  (a^q \tilde{W}(h_0(x)/h_1(x)) + b^q  ) (c W(x)+d) \\
&&- (a W(x) + b ) (\tilde{W}(h_0(x)/h_1(x)) + d^q h_1(x) ) \\
&& \pmod { x^q h_1(x) - h_0(x)}.
\end{eqnarray*}
It was shown in \cite{BGJT13v1} that  matrices in the 
same right coset of $PGL_2(\F_q)$
of $PGL_2(\F_{q^2})$ generate 
the same equations.
The denominator of the right-hand side  is a power of $ h_1(x) $.  
Denote the numerator of the right-hand side polynomial by $ N_{m,W}(x) $.
If the polynomial  $ N_{m,W}(x) $ is $ w/2 $-smooth, 
namely, it can be factored completely into a product of irreducible factors 
over $ \F_{q^2} $, all have degree $ w/2 $ or less,
we obtain a relation of the form 
\begin{equation}\label{Dmrelation}
\prod_{i=1}^{q^2} (W(x) + \alpha_i)^{e_i} 
 = \lambda^{e_0} \prod_{g(x)\in S } g(x)^{e'_g} \pmod { x^q h_1(x) - h_0(x)} ,
\end{equation}
where $ S\subseteq \F_{q^2}[x] $ is a set of monic polynomials of degrees
less than $ w/2 $ and with cardinality at most $ 3 w $. 
Denote the vector $ (e_1, e_2, \dotsc, e_{q^2}) $ by $ \v_m $.
Note that it is a binary vector, and it is independent of $ W(x) $.  
Collecting enough number of relations will allow
us to represent $ W(x) $ as a product of elements of smaller degrees.
This process is the QPA-descent. A heuristic made in \cite{BGJT13v1}
is that repeating this process, one can
represent any element in $ \F_{q^2}[x]/(f(x)) $ 
as a product of linear factors. Combining it with
the fact that the discrete logarithm of the linear factors
are known, one solves the discrete logarithm for any element. 

However, the descent will not work
if $ W(x) $ is a factor of $x^q h_1(x) - h_0 (x)  $. Recall that 
$ \alpha_1=0 $.

%Assuming the simplifying assumption that $x^qh_1(x)-h_0(x)$ has no linear factors over $\F_{q^2}$. Then, all the linear factors 
%$x+\alpha_i$'s are invertible modulo $x^qh_1(x)-h_0(x)$. In this case, canceling the linear factors, we obtain a relation of the form 
%\begin{equation}\label{mrelation}
%\lambda^{e_0} \prod_{i=1}^{q^2} (x + \alpha_i)^{e_i} =1
%\pmod { x^q h_1(x) - h_0(x)} . 
%\end{equation}
%we can show
\begin{theorem}
%there exists polynomials $ h_0 $ and $ h_1 $, such that 
If 
$ W(x) | x^q h_1(x) - h_0 (x)$,  $e_1 $ will always be $ 0$
in (\ref{Dmrelation}).
%In the other words, 
%the relation will not have full rank $ q^2 $ .
\end{theorem}
In other words, if $W(x)$ is a factor of $x^q h_1(x) - h_0(x)  $,
then it will  never appear in the left-hand side of
(\ref{Dmrelation}) as a factor. So the 
descent for $ W(\zeta) $ is not possible. 


\begin{proof}
The polynomial
$ W(x) $ is a zero divisor 
%or nilpotent in the $(x+\alpha_t)$-th component of 
in the ring
$ \F_{q^2}[x] / (x^q h_1 (x) - h_0 (x))$.
% =\F_{q^2}[x]/(f(x)) \bigoplus_{i=1}^m \F_{q^2}[x]/(f_i(x)^{a_i}).\] 
Hence if     $ W(x) $ 
appears in the left-hand side of (\ref{Dmrelation}) as a factor,
it will also appear in the right-hand side. This contradicts 
to the requirement that the factors in the right-hand
side  have degrees smaller than the degree of $ W(x) $. 
\end{proof}

Note that the trap factor $ W(\zeta) $ can appear in the descent paths
of other elements, which essentially blocks the descents.
It is especially troublesome if
 $x^q h_1 (x) - h_0 (x)$ has many small degree factors.

%\section{Yet another lattice}



\subsection{The trap-avoiding descent}


Now we have discovered traps for the original QPA-descent. 
How can we work around them? From the above discussion, 
we assume that we work in a non-Kummer extension,
and the polynomial $ x^q h_1 (x) - h_0 (x)  $ 
with the factorization as in (\ref{ringpolfac}) satisfies
\begin{itemize}
  \item $ \deg(h_0) \leqslant 2, \deg(h_1)\leqslant 1 $,
  \item $ k_i > 1 $ for all $ 1\leqslant i\leqslant l $; in other words, 
it is free of linear factors,
  \item $ \gcd(k, k_i) =1 $  for all $ 1\leqslant i\leqslant l $. 
\end{itemize}
In the most interesting case where $ k $ is a prime, our numerical
data show that the above requirements can be easily satisfied.
For example, when $q=1024$, the result is in Appendix D.


\begin{heuristic}\label{Hh0h1}
Let $ q $ be a prime power and $ k < q $ be a prime. 
Then there exist polynomials $ h_0 $ and $ h_1 $ satisfying
the above requirements.
\end{heuristic}

Assume that the  discrete logarithms of all linear polynomials
have been computed. Suppose that we need to compute the discrete logarithm
of $ W(\zeta) $, where  $ W(x) $ is an irreducible polynomial of
degree less than $ k $, and it is relatively prime to $f(x)$. 
%We will then compute the discrete 
%logarithm of all the factors of $ x^q h_1(x) - h_0 (x) $ whose
%degrees are less than $ k $. To do this, for a factor 
If $ W(x) |  x^q h_1(x) - h_0 (x)$,
we will search for an integer $ i $   
such that $ W(x)^i \pmod{ f(x)} $ is relatively prime to $ x^q h_1(x) - 
h_0 (x) $. Such an $ i $ can be found easily by a random process.

% \begin{algorithmic}
% \State {\bf Input:} $ W(x)\in \F_{q^2}[x] $ with degree $ w $ 
% satisfying $\gcd (W(x), x^q h_1(x) - h_0 (x) ) =1  $
% \State {\bf Output:} A product of polynomials of degrees $ \leqslant w/2 $ 
% that is congruent to $ W(x) $ modulo $ f(x) $. 
% \State Initiate the descent lattice to be the one generated by row vectors of
% \[ \begin{pmatrix} q^{2k} -1 & 0 & \cdots & 0\\
% 0 & q^{2k}-1 & \cdots & 0\\
% \vdots & \vdots & \ddots & \vdots\\
% 0 & 0 & \cdots & q^{2k}-1
% \end{pmatrix}
% \]
% \For{$ m \in \P_q$ }
% \State Compute $ N_{m, W}(x) $
% \If{all its factors have degrees less than $ w/2 $}
% \If{it is relatively prime to $ x^q h_1(x) - h_0 (x) $  } 
% \State add the vector $ \v_m $  into the descent lattice 
% \If{the vector $(1,0,\ldots,0)$ is in the lattice}
% \State Let \[(1,0,\ldots,0) = \sum_{m} g_{m} \v_{m} \]
% \State where $g_{m}\in \Z$.
% \State {\bf Return:} 
% \[ \prod_{m} \left(\frac{N_{m, W(x)}(x)}{h_1^w(x)}\right)^{g_{m}} 
% \] 
% \EndIf
% \EndIf
% \EndIf
% \EndFor
% %\State Solve the linear system over $ \Z/ (q^{2k}-1)\Z $ 
% \end{algorithmic}

Now we can  assume that $ \gcd(W(x), x^q h_1(x) - h_0 (x)) =1 $.
If there are not many traps,  we will 
use a trap-avoiding strategy for the descent.
The basic idea is simple.
Whenever we find a relation (\ref{Dmrelation}),
we will not use it unless the right-hand side is
relatively prime to $ x^q h_1(x) - 
h_0 (x) $. 
\begin{definition}
Define the trap-avoiding descent 
lattice $ \L(W) $  associated with $ W(x) $ to be
generated by
\[ \{ \v_m | N_{m,W} \ is \ w/2-smooth, \ and\ 
\gcd(N_{m,W}, x^qh_1 (x)-h_0(x))=1 \}. \]
\end{definition}
Note that  we  use less
relations than \cite{BGJT13v1} does, since we have to avoid traps. 
If the vector  $(1,0,\ldots,0)$ is in the 
trap-avoiding descent lattice of $ W(x) $,
then $ W(x) $  can be written as a product
of low-degree polynomials in  $\F_{q^2}[x]/(f(x))$ that are not traps. 
We believe that the following heuristic is very likely to be true. 
%make a heuristic that we can still find a
%representation of $ W(x) $ by a product of smooth
%{\em non-trap} polynomials.
\begin{heuristic}\label{Hdescent}
The trap-avoiding descent lattice for $ W(x) $ 
contains the vector $(1,0,\ldots,0)$ if 
$ \gcd(W(x), x^q h_1(x) - h_0 (x)) =1 $.
\end{heuristic}

\begin{remark}
The authors of \cite{BGJT13v2} and \cite{HuangNa13a} proposed their solutions for the traps.
\end{remark}

To provide a theoretical evidence,  we will show 
that $(1,0,\ldots,0)$ is in its super lattice
that is generated by $ \v_m $ for all $ m\in \P_q $, regardless
whether $ N_{m,W} (x) $  is $w/2$-smooth or not.
This is a slight improvement over \cite{BGJT13v1},
where it is proved that 
$(q^3-q, 0, \ldots, 0)$ is in the super lattice.
To proceed, we first make some definitions following 
\cite{BGJT13v1}.
There are two matrices in consideration.
The matrix $\H$ is composed by the binary row vectors $\v_m $ for all 
\[
m = \left( \begin{array}{cc} a & b  \\ c & d \end{array} \right) \in \P_q.
\]
It is a matrix with $q^3+q$ rows and $q^2$ columns.
If we view $ m^{-1} $ as a map from 
$ \Proj^1 (\F_q) $ to $ \Proj^1 (\F_{q^2}) $ 
given by \[ (\beta_1 : \beta_2) \rightarrow ( -d \beta_1 + b \beta_2 : 
c \beta_1 - a \beta_2), \] 
then the $ i $-th component of $ v_m $  is $ 1 $ if there is a point 
$ P \in \Proj^1 (\F_q) $ such that $ m^{-1}(P) = (\alpha_i : 1) $. 
We define a binary vector $\v_m^{+}=(e_1,\dotsc,e_{q^2},e_{q^2+1})$
for $  m \in \P_q $, where $ (e_1,\dotsc,e_{q^2}) = \v_m, $   
and 
\[ e_{q^2+1}= \left\{ 
 \begin{array}{ll}
  1 & \text{if } (a:c) \in \Proj^1 (\F_q) \\
  0 & \text{otherwise.}
\end{array}
\right.
\]
One can verify that the last component of 
$\v_m^{+}$ corresponds to whether there is a point 
$ P \in \Proj^1 (\F_q) $ such that $ m^{-1}(P) = (1:0) = \infty $.
% Given a matrix $m=\left( \begin{array}{cc} a & b 
% \\ c & d \end{array} \right)\in \P_q$, 
% the corresponding factors in the left-hand side of (\ref{Dmrelation}) are 
% $\{W(x)+\frac{d}{c}, W(x)+\frac{b-\alpha d}{a-\alpha c}\mid \alpha \in \F_q\},$
% which includes $W(x)+\infty$ if $c=0$ or $\frac{a}{c}\in \F_q$.
% Define 
% where $e_i=1$ if $W(x)+\alpha_i$
% appears and $0$ otherwise for $1\leqslant i \leqslant q^2$, 
% and $e_{q^2+1}=1$ if $W(x)+\infty$
% appears and $0$ otherwise.
The matrix $\H^{+}$ is composed of the vectors $\v_m^{+}, m\in \P_q$.
$\H^{+}$ is a matrix with $q^3+q$ rows and $q^2+1$ columns. All the row vectors
have exactly $ q+1 $ coordinates which are $ 1 $'s. 



Denote the lattices generated by the row vectors of $\H$ and $\H^{+}$ by $\L(\H)$ 
and $\L(\H^{+})$, respectively. 
In \cite{BGJT13v1}, the authors showed that $\v_1=(q^2+q,\ldots,q^2+q)\in \L(\H^{+})$ 
and $\v_2=(q^2+q,q+1,\ldots,q+1)\in \L(\H^{+})$. 


\begin{theorem}
The vector $(1, 0, \dotsc, 0) $ is in the lattice $\L(\H)$.
\end{theorem}

\begin{proof} Fix a $ \gamma$ such that   $ \F_{q^2} = \F_q[ \gamma] $. 
Firstly, observe that $\v_3=(1,\ldots,1,q)\in \L(\H^{+})$. 
This follows from $\v_3=\sum_{\beta\in\F_q}\v_{m_\beta}\in \L(\H^{+}),$ 
where 
\[
m_\beta=\left( \begin{array}{cc} 1 & \beta\gamma \\ 0 & 1 \end{array} \right) \in \P_q.
\]
%Also note there are $q^2+q$ row vectors in $\H^{+}$  
%whose first coordinate is $1$
%and the sum of these $q^2+q$ vectors 
%is $\v_2=(q^2+q,q+1,\ldots,q+1)\in \L(\H^{+})$. 
%Among these $q^2+q$ vectors, 
There are $q+1$  row vectors in $\H^{+}$   
such that both the first and the last coordinates are $1$.
Since the projective linear map
on a projective line is sharply 3-transitive, 
a third  coordinate with value $ 1 $  will uniquely determine the coset
in $\P_q $. Thus the sum of these $q+1$ vectors is 
$\v_4=(q+1,1,\ldots,1,q+1)\in \L(\H^{+})$.  


From the above observations, we have 
\[
\v_5 = \v_2-(q+1)\v_3= (q^2-1,0,\dotsc,0,1-q^2)\in \L(\H^{+}),
\]
\[
\v_6 = \v_4 - \v_3 = (q,0,\dotsc,0,1)\in \L(\H^{+}).
\]
We deduce 
\[
\v_7 = q\v_6 - \v_5 = (1,0,\dotsc,0,q^2+q-1) \in \L(\H^{+}),
\]
which implies $(1,0,\dotsc,0)\in \L(\H)$. 
\end{proof}




\iffalse
\section{Possible applications of the BGJT-algorithm}
There are many problems related to the discrete logarithms over finite fields, which we may apply
the BGJT-algorithm to solve. 

\subsection{Decoding of Reed-Solomon codes}
Cheng and Wan \cite{CW07} established a connection between the list decoding of Reed-Solomon codes and DLP over finite fields.
This relation may be used to decoding Reed-Solomon codes with BGJT-algorithm.
 
\subsection{Generalized birthday problem}
Wagner \cite{Wagner02} introduced the $k-$sum problem as a generalization of the classic birthday problem.

\begin{definition}
Let $(G,\circ)$ be a group and $k$ lists $L_1,\ldots,L_k$ of elements drawn 
uniformly and independently at from $G^n$. The $k-$sum problem is to find $x_1\in L_1,\ldots,x_k\in L_k$ such that $x_1\circ x_2\circ \ldots \circ x_k$ is the identity of $G$.
\end{definition}
There is a close connection between the $s-$sum problem and discrete logarithm problem (DLP).

\begin{theorem} (\cite{Wagner02})
Given $G=\langle g \rangle$ be a multiplicative group of order $m$. Suppose the DLP in $G$ can be solved in time $t_1$ and the $s-$sum problem over 
$(\Z/m\Z,+)$ with lists of size $l$ can be solved in time $t_2$. Then the $s$-sum problem over $G$ with lists of size $l$ can 
be solved in time $t_2+klt_1$.
\end{theorem}

Thus the BGJT-algorithm may be used to attack the generalized birthday problem over finite fields with small characteristics.
\fi

