\newpage
\part{COMPUTER ALGEBRA}
\chapter[ Algebra]{Algebra\label{chapter:Algebra}}
First,\index{algebra|(} in this chapter, we will discuss some of the basic concepts of algebra, 
such as fields, vector spaces and polynomials
(Section~\ref{sec:algebra1}). Our main focus will be the study of 
 polynomial rings in one variable. These polynomial rings
play a very important role in \textit{constructive applications}. After
this, we will outline the theory of finite fields, putting a strong emphasis on
the problem of constructing them (Section~\ref{sec:algebra2}) and on the problem 
of factoring polynomials over such fields
(Section~\ref{sec:algebra3}). Then we will study lattices and discuss the Lenstra-Lenstra-Lov�sz
algorithm which can be used to find short lattice vectors
(Section~\ref{sec:algebra4}). We will present
a polynomial time algorithm for the factorisation of polynomials with rational
coefficients; this
was the first notable application of the Lenstra-Lenstra-Lov�sz algorithm
(Section~\ref{sec:algebra5}).

\vspace{6mm}
\section{Fields, vector spaces, and polynomials\label{sec:algebra1}}
In this section we will overview some important concepts related to rings and polynomials.

\subsection{Ring theoretic concepts}
We recall some definitions introduced in Chapters~31--33 of 
the textbook \textit{Introduction to Algorithms}.
In the sequel all cross references to Chapters~31--33 refer to
results in that book.

A set $S$ with at least two elements is called a \ki{ring,}\inddef{ring} 
if it has two binary operations, the addition, denoted by the $+$ sign, and
the multiplication, denoted by the $\cdot$ sign. 
The elements of $S$ form an Abelian group\index{group!Abelian}  with respect to the addition,
and they form a monoid (that is, a semigroup\index{semigroup} with an identity),
whose identity element\index{identity element}
is denoted by~1, with respect to the multiplication. 
We assume that $1\neq 0$. Further, the distributive properties also hold: for arbitrary 
elements $a,\ b,\ c\in S $ we have
$$ a\cdot (b+c)= a\cdot b+a \cdot c \quad\mbox{and} $$
$$ (b+c)\cdot a = b\cdot a+c \cdot a \koz . $$ \index{distributive}

Being an Abelian group\index{group!Abelian} with respect to the addition means that the operation is
associative,\index{associative} commutative,\index{commutative}
it has an identity element\index{identity element} 
(denoted by 0), and every element has an inverse with respect to this
identity\index{inverse!additive}. 
More precisely, these requirements are the following:\\
\ki{associative\index{associative} property:} for all triples $a,\ b,\ c\in S$
we have $(a+b)+c=a+(b+c)$;\\
\ki{commutative\inddef{commutative} property:} for all pairs $a,\ b\in S$ we
have  $a+b=b+a$; \\
\ki{existence of the identity element:\index{identity element}} 
for the zero element $0$ of $S$ and
for all elements $a$ of $S$, we have 
$a+0=0+a=a$;\\
\ki{existence of the additive inverse:\inddef{inverse!additive}}  
for all $a\in S$ there exists $b\in S$,
such that $a+b=0$. \\
It is easy to show that
each of the elements $a$ in $S$ has a unique inverse. 
We usually denote the inverse of an element $a$ by $-a$. 

Concerning the multiplication, we require that it must be  associative and that the
multiplicative identity should exist. 
The \ki{identity\inddef{identity element!of a ring}} 
of a ring $S$ is the multiplicative identity of $S$. 
The usual name of the additive identity is 
\ki{zero.\inddef{zero}} 
We usually omit the $\cdot$ sign when writing the multiplication, for example 
we usually write $ab$ instead of  $a\cdot b$.


\begin{pelda} \textit{Rings.} \\
(i) The set $\Z$ of integers\index{integers} 
with the usual operations $+$ and $\cdot$. \\ 
(ii) The set $\Z_m$ of residue classes 
modulo $m$\index{residue classes} with respect to the addition and
multiplication modulo $m$.
(iii) The set $\R^{n\times n}$ of $(n\times n)$-matrices 
with real entries with respect to the addition and multiplication of
matrices. 
\end{pelda}


Let  $S_1$ and $S_2$ be rings. 
A map $\phi:S_1\rightarrow  S_2$ 
is said to be a \ki{homomorphism,}\inddef{homomorphism} 
if $\phi$ preserves the operations, in the sense 
that $\phi(a\pm b)=\phi(a)\pm \phi(b)$ and
$\phi(ab)=\phi(a)\phi(b)$ holds for all pairs $a,\ b\in S_1$. 
A homomorphism $\phi$ is called an \ki{isomorphism,}\inddef{isomorphism} 
if $\phi$ is a one-to-one correspondence, 
and the inverse is also a homomorphism. 
We say that the rings $S_1$ and $S_2$  
are \ki{isomorphic,} if there is an isomorphism between them. 
If $S_1$ and $S_2$ are isomorphic rings, then we write $S_1\cong S_2$.  
From an algebraic point of view, isomorphic rings can be viewed as identical. 


For example the map $\phi:\Z \rightarrow \Z_6$ which maps an integer to its 
residue modulo 6 is a homomorphism: 
$\phi(13)=1,~\phi(5)=5,~\phi(22)=4$, etc. 

A useful and important ring theoretic construction 
is the \ki{direct sum.}\inddef{direct sum} 
The direct sum of the rings 
$S_1$ and $S_2$ is denoted by $S_1\oplus S_2$. 
The underlying set of the direct sum is
$S_1\times S_2$, that is, the set of ordered pairs $(s_1,s_2)$ 
where
$s_i\in S_i$. The operations are defined componentwise:
for $s_i,\ t_i \in S_i$ we let
$$(s_1,s_2)+(t_1,t_2):=(s_1+t_1,s_2+t_2)\quad \mbox{and} $$
$$(s_1,s_2)\cdot (t_1,t_2):=(s_1\cdot t_1,s_2\cdot t_2) \koz . $$
Easy calculation shows that $S_1\oplus S_2$ is a ring
with respect to the operations above. 
This construction can easily be generalised to more than two rings. 
In this case, the elements of the direct sum are 
the $k$-tuples, where $k$ is the number of rings in the direct sum, 
and the operations are defined componentwise.

\subsubsection{Fields.}
A ring  $\F$ is said to be a  \ki{field,}\inddef{field} if its 
non-zero\index{zero}
elements
form an Abelian group\index{group!Abelian} with respect to the multiplication.
The multiplicative inverse\index{inverse!multiplicative} 
of a non-zero element $a$ is usually denoted 
$a^{-1}$. 

The best-known examples of fields are the the 
sets of rational numbers,\index{rational numbers} real numbers,\index{real
numbers} and complex numbers\index{complex numbers} with respect to
the usual operations. We usually denote these fields by $\Q, \ \R, \
\C$, respectively. 

Another important class of fields consists of the fields $\F_p$ of
$p$-elements where $p$ is a prime number. The elements of $\F_p$ are the
residue classes\index{residue classes} modulo $p$, and the operations are the
addition and the multiplication defined on the residue classes. The
distributive property can easily be derived from the distributivity of the
integer operations. 
By Theorem~33.12, $\F_p$ is a group\index{group} with respect to the addition, and,
by Theorem 33.13, the set $\F_p^*$ of non-zero elements of $\F_p$ 
is a group\index{group} with respect to the multiplication.
In order to prove this latter claim, we need to use that $p$ is a prime
number. 

\subsubsection{Characteristic, prime field.}
In an arbitrary field, we may consider 
the set of elements of the form $m\cdot 1$, that is, the
set of elements that can be written as the sum $1+\cdots+1$ of $m$ copies of 
the multiplicative identity where $m$ is a positive integer. 
Clearly, one of the two possibilities must hold:\\
(a) none of the elements $m\cdot 1$ is zero;\index{zero} \\
(b) $m\cdot 1$ is zero for some $m\geq 1$.

In case~(a) we say that $\F$ is a field with \ki{characteristic
zero.}\inddef{field!of characteristic zero}  
In case~(b) the \ki{characteristic}\inddef{characteristic} 
of $\F$ is the smallest  $m\geq 1$ such that
$m\cdot 1=0$. In this case, the number $m$ must be a prime, for, if $m=rs$, then 
$0=m\cdot 1 =rs \cdot 1=(r\cdot 1)(s\cdot 1)$, and so either
$r\cdot 1=0$ or $s\cdot 1=0.$ 

Suppose that $P$ denotes the smallest subfield of $\F$
that contains $1$. Then $P$ is said to be the 
\ki{prime field}\inddef{prime field} of $\F$.  
In case~(a) the subfield $P$ consists of the elements 
$(m \cdot 1)(s\cdot 1)^{-1}$ where $m$ is an integer 
and $s$ is a positive integer. 
In this case, $P$ is isomorphic to the
field $\Q$ of rational numbers. 
The identification is obvious: $(m \cdot 1)(s\cdot 1)^{-1}\leftrightarrow
m/s.$ 

In case~(b) the characteristic is a prime number, 
and $P$ is the set of elements $m\cdot 1$ where $0\leq m< p$. 
In this case, $P$ is isomorphic to the field $\F_p$ of residue classes modulo 
$p$.
 
\subsubsection{Vector spaces.}
Let $\F$ be a field.\index{field}  
An additively written Abelian group\index{group!Abelian} $V$ 
is said to be a \ki{vector space}\inddef{vector space} 
over $\F$, or simply an $\F$-vector space, if for all elements 
$a\in\F$ and $v\in V$, an element $av\in V$ is defined (in other words, $\F$
acts on $V$) and the following hold:
$$ a (u+v)=au+av, ~~(a+b)u=au+bu \koz , $$
$$ a(bu)=(ab)u, ~~1u=u \koz . $$  
Here  $a,\ b$ are arbitrary elements of  
$\F$, the elements  $u,\ v$ are arbitrary in $V$, and the element~1 is the
multiplicative identity of $\F$.\index{identity element!multiplicative} 

The space of $(m\times n)$-matrices over $\F$ is an important example of
vector spaces. Their properties are studied in Chapter~31. 


A vector space $V$ over a field $\F$ is said to be
\ki{finite-dimensional}\index{dimension} if
there is a collection
$\{v_1, \ldots ,v_n\}$ of finitely many elements in $V$ 
such that each of the elements $v\in V$ can be written as 
a \ki{linear combination} $v=a_1v_1+\cdots +a_nv_n$ for some
$a_1,\ldots , a_n\in\F$. Such a set
$\{v_i\}$ 
is called a \ki{generating set}\inddef{generating set!of vector spaces} of $V$.
The cardinality of the smallest generating set of $V$ is referred to as the
\ki{dimension}\inddef{dimension} of $V$ over $\F$, denoted 
$\dim_{\F}V$. In a finite-dimensional vector space, 
a generating system containing $\dim_{\F}V$ elements
is said to be a \ki{basis.}\inddef{basis!of a vector space} 

A set $\{v_1,\ldots ,v_k\}$ of elements of a vector space $V$ 
is said to be \ki{linearly independent,}\inddef{linear independence}
if, for $a_1,\ldots,a_k\in\F$, the equation 
$0=a_1v_1+\cdots +a_kv_k$ implies $a_1=\cdots =a_k=0$.
It is easy to show that a basis in $V$ is a linearly independent set.
An important property of linearly independent sets is that 
such a set  can be extended
to a basis of the  vector space.
The dimension of a vector space coincides with the cardinality of its largest
linearly independent set.


A non-empty subset $U$ of a vector space 
$V$ is said to be  a \ki{subspace}\inddef{subspace} of $V$, 
if it is an (additive) subgroup\index{subgroup!additive} 
of $V$, and $au\in U$ holds for all $a\in\F$ and $u\in U$.
It is obvious that a subspace can be viewed as a vector space.

The concept of homomorphisms can be defined for vector spaces, but in this
context we usually refer to them as \ki{linear maps.}\inddef{linear
mapping} Let $V_1$ and $V_2$ be vector spaces over a common field $\F$. 
A map  $\phi:V_1 \rightarrow  V_2$ 
is said to be linear, 
if, for all $a,\ b\in \F$ and $u,\ v\in V_1$, we have
$$\phi(au+bv)=a\phi(u)+ b\phi(v) \koz .$$ 
The linear mapping $\phi$  is an
\ki{isomorphism}\inddef{isomorphism!of vector spaces} if $\phi$ 
is a one-to-one correspondence and its inverse is also a homomorphism.
Two vector spaces are said to be isomorphic if there is an isomorphism between
them. 

\begin{lemma} \label{linearis}
Suppose that 
$\phi:V_1 \rightarrow  V_2$ is a linear mapping. 
Then $U=\phi(V_1)$ 
is a subspace in $V_2$. If $\phi$ is one-to-one,\index{one-to-one map} then
$\dim_{\F}U =\dim_{\F}V_1$. If, in this case, $\dim_\F V_1=\dim_\F V_2<\infty$, then $U=V_2$ and 
the mapping $\phi$ is an isomorphism.
\end{lemma}

\begin{biz} As
$$
\phi(u)\pm \phi(v)= \phi(u\pm v) \quad\mbox{and}\quad a\phi(u)=\phi(au), 
$$ 
we obtain that $U$ is a subspace. Further, it is clear that the images of the
elements of a generating set of $V_1$ form a generating set for $U$. 
Let us now suppose that $\phi$ is one-to-one.
In this case, the image of a linearly independent subset of $V_1$ is linearly
independent in $V_2$. 
It easily follows from these observations
that the image of a basis of $V_1$
is a basis of $U$, and so
$\dim_{\F}U =\dim_{\F}V_1$. If we assume, in addition, that
 $\dim_{\F}V_2 =\dim_{\F}V_1$, then a basis of  $U$ is also a basis of $V_2$,
 as it is a linearly independent set, and so it can be extended to a basis
of $V_2$. Thus $U=V_2$ and the mapping $\phi$ must be a one-to-one
correspondence. It is easy to see, and is left to the reader, that
$\phi^{-1}$ is a linear mapping. \index{linear mapping}
\end{biz}  



The \ki{direct sum}\index{direct sum} 
 of vector spaces can be defined similarly to the direct sum of rings. 
The direct sum of the vector spaces $V_1$ and
$V_2$ is denoted by $V_1\oplus V_2$. The underlying set of the direct sum
is $V_1\times V_2$, and the addition and the action of the field 
$\F$ are defined componentwise.
It is easy to see that
$$\dim_{\F}\left(V_1 \oplus V_2\right)=\dim_{\F}V_1+\dim_{\F}V_2 \koz . $$


\subsubsection{Finite multiplicative subgroups of fields.} 
Let $\F$ be a field and let $G\subseteq \F$ be a finite multiplicative
subgroup of $\F$.\index{subgroup!multiplicative}
That is, the set  $G$ contains finitely many 
elements of $\F$, each of which is non-zero, 
$G$ is closed under multiplication, and the
multiplicative inverse of an element of $G$ also lies in $G$. 
We aim to show that the group $G$ is cyclic, 
that is, $G$ can be generated by a single element. 
The main concepts related to cyclic groups can be found
in Section~33.3.4. $\mbox{ord}(a)$ 
\inddef{order!of a group element} 
of an element $a\in G$
is the smallest positive integer $k$ such that $a^k=1$. 

The cyclic group\index{group!cyclic}  generated by an element $a$
is denoted by
$\langle a\rangle$. 
Clearly,  $|\langle a\rangle |= \mbox{ord} (a)$, and
an element $a^i$ generates the group $\langle a\rangle$ if and only if
$i$ and $n$ are relatively prime.
Hence the group $\langle a\rangle$ has exactly 
$\phi(n)$ generators where $\phi$ is 
Euler's totient function\nevindex{Euler, Leonhard (1707--1783)} (see Subsection 33.3.2).

The following identity is valid for an arbitrary
integer $n$:
$$ \sum _{d\mid n}\phi(d)=n. $$
Here 
the summation index $d$ runs through all positive divisors of $n$.
In order to verify this identity, consider 
all the rational numbers $i/n$ with $1\leq i\leq n$. The number of these is
exactly $n$.  
After simplifying these fractions, they will be of the form 
$j/d$ where $d$ is a positive divisor of $n$.
A fixed denominator $d$ 
will occur exactly $\phi(d)$ times. 

\begin{tetel} \label{ciklikus}
Suppose 
that $\F$ is a field and let $G$ be a finite multiplicative 
subgroup of $\F$.
Then there exists an element $a\in G$ such that
$G=\langle a\rangle$.
\end{tetel}
\begin{biz} 
Suppose that $|G|=n.$ Lagrange's\nevindex{Lagrange, Joseph Louis (1736--1813)}\index{Lagrange's theorem}
theorem (Theorem~33.15) implies that the order of an element $b\in G$ is a divisor of $n$. 
We claim, for an arbitrary $d$, that there are at most $\phi(d)$ elements 
in $\F$ with order $d.$ The elements with order  $d$ are roots of the polynomial $x^d-1$. 
If $\F$ has an element $b$ with order $d$, then, by Lemma~\ref{gyokszam},
$x^d-1=(x-b)(x-b^2)\cdots (x-b^d)$ (the lemma will be verified later). 
Therefore all the elements of $\F$ with order $d$ 
are contained in the group $\langle b\rangle$, which, in turn, contains 
exactly $\phi(d)$ elements of order $d$. 

If $G$ had no element of order $n$, 
then the order of each of the elements of $G$ would be a proper divisor 
of $n$. In this case, however, using the identity above and the fact that $\phi(n)>0$,
we obtain $$ n=|G|\leq \sum_{d\mid n,\ d<n}\phi(d)<n \koz , $$
which is a contradiction.
\end{biz} 


\subsection{Polynomials}
Suppose that $\F$ is a field and that $a_0,\ldots, a_n$ are elements of $\F$. 
Recall that an expression of the form
$$ f=f(x)=a_0+a_1x+a_2x^2+ \cdots +a_nx^n\koz, $$
where $x$ is an indeterminate,
is said to be a \ki{polynomial} over $\F$\inddef{polynomial}
(see Chapter~32). The scalars $a_i$ 
are the \ki{coefficients} of the polynomial $f$. 
The degree of the zero polynomial is zero,
while the \ki{degree}\inddef{degree} of a non-zero polynomial $f$
is the largest index $j$ such that $a_j\neq 0$. The degree of  $f$ is denoted by $\fok f$.


The set of all polynomials over $\F$ in the indeterminate $x$ 
is denoted by $\F[x]$.
If 
$$ f=f(x)=a_0+a_1x+a_2x^2+ \cdots +a_nx^n $$
and
$$ g=g(x)=b_0+b_1x+b_2x^2+ \cdots +b_nx^n $$
are polynomials with degree not larger than $n$, then 
their sum is defined as 
the polynomial 
$$ h=h(x)=f+g=c_0+c_1x+c_2x^2+ \cdots +c_nx^n $$
whose coefficients are $c_i=a_i+b_i$. 

The product $fg$ of the polynomials 
$f$ and $g$  is defined as the polynomial
$$ fg=d_0+d_1x+d_2x^2+ \cdots +d_{2n}x^{2n} $$ 
with degree at most $2n$ whose 
coefficients are given by the equations $d_j=\sum_{k=0}^ja_kb_{j-k}$. 
On the right-hand side of these equations, 
the coefficients with index greater
than $n$ are considered zero.
Easy computation shows that 
$\F[x]$ is a commutative ring with respect to these operations.
It is also straightforward to show that 
$\F[x]$  has no 
\ki{zero divisors,} that is,  whenever $fg=0$, then either $f=0$ or $g=0$. 

\subsubsection{Division with remainder and divisibility.} 
The ring $\F[x]$ of polynomials over $\F$ is quite similar, in many ways, 
to the ring $\Z$ of integers.
One of their similar features is that the procedure of 
division with remainder can be
performed in both rings.

\begin{lemma}\label{maradekososztas}
\inddef{division with remainder!of polynomials}
Let $f(x),\ g(x)\in \F[x]$ be polynomials such that $g(x)\neq 0$. 
Then there there exist
polynomials $q(x)$ and $r(x)$ such that
$$ f(x)=q(x)g(x)+r(x) \koz , $$
and either $r(x)=0$ or $\fok r(x)<\fok g(x)$. Moreover, the polynomials
$q$ and $r$ are uniquely determined by these conditions.
\end{lemma} 
\begin{biz} 
We verify the claim about the existence of the polynomials 
$q$ and $r$ by induction on 
the degree of $f$. 
If  $f=0$ or  $\fok f <\fok g$, then the assertion clearly holds.
Let us suppose, therefore, that 
$\fok f \geq \fok g$. Then subtracting a suitable multiple $q^*(x)g(x)$ of
$g$  from $f$, we obtain
that the degree of 
$f_1(x)=f(x)-q^*(x)g(x)$ is smaller than $\fok f(x)$. 
Then, by the induction hypothesis,
there exist polynomials $q_1$ and $r_1$ such that
$$f_1(x)=q_1(x)g(x)+r_1(x)$$ 
and either $r_1=0$ or $\fok r_1<\fok g$. 
It is easy to see that, in this case, the polynomials 
$q(x)=q_1(x)+q^*(x)$ and $r(x)=r_1(x)$ are as required.

It remains to show that the polynomials $q$ and $r$ are unique. 
Let $Q$ and $R$ be polynomials, possibly different from $q$ and $r$, 
satisfying the assertions of the lemma. That is, $f(x)=Q(x)g(x)+R(x)$, and so 
$(q(x)-Q(x))g(x)=R(x)-r(x)$. If the polynomial on the left-hand side is
non-zero, then its degree is at least $\fok g$, while the degree of the
polynomial on the right-hand side is smaller than $\fok g$. 
This, however, is not possible.
\end{biz}



Let $R$ be a commutative ring with a multiplicative identity 
and without zero divisors, and set
$R^*:=R\setminus \{0\}$. 
The ring $R$ is said to be a
\ki{Euclidean ring}\index{ring!Euclidean} 
if there is a function $\phi: R^* \rightarrow \N$
such that $\phi(ab)\geq \phi(a)\phi(b)$, for all $a,\ b \in R^*$; 
and, further, if  
$a\in R$, $b\in R^*$, then there are elements $q,\ r\in R$ such that
$a=qb+r$, and if $r\neq 0$, then $\phi(r)< \phi(b)$. The previous lemma
shows that $\F[x]$ is a Euclidean ring where the r\^ole of the function 
$\phi$ is played by the degree function.

The concept of \ki{divisibility}\inddef{divisibility!of polynomials}   
in $\F[x]$ can be defined similarly 
to the definition of the corresponding concept in the ring of integers.
A polynomial $g(x)$ is said to be a   \ki{divisor} of 
a polynomial $f(x)$ (the notation is
$g\mid f$), if there is a polynomial
$q(x)\in\F[x]$ such that $f(x)=q(x)g(x)$. 
The non-zero elements of $\F$, which are clearly divisors of each of the polynomials, are
called the \ki{trivial divisors} or  
\ki{units.}\inddef{unit} 
A non-zero  polynomial $f(x)\in \F[x]$ is said to be 
\ki{irreducible,}\index{irreducible polynomial|see{polynomial}}\inddef{polynomial!irreducible}
if whenever 
$f(x)=q(x)g(x)$ with $q(x),\ g(x)\in\F[x]$, then
either $q$ or
$g$ is a unit.

Two polynomials $f,\ g\in \F[x]$ are called 
\ki{associates,}\inddef{associate polynomials} 
if there is some $u\in \F^*$ such that
$f(x)=u g(x)$. 


Using Lemma~\ref{maradekososztas}, one can easily prove the
unique factorisation theorem in the ring  of polynomials following
the argument of the proof of the corresponding theorem in the ring of integers (see Section~33.1).
The role of the absolute value of integers
is played by the degree of polynomials.
\begin{tetel}
\label{ufd}\index{unique factorisation}
An arbitrary polynomial  $0\neq f\in \F[x]$ can be written in the form
$$f(x)=u   q_1(x)^{e_1}\cdots q_r(x)^{e_r}, $$
where $u   \in \F^*$ is a unit, the polynomials $q_i\in \F[x]$ 
are pairwise non-associate and irreducible, and, further, the numbers 
$e_i$ are positive integers. Furthermore, this decomposition is essentially
unique in the sense that whenever
$$f(x)=U   Q_1(x)^{d_1}\cdots Q_s(x)^{d_s} $$
is another such decomposition, then $r=s$, and,
after possibly reordering
the  factors $Q_i$, the polynomials $q_i$ and $Q_i$ are associates, and moreover
$d_i=e_i$ for all $1\leq i\leq r$. 
\end{tetel}
Two polynomials are said to be \ki{relatively prime,\inddef{relatively prime!polynomials}} 
if they have no common irreducible divisors.

  
A scalar $a\in \F$ is a  \ki{root}\inddef{root!of a polynomial}
of a polynomial $f\in \F[x]$, if $f(a)=0$. 
Here the value $f(a)$ is obtained by substituting $a$ into the place of $x$ in $f(x)$.
\begin{lemma} \label{gyokszam}
Suppose that $a\in \F$ is a root of  a polynomial 
$f(x)\in \F[x]$. Then there exists a polynomial $g(x)\in \F[x]$ such that
$ f(x)=(x-a)g(x)$. 
Hence the polynomial $f$ may have at most 
$\fok f$ roots.
\end{lemma} 
\begin{biz} By Lemma~\ref{maradekososztas}, 
there exists $g(x)\in\F[x]$ and $r\in\F$ such that $f(x)=(x-a)g(x)+r$.
Substituting $a$ for $x$, we find that $r=0$.
The second assertion now follows by induction on $\deg f$ from the fact that
the roots of $g$ are also roots of $f$.
\end{biz}


\subsubsection{The cost of the operations with  polynomials.\inddef{cost of polynomial
operations}}
Suppose that $f(x),\ g(x)\in \F[x]$ are polynomials of degree at most $n$. 
Then the polynomials $f(x)\pm g(x)$ can obviously be computed using $O(n)$ 
field operations. The product $f(x)g(x)$ can be obtained, using its definition,
by $O(n^2)$ field operations. If the Fast Fourier Transform can be performed
over $\F$, \index{fast Fourier transform} then the multiplication can be
computed using only $O(n\lg n)$ field operations (see
Theorem~32.2). %%\marginpar{Reference to NA!}
For general fields, the cost of 
the fastest known multiplication algorithms for polynomials
(for instance the Sch�nhage\nevindex{Sch�nhage, Arnold}--Strassen\nevindex{Strassen, Volker}-method)
is $O(n\lg n\lg\lg n)$, that is, ${\widetilde O}(n)$ field operations.



The division with remainder,\index{division with remainder!of polynomials} 
that is, determining the polynomials $q(x)$ and $r(x)$ for which
$f(x)=q(x)g(x)+r(x)$ and either $r(x)=0$ or $\fok r(x)<\fok g(x),$  can be
performed using $O(n^2)$ field operations following the straightforward 
method outlined in the proof of Lemma~\ref{maradekososztas}. 
There is, however, an algorithm 
(the Sieveking\nevindex{Sieveking, Malte}--Kung\nevindex{Kung, H. T.} algorithm)
for the same problem using only
${\widetilde O}(n)$ steps. 
The details of this algorithm are, however, not discussed here.

\subsubsection{Congruence,\inddef{congruence!of polynomials} 
residue class ring.\inddef{residue class ring}} 
Let $f(x)\in \F[x]$ with $\fok f=n>0$, and let $g,\ h\in \F[x]$.
We say that $g$ is \ki{congruent} to
$h$ modulo $f$, or simply
$g\equiv h\mypmod{f}$,  if $f$ divides the polynomial 
$g-h$. This concept of 
congruence is similar to the corresponding concept 
introduced in the ring of integers (see~33.3.2). 
It is easy to see from the definition that
the relation $\equiv$ is an equivalence relation\index{equivalence relation} 
on the set $\F[x]$. Let  $[g]_f$ (or simply $[g]$ if $f$ is clear from the
context) denote the equivalence class containing $g$. 
From Lemma~\ref{maradekososztas} we obtain immediately,
for each $g$, that there is a unique $r\in\F[x]$ such that $[g]=[r]$, and
either $r=0$ (if $f$ divides $g$) or $\fok r<n$. This polynomial $r$ 
is called the \ki{representative} of the class $[g]$. The set of equivalence
classes is traditionally denoted by $\F[x]/(f)$.   

\begin{lemma}\label{kompatibilitás}
Let $f,\ f_1,\ f_2,\ g_1,\ g_2\in \F[x]$ and let $a\in \F$. 
Suppose that 
$f_1\equiv f_2\mypmod{f}$ and $g_1\equiv g_2 \mypmod{f}$. 
Then
$$f_1+g_1\equiv f_2+g_2\mypmod{f} \koz ,$$ 
$$f_1g_1\equiv f_2g_2\mypmod{f} \koz ,$$
and
$$af_1\equiv af_2 \mypmod{f} \koz . $$
\end{lemma} 
\begin{biz} 
The first congruence is valid, as
$$(f_1+g_1)-(f_2+g_2)=(f_1-f_2)+(g_1-g_2) \koz , 
$$ 
and the right-hand side of this is clearly divisible by $f$.
The second and the third congruences follow similarly from 
the identities $$f_1g_1-f_2g_2=(f_1-f_2)g_1+(g_1-g_2)f_2$$
and 
$$
af_1-af_2=a(f_1-f_2) \koz ,
$$ 
respectively.
\end{biz}



The previous lemma makes it possible to define the sum and the product of
two congruence classes $[g]_f$ and $[h]_f$ as 
$[g]_f+[h]_f:=[g+h]_f$ and
$[g]_f[h]_f:=[gh]_f$, respectively. 
The lemma claims that
the sum and the product are independent of the choice of the congruence class
representatives.
The same way, we may define the action of $\F$ on the set of congruence 
classes: we set $a[g]_f:=[ag]_f$.

\begin{tetel}\label{maradekosztalygyuru}
Suppose that $f(x)\in \F[x]$ and that $\fok f=n>0$. \\ 
(i) The set of residue classes $\F[x]/(f)$ is a commutative ring with an 
identity 
under the operations $+$ and $\cdot$ defined above.\\
(ii) The ring $\F[x]/(f)$ contains the field $\F$ as a subring, and it is an
$n$-dimensional vector space over $\F$. Further, the residue classes
$[1],\ [x],\ldots ,[x^{n-1}]$ form a basis of $\F[x]/(f)$. \\
(iii) If $f$ is an irreducible polynomial in $\F[x]$, then $\F[x]/(f)$  is a field.
\end{tetel}
\begin{biz}(i) The fact that $\F[x]/(f)$ is a ring follows easily from the fact
that $\F[x]$ is a ring.
Let us, for instance, verify the distributive property:
$$ [g]([h_1]+[h_2])=[g][h_1+h_2]=[g(h_1+h_2)]=[gh_1+gh_2]=[gh_1]+[gh_2]=
[g][h_1]+[g][h_2] \koz . $$
The zero element of $\F[x]/(f)$ is the class $[0]$, the additive inverse of
the class $[g]$  is the class $[-g]$, while the multiplicative identity element
is
the class $[1]$. The details are left to the reader.

(ii) The set $\{[a]\ |\ a\in \F\}$ is a subring isomorphic to $\F$.
The correspondence is obvious: $a\leftrightarrow [a]$. By part~(i),  
$\F[x]/(f)$ is an additive 
Abelian group, and the action of 
$\F$ satisfies the vector space axioms.
This follows from the fact that the polynomial ring is itself a vector space
over $\F$. 
Let us, for example, verify the distributive property:
$$ a([h_1]+[h_2])=a[h_1+h_2]=[a(h_1+h_2)]=[ah_1+ah_2]=[ah_1]+[ah_2]=
a[h_1]+a[h_2] \koz. $$
The other properties are left to the reader.

We claim that the classes $[1],\ [x],\ldots ,[x^{n-1}]$ are linearly 
independent. For, if
$$ [0]=a_0[1]+a_1[x]+\cdots +a_{n-1}[x^{n-1}]=
[a_0+a_1x+\cdots +a_{n-1}x^{n-1}] \koz , $$
then $a_0=\cdots =a_{n-1}=0$, as the zero polynomial is the unique polynomial
with degree less than $n$ that is divisible by $f$.
On the other hand, for a polynomial $g$, 
the degree of the class representative of 
$[g]$ is less than $n$. Thus the class
$[g]$ can be expressed as a linear combination of the classes
$[1],[x],\ldots ,[x^{n-1}]$. Hence the classes
$[1],[x],\ldots ,[x^{n-1}]$ form a basis of $\F[x]/(f)$, and so
$\dim_{\F}\F[x]/(f)=n$. 

(iii) Suppose that $f$ is irreducible. First we show that
$\F[x]/(f)$ has no zero divisors. 
If $[0]=[g][h]=[gh]$, then $f$ divides $gh$,
and so $f$ divides either $g$ or $h$. That is, either $[g]=0$ or $[h]=0$.
Suppose now that $g\in \F[x]$ with $[g]\neq [0]$. 
We claim that the classes $[g][1],[g][x],\ldots ,[g][x^{n-1}]$ 
are linearly independent.
Indeed, an equation 
$[0]=a_0[g][1]+\cdots +a_{n-1}[g][x^{n-1}]$ implies
 $[0]=[g][a_0+\cdots +a_{n-1}x^{n-1}]$, and, in turn, it also yields
that $a_0=\cdots =a_{n-1}=0$.
Therefore the classes $[g][1],[g][x],\ldots ,[g][x^{n-1}]$ form a basis of $\F[x]/(f)$.
Hence there exist coefficients $b_i\in \F$ for which
$$[1]=b_0[g][1]+\cdots +b_{n-1}[g][x^{n-1}]=
[g][b_0+\cdots +b_{n-1}x^{n-1}] \koz .$$ 
Thus we find that the class $[0]\neq [g]$ has a multiplicative inverse, and so
$\F[x]/(f)$ is a field, as required.
\end{biz}
 


We note that the converse of part~(iii) of the previous theorem
is also true, and its proof is left to the reader 
(Exercise~\ref{fldquo-irred-ex}).


\begin{pelda}\label{Szamolasmaradekosztalygyuruben}
We usually represent the elements of the residue class ring
$\F[x]/(f)$ by their representatives,
which are polynomials with degree less than $\fok f$.


1. Suppose that $\F=\F_2$ is the field of two elements, and let 
$f(x)=x^3+x+1$. 
Then the ring $\F[x]/(f)$ has 8 elements, namely
$$ 
[0],~[1],~[x],~[x+1],~[x^2],~[x^2+1],~[x^2+x],~[x^2+x+1]. 
$$
Practically speaking, 
the addition between the classes is the 
is addition of polynomials. 
For instance
$$[x^2+1]+[x^2+x]=[x+1] \koz .$$ 
When computing the product, we compute the product of the representatives, 
and substitute it (or reduce it) with its remainder after dividing 
by $f$. For instance, 
$$[x^2+1]\cdot [x^2+x]=[x^4+x^3+x^2+x]=[x+1] \koz .$$
The polynomial $f$ is irreducible over $\F_2$, since it has degree 3, and has
no roots. Hence the residue class ring $\F[x]/(f)$ is a field.

2. Let $\F=\R$ and let $f(x)=x^2-1$. The elements of the residue class ring
are the classes of the form $[ax+b]$ where  $a,\ b\in \R$. 
The ring   $\F[x]/(f)$ is not a field, since $f$
is not irreducible. For instance, $[x+1][x-1]=[0]$.  
\end{pelda}
\begin{lemma} \label{minimalpolinom} 
Let $\mathbb{L}$ be a field containing a field $\F$ and let 
$\alpha\in \mathbb{L}$.  \\
(i) If $\mathbb{L}$ is finite-dimensional as a vector space over $\F$, 
then there is a non-zero polynomial
$f\in \F[x]$ such that $\alpha$ is a root of $f$. \\ 
(ii) Assume that there is a polynomial $f\in\F[x]$ with $f(\alpha)=0$,
and let  $g$ be such a polynomial with minimal degree.
Then the polynomial $g$ is irreducible in $\F[x]$. Further, if $h\in\F[x]$ with
$h(\alpha)=0$ then 
$g$ is a divisor of  $h$. 
\end{lemma}
\begin{biz} (i)
For a sufficiently large $n$,  the elements $1,\alpha, \ldots, \alpha^n$ 
are linearly dependent over $\F$. A linear dependence
gives a polynomial $0\neq f\in \F[x]$ such that $f(\alpha)=0$.  

(ii) If $g=g_1g_2$, then, as $0=g(\alpha)=g_1(\alpha)g_2(\alpha)$,
the element $\alpha$ is a root of either $g_1$ or $g_2$. 
As $g$ was chosen to have minimal degree, 
one of the polynomials $g_1,\ g_2$ is a unit, and so $g$ is irreducible.
Finally, let $h\in\F[x]$ such that $h(\alpha)=0$. Let 
$q,\ r\in \F[x]$  be the polynomials as in Lemma~\ref{maradekososztas} for which
$h(x)=q(x)g(x)+r(x)$. Substituting $\alpha$ for $x$ into the last equation, 
we obtain $r(\alpha)=0$, which is only possible if $r=0$. 
\end{biz}



\begin{defi} The polynomial $g\in \F[x]$ in the last lemma is said to be 
a \ki{minimal polynomial}\inddef{minimal polynomial} of $\alpha$. 
\end{defi}

It follows from the previous lemma that the minimal polynomial is unique
up to a scalar multiple. 
It will often be helpful to assume that the leading coefficient (the coefficient of the term
with the highest degree) of the minimal polynomial $g$ 
is~1.    

\begin{kov} \label{min-kov}
Let  $\mathbb{L}$ be a field containing $\F$, 
and let $\alpha\in \mathbb{L}$.
Suppose that $f\in\F[x]$ is irreducible and that  $f(\alpha)=0$. 
Then $f$ is a minimal polynomial of $\alpha$.
\end{kov}
\begin{biz}  Suppose that $g$ is a minimal polynomial of $\alpha$. 
By the previous lemma, $g\mid f$ and $g$ is irreducible. 
This is only possible if the polynomials 
$f$ and $g$ are associates.
\end{biz} 



Let $\mathbb{L}$ be a field containing 
$\F$ and let $\alpha\in \mathbb{L}$. 
Let $\F(\alpha)$ denote the smallest subfield 
of $\mathbb L$ that contains $\F$ and $\alpha$.
\begin{tetel}\label{egyszeru-bovites}
Let  $\mathbb{L}$ be a field containing 
$\F$ and let $\alpha\in \mathbb{L}$. 
Suppose that $f\in \F[x]$ is a minimal polynomial of  $\alpha$.
Then the field $\F(\alpha)$ is isomorphic to the field $\F[x]/(f)$. 
More precisely, 
there exists an isomorphism $\phi: \F[x]/(f)\rightarrow \F(\alpha)$
\index{isomorphism}
such that $\phi(a)=a$, for all $a\in \F$, and $\phi([x]_f)=\alpha$.
The map  $\phi$ is also an isomorphism of vector spaces\index{vector space} 
over $\F$, and so $\dim_{\F}\F(\alpha)=\fok f$. 
\end{tetel}
\begin{biz} Let us consider the map
 $\psi: \F[x]\rightarrow \mathbb{L}$, which maps a polynomial $g\in \F[x]$
 into  $g(\alpha)$. This is clearly a ring homomorphism, and
$\psi(\F[x])\subseteq \F(\alpha)$. We claim that $\psi(g)=\psi(h)$ if
and only if $[g]_f=[h]_f$. Indeed,
$\psi(g)=\psi(h)$ holds if and only if $\psi(g-h)=0$, that is, if
$g(\alpha)-h(\alpha)=0$, which, by Lemma~\ref{minimalpolinom}, is equivalent  
to $f\mid g-h$, and this  amounts to saying that 
$[g]_f=[h]_f$. Suppose that $\phi$ is the map $ \F[x]/(f)\rightarrow
\F(\alpha)$ induced by 
$\psi$, that is,
$\phi([g]_f):=\psi(g)$. 
By the argument above, the map $\phi$ is one-to-one. 
Routine computation shows that $\phi$ is a ring, and also a vector space,
homomorphism.\index{homomorphism}  
As $\F[x]/(f)$ is a field, its homomorphic image
 $\phi(\F[x]/(f))$ is also a field. 
The field $\phi(\F[x]/(f))$ contains $\F$ and $\alpha$, and so
necessarily $\phi(\F[x]/(f))=\F(\alpha)$.
\end{biz}

\subsubsection{Euclidean algorithm and\inddef{Euclidean 
algorithm!for polynomials.} 
the greatest common divisor.\inddef{greatest common divisor!of polynomials}}
Let  $f(x),\ g(x)\in \F[x]$ be polynomials such that
$g(x)\neq 0$. Set $f_0=f$, 
$f_1=g$  and define the polynomials $q_i$ and
$f_i$ using division with reminder as follows:
$$ f_0(x)=q_1(x)f_1(x)+f_2(x) \koz, $$
$$ f_1(x)=q_2(x)f_2(x)+f_3(x) \koz , $$
$$ \vdots $$
$$ f_{k-2}(x)=q_{k-1}(x)f_{k-1}(x)+f_k(x) \koz, $$
$$ f_{k-1}(x)=q_k(x)f_k(x)+f_{k+1}(x) \koz . $$
Note that if 
$1< i<k$ then $\deg f_{i+1}$ is smaller than $\deg f_i$. We form this sequence
of polynomials until we obtain that $f_{k+1}=0$.   
By Lemma~\ref{maradekososztas}, this defines a finite process. 
Let $n$ be the maximum of $\deg f$ and 
$\deg g$. As, in each step, we decrease the degree of the polynomials, 
we have $k\leq n+1$.  The computation outlined above is usually referred to as
the \ki{Euclidean algorithm.} A version of this algorithm for the ring
of integers is described in Section~33.2. 

We say that the polynomial $h(x)$ is the \ki{greatest common divisor} 
of the polynomials $f(x)$ and $g(x)$, if 
$h(x)\mid f(x)$, $h(x)\mid g(x)$, and,  if a polynomial $h_1(x)$ is a divisor
of $f$ and $g$, then $h_1(x)$ is a divisor of $h(x)$. The usual notation for
the greatest common divisor of $f(x)$ and
$g(x)$ is $\gcd(f(x),g(x))$. 
It follows from Theorem~\ref{ufd} that 
$\lnko(f(x),g(x))$ exists and it is unique up to a scalar multiple.
\begin{tetel} \label{euklideszi}  
Suppose that $f(x),\ g(x)\in \F[x]$ are polynomials, 
that $g(x)\neq 0$, and let $n$ be the maximum of
$\deg f$ and $\deg g$. Assume, further, that the number 
$k$ and the polynomial $f_k$ are defined by the procedure above. Then\\
(i) $\lnko(f(x),g(x))=f_k(x)$. \\
(ii) There are polynomials $F(x),\ G(x)$ with degree at most $n$ such that
\begin{equation}
\label{eukl-eq}
f_k(x)=F(x)f(x)+G(x)g(x)\koz .
\end{equation}
(iii) With a given input $f,\ g$, the polynomials $F(x),\ G(x),\ f_k(x)$ 
can be computed using $O(n^3)$ field operations in $\F$.
\end{tetel}
\begin{biz} (i) Going backwards in the Euclidean algorithm, it 
is easy to see that the polynomial 
$f_k$ divides each of the $f_i$, and so it divides both $f$ and $g$.
The same way, if a polynomial $h(x)$ divides
$f$ and $g$, then it divides $f_i$, for all $i$, and, in particular, it
divides $f_k$. Thus $\lnko(f(x),g(x))=f_k(x)$.

(ii) The claim is obvious if $f=0$, and so we may assume without loss of
generality that $f\neq 0$. 
Starting at the beginning of the 
Euclidean sequence, it is easy to see that there are polynomials
$F_i(x),\ G_i(x)\in \F[x]$ such that
\begin{equation} \label{kombinacio} 
F_i(x)f(x)+G_i(x)g(x)=f_i(x) \koz .
\end{equation}
We observe that (\ref{kombinacio}) also holds if we substitute $F_i(x)$ 
by its remainder $F_i^*(x)$ after dividing by $g$
and substitute  $G_i(x)$ by
its remainder $G_i^*(x)$
after dividing by $f$.
In order to see this, we compute  
$$F_i^*(x)f(x)+G^*_i(x)g(x)\equiv f_i(x)\mypmod{f(x)g(x)} \koz , $$
and notice that the degree of the polynomials on both sides of this congruence
is smaller than
$(\fok f)(\fok g)$. This gives
$$F_i^*(x)f(x)+G^*_i(x)g(x) = f_i(x) \koz .$$


(iii) Once we determined the polynomials $f_{i-1}$, $f_i$, 
$F_i^*$ and $G^*_i$, the polynomials $f_{i+1}$,  
$F_{i+1}^*$ and  $G_{i+1}^*$ can be obtained using 
$O(n^2)$ field operations in $\F$.
Initially we have  $F_1^*=1$ and $G_2^*=-q_1$. As $k\leq n+1$,
the claim follows.
\end{biz}



\textit{Remark.} Traditionally, the Euclidean algorithm is only used to
compute the greatest common divisor. 
The version that also computes the polynomials
$F(x)$ and $G(x)$ in (\ref{eukl-eq}) is usually called the 
extended Euclidean algorithm.\index{Euclidean algorithm!extended}
In Chapter~\ref{chapter:compalgebra}
the reader can find a discussion of the Euclidean algorithm for polynomials. 
It is relatively easy to see that
the polynomials $f_k(x)$, $F(x)$, and $G(x)$ in
(\ref{eukl-eq}) can, in fact, be computed
using $O(n^2)$ field operations.
The cost of the asymptotically best method is ${\widetilde O}(n)$. 

\inddef{polynomial!derived}
The derivative of  a polynomial is often useful when investigating
multiple factors.
The \ki{derivative} of the polynomial 
$$f(x)=a_0+a_1x+a_2x^2+ \cdots +a_nx^n \in \F [x] $$
is the polynomial
$$ f'(x)=a_1+2a_2x+ \cdots +na_nx^{n-1}\koz. $$ 
It follows immediately from the definition that the map $f(x)\mapsto f'(x)$
is an $\F$-linear mapping\index{linear mapping} $\F[x]\rightarrow \F[x]$.
Further, for $f(x),\ g(x)\in \F[x]$ and $a\in \F$,   the equations
$(f(x)+g(x))'=f'(x)+g'(x)$ and $(af(x))'=af'(x)$ hold.
The derivative of a product can be computed using the 
\ki{Leibniz rule:}\inddef{Leibniz rule}\nevindex{Leibniz, Gottfried Wilhelm
(1646--1716)}  for all $f(x),\ g\ (x)\in \F[x]$ we have
$(f(x)g(x))'=f'(x)g(x)+f(x)g'(x).$ 
As the derivation is a linear map, 
in order to show that the Leibniz rule is valid, it is enough to verify it for
polynomials of the form
$f(x)=x^i$ and $g(x)=x^j$. It is easy to see that, for such polynomials, the
Leibniz rule is valid.


The derivative $f'(x)$ is sensitive to multiple factors in the irreducible
factorisation of $f(x)$.

\begin{lemma} \label{többes}
Let $\F$ be an arbitrary field, and assume that
$f(x)\in \F[x]$ and
$f(x)=u^k(x)v(x)$ where
$u(x),\ v(x)\in \F[x]$. Then $u^{k-1}(x)$ divides the derivative $f'(x)$ of the polynomial $f(x)$.
\end{lemma}
\begin{biz}
Using induction on $k$  and the Leibniz rule, 
we find $(u^k(x))'=ku^{k-1}(x)u'(x)$.
Thus, applying the Leibniz rule again, 
$f'(x)=u^{k-1}(x)(ku'(x)v(x)+u^k(x)v'(x))$. Hence
$u^{k-1}(x)\mid f'(x)$. 
\end{biz}



In many cases the converse of the last lemma also holds.

\begin{lemma}
\label{egyszeres}
Let  $\F$ be an arbitrary field, 
and assume that $f(x)\in \F[x]$ and
$f(x)=u(x)v(x)$ where the polynomials $u(x)$ and $v(x)$ are relatively prime.
Suppose further that $u'(x)\neq 0$ 
(for instance $\F$ has characteristic $0$ and $u(x)$ 
is non-constant). Then the derivative 
$f'(x)$ is not divisible by $u(x)$.
\end{lemma}
\begin{biz}
By the Leibniz rule,
$f'(x)=u(x)v'(x)+u'(x)v(x)\equiv u'(x)v(x) \mypmod{u(x)}$. Since 
$\deg u'(x)$ is smaller than $\deg u(x)$, 
we obtain that 
$u'(x)$ is not divisible by $u(x)$, and neither is the product 
 $u'(x)v(x)$, as 
$u(x)$ and $v(x)$ are relatively prime.
\end{biz}


\subsubsection{The Chinese remainder theorem for polynomials.} 
\inddef{Chinese
remainder theorem!for polynomials}

Using the following theorem, the ring $\F[x]/(f)$ can be assembled from
rings of the form $\F[x]/(g)$ where $g\mid f$.   
\begin{tetel}{(Chinese remainder theorem for polynomials)}\label{chinese}
Let $f_1,\ldots , f_k\in \F[x]$ pairwise relatively prime 
polynomials\index{relatively prime!polynomials} with positive degree
and set $f=f_1\cdots f_k$. Then the rings $\F[x]/(f)$
and $\F[x]/(f_1)\oplus\cdots \oplus \F[x]/(f_k)$ 
are isomorphic. 
The mapping realizing the isomorphism is
$$ \phi : [g]_f\mapsto ([g]_{f_1},\ldots , [g]_{f_k}), ~~~g\in \F[x] \koz . $$
\end{tetel}
\begin{biz}
First we note that the map $\phi$ is well-defined.
If $h\in [g]_f$, then $h=g+f^*f$, which implies that 
$h$ and $g$ give the same remainder after division by the polynomial
$f_i$,
that is, $[h]_{f_i}=[g]_{f_i}$. 

The mapping $\phi$ is clearly a ring homomorphism, \index{homomorphism}
and it is also a linear mapping between two
vector spaces over $\F$. 
The mapping $\phi$ is one-to-one; for, if 
$\phi([g])=\phi([h])$, 
then  $\phi([g-h])=(0,\ldots, 0)$, that is, $f_i\mid g-h$ ($1\leq i\leq k$), 
which gives $f\mid g-h$ and $[g]=[h]$.

The dimensions of the vector spaces $\F[x]/(f)$
and $\F[x]/(f_1)\oplus\cdots \oplus \F[x]/(f_k)$ coincide: 
indeed, both spaces  have dimension $\fok f$. Lemma~\ref{linearis} implies that
$\phi$ is an isomorphism between vector spaces.
It only remains to show that
$\phi^{-1}$ preserves the multiplication; this, however, is left to the reader.
\end{biz}

\vspace{-2mm}
\begin{gyak}
\ujgyak\label{fldquo-irred-ex}
Let $f\in \F[x]$ be polynomial.
Show that the residue class ring $\F[x]/(f)$ has no zero divisors if and only
if $f$ is irreducible.
\ujgyak
Let $R$ be a commutative ring with an identity.
A subset $I\subseteq R$ is said to be an \ki{ideal,}\inddef{ideal} if $I$
is an additive subgroup,\gyakindex{subgroup!additive} and 
$a\in I$, $b\in R$ imply $ab\in I$.
Show that $R$ is a field\gyakindex{field} if and only if 
its ideals are exactly $\{0\}$ and $R.$ 
\ujgyak 
Let $a_1,\ldots , a_k\in R.$ 
Let $(a_1,\ldots ,a_k)$ denote the smallest ideal in 
$R$ that contains the elements $a_i$. Show that
$(a_1,\ldots ,a_k)$ always exists, and it consists of the elements
of the form
$b_1a_1+b_2a_2+\cdots+b_ka_k $ where $b_1,\ldots, b_k\in R.$
\ujgyak 
A commutative ring $R$ with an identity and without zero divisors is said to be 
a \ki{principal ideal domain}\inddef{principal ideal domain} 
if, for each ideal $I$ of $R$, 
there is an element 
$a\in I$ such that (using the notation of the previous exercise)
$I=(a)$. Show that $\Z$ and $\F[x]$ where $\F$ is a field, are  principal ideal
domains. 
\ujgyak 
Suppose that $S$ is a commutative ring with an identity, that $I$ an ideal in $S$, 
and that
$a,\ b\in S$. Define a relation on $S$ as follows: 
$a\equiv b \mypmod{I}$ if and only if
$a-b\in I$. Verify the following: \\
\textit{a.)} The relation $\equiv$ is an equivalence relation on $S$. \\
\textit{b.)} Let $[a]_I$ denote the 
equivalence class containing an element $a$, and let $S/I$ denote the set of
equivalence classes.
Set $[a]_I+[b]_I:=[a+b]_I$, and 
$[a]_I[b]_I:=[ab]_I$. Show that, with respect to these operations, 
$S/I$ is a commutative ring with an identity.
\textit{Hint.} Follow the argument in the proof of Theorem~\ref{maradekosztalygyuru}.
\ujgyak\label{eukl-feladat} 
Let $\F$  be a field and let  $f(x),\ g(x)\in \F[x]$ such that
$\gcd(f(x),g(x))=1$. Show that
there exists a polynomial $h(x)\in\F[x]$ such that
$h(x)g(x)\equiv 1\mypmod{f(x)}.$ 
\textit{Hint.} Use the Euclidean algorithm.
\end{gyak}

\vspace{-2.5mm}
\section{Finite fields\label{sec:algebra2}}
\vspace{-0.5mm}
Finite fields, that is, fields with a finite number of elements,
\inddef{field!finite}
play an important r\^ole in mathematics and in several of its application areas, 
for instance, in computing.
They are also fundamental  in many important constructions.
In this section we summarise the most important results in the theory of 
finite fields, putting an emphasis on the problem of their construction.

In this section $p$ denotes a prime number, and $q$ denotes a power of $p$ 
with a positive integer exponent.
   
\begin{tetel} \label{primhatvany}
Suppose that $\F$ is a finite field. Then there is a prime number $p$ such that the prime field of 
$\F$ \index{prime field} 
is isomorphic to $\F_p$ (the field of residue classes modulo $p$). 
Further, 
the field $\F$ is a finite dimensional vector space\index{vector space} 
over $\F_p$, and the number of its elements is a power of $p$. In fact, if
$\dim_{\F_p}\F=d$, then
$|\F|=p^d$.
\end{tetel}
\begin{biz}
The characteristic of $\F$ must be a prime, say $p$,\index{characteristic}
as a field with characteristic zero must have infinitely many elements.
Thus the prime field $P$ of $\F$ is isomorphic to 
$\F_p$. Since $P$ is a subfield, the field $\F$ 
is a vector space over  $P$. Let
$\alpha_1, \ldots , \alpha_d $ be a basis
\index{basis!of a vector space} 
of $\F$ over $P$. 
Then each $\alpha\in \F$ 
can be written uniquely
in the form $\sum_{j=1}^d a_i\alpha_i$ where $a_i\in P$. Hence
$|\F|=p^d$. 
\end{biz}



In a field $\F$, the set of non-zero elements
(the multiplicative group\index{group!multiplicative} of $\F$) 
is denoted by $\F^*$. From Theorem~\ref{ciklikus} we immediately obtain the following result.


\begin{tetel} \label{primitiv}
If $\F$ is a finite field, then its multiplicative 
group $\F^*$ is cyclic\index{group!cyclic}. 
\end{tetel}

A generator of the group $\F^*$ is said to be a
\ki{primitive\inddef{primitive element} element.} 
If $|\F|=q$ and $\alpha$ is a primitive element of 
$\F$, then the elements of $\F$ are
$0, \alpha, \alpha^2, \ldots, \alpha^{q-1}=1$.

\begin{kov} \label{primitive-minimal}
Suppose that $\F$ is a finite field with
order $p^d$ and let $\alpha$ be a primitive element of $\F$.
Let $g\in \F_p[x]$ be a minimal polynomial of 
$\alpha$\index{minimal polynomial} 
over $\F_p$. Then
$g$ is irreducible in  $\F_p[x]$, the degree of $g$ is $d$, and $\F$ 
is isomorphic to the field  $\F_p[x]/(g)$.
\end{kov}
\begin{biz} Since the element $\alpha$ is primitive in $\F$, we have
$\F=\F_p(\alpha)$. The rest of the lemma follows from
Lemma~\ref{minimalpolinom} and from Theorem~\ref{egyszeru-bovites}.
\end{biz}

\begin{tetel} \label{Fermat} 
Let  $\F$ be a finite field with order $q$. Then \\
(i) {\rm (Fermat's little theorem)} 
\inddef{Fermat's theorem!little}\nevindex{Fermat, Pierre, de (1601--1655)}
 If $\beta \in \F^*$, then $\beta^{q-1}=1$. \\
(ii) If $\beta \in \F$, then $\beta^q=\beta$. 
\end{tetel}
\begin{biz}
(i) Suppose that $\alpha\in \F^*$ is a primitive element. 
Then we may choose an integer $i$ such that
$\beta=\alpha^i$. Therefore 
$$ \beta^{q-1}=(\alpha^i)^{q-1}=(\alpha^{q-1})^i=1^i=1\koz. $$

(ii) 
Clearly, if $\beta=0$ then this claim is true, while, for $\beta\neq 0$, 
the claim follows from part~(i).
\end{biz}
\begin{tetel}
\label{fermat-decomp-thm}
Let $\F$ be a field with $q$ elements. Then
$$x^q-x=\prod_{\alpha\in \F}(x-\alpha) \koz.$$
\end{tetel}
\begin{biz} By Theorem~\ref{Fermat} and  Lemma~\ref{gyokszam},
the product on the right-hand side is a divisor of the polynomial
$x^q-x\in \F[x]$. 
Now the assertion follows, as the degrees and the leading coefficients of 
the two polynomials in the equation coincide.
\end{biz}
\begin{kov}
Arbitrary two finite fields with the same number of elements are isomorphic.
\index{isomorphism}
\end{kov}
\begin{biz}
Suppose that $q=p^d$, and that both $\K$ and $\mathbb{L}$ are
fields with $q$ elements. Let $\beta$ be a primitive element 
in $\mathbb{L}$.
Then Corollary~\ref{primitive-minimal} implies that
a minimal polynomial $g(x)\in \F_p[x]$ of $\beta$ over
$\F_p$\index{minimal polynomial} is irreducible 
(in $\F_p[x]$) 
with degree $d$. Further, $\mathbb{L}\cong \F_p[x]/(g(x))$. 
By Lemma~\ref{minimalpolinom} and Theorem~\ref{Fermat}, 
the minimal polynomial $g$ 
is a divisor of the polynomial $x^q-x$.
Applying Theorem~\ref{fermat-decomp-thm} to $\K$, we find
that the polynomial $x^q-x$, and also its divisor $g(x)$, 
can be factored as a product of linear terms in 
$\K[x]$, and so $g(x)$ has at least one root
$\alpha$ in $\K$.
As $g(x)$ is irreducible in $\F_p[x]$,
it must be a minimal polynomial of 
$\alpha$ (see Corollary~\ref{min-kov}), and so
$\F_p(\alpha)$ is isomorphic to the field
$\F_p[x]/(g(x))$. Comparing the number of elements
in $\F_p(\alpha)$ and in $\K$, we find that
$\F_p(\alpha)=\K$, and further, that $\K$ and $\mathbb{L}$ are isomorphic.
\end{biz}



In the sequel, we let $\F_q$ denote the field with $q$ elements, provided it exists.
In order to prove the existence of such a field for each prime-power $q$, 
the following two facts will be useful.

\begin{lemma}
If $p$ is a prime number and $j$ is an integer such that 
$0<j<p$, then
$p\mid \choose{p}{j}$. 
\end{lemma}
\begin{biz} On the one hand, the number $\choose{p}{j}$ is an integer. 
On the other hand,
$\choose{p}{j}= p(p-1) \cdots (p-j+1)/j!$ is a fraction such that,
for $0<j<p$, its numerator is divisible by $p$, but its denominator is not.
\end{biz}

\begin{lemma} \label{Frobenius}
Let $R$ be a commutative ring\index{ring} and let $p$ be a prime 
such that $pr=0$ for all
$r\in R$. Then the map $\Phi_p:R\rightarrow R$ mapping $r\mapsto r^p$ 
is a ring homomorphism\index{homomorphism}.
\end{lemma}
\begin{biz} Suppose that $r,\ s\in R$. Clearly,
$$ \Phi_p(rs)=(rs)^p=r^ps^p=\Phi_p(r)\Phi_p(s) \koz . $$
By the previous lemma,
$$ \Phi_p(r+s)=(r+s)^p=\sum _{j=0}^p \choose{p}{j}r^{p-j}s^j=r^p+s^p=
\Phi_p(r)+\Phi_p(s) \koz . $$
We obtain in the same way that $\Phi_p(r-s)=\Phi_p(r)-\Phi_p(s)$.
\end{biz}



The homomorphism $\Phi_p$ in the previous lemma is called the 
\ki{Frobenius endomorphism.} \index{endomorphism!Frobenius}
\nevindex{Frobenius, Ferdinand Georg (1849--1917)}

\begin{tetel}
\label{fermat-factors-thm}
Assume that the polynomial $g(x)\in \F_q[x]$ is irreducible, 
and, for a positive integer $d$,
it is a divisor of the polynomial $x^{q^d}-x$.
Then the degree of $g(x)$ divides $d$.
\end{tetel}
\begin{biz}
Let $n$ be the degree of $g(x)$, and suppose, by contradiction, that
$d=tn+s$ where $0<s<n$. The assumption that $g(x)\mid x^{q^d}-x$ can be rephrased 
as $x^{q^d}\equiv x\mypmod{g(x)}$. However, this means that, for an arbitrary
polynomial $u(x)=\sum_{i=0}^N u_ix^i\in\F_q[x]$, we have
$$u(x)^{q^d}=\sum_{i=0}^Nu_i^{q^d}x^{iq^d}
=\sum_{i=0}^Nu_i(x^{q^d})^i\equiv
\sum_{i=0}^Nu_ix^i=u(x)\mypmod{g(x)} \koz .
$$
Note that we applied Lemma~\ref{Frobenius} to the ring 
 $R=\F_q[x]/(g(x))$, and Theorem~\ref{Fermat} to $\F_q$.
The residue class ring $\F_q[x]/(g(x))$ is isomorphic to the 
field $\F_{q^n}$, which has $q^n$ elements. Let $u(x)\in\F_q[x]$ be a polynomial
for which $u(x)\mypmod{g(x)}$ is a primitive element in the field $\F_{q^n}$. 
That is, $u(x)^{q^n-1}\equiv 1\mypmod{g(x)}$, but
$u(x)^j\not\equiv 1\mypmod{g(x)}$ for $j=1,\ldots,q^n-2$.
Therefore,
$$
u(x)\equiv u(x)^{q^d}=u(x)^{q^{tn+s}}=
(u(x)^{q^{nt}})^{q^s}\equiv u(x)^{q^s}\mypmod{g(x)} \koz ,
$$ 
and so
$u(x)(u(x)^{q^s-1}-1)\equiv 0\mypmod{g(x)}$. Since the residue class ring
$\F_q[x]/(g(x))$ is a field, 
$u(x)\not\equiv 0\mypmod{g(x)}$, but we must have
$u(x)^{q^s-1}\equiv 1\mypmod{g(x)}$. As $0\leq q^s-1<q^n-1$, 
this contradicts to the primitivity of $u(x)\mypmod{g(x)}$.
\end{biz}
\begin{tetel}
For an arbitrary prime $p$ and positive integer $d$,
there exists a field with $p^d$ elements.
\end{tetel}\label{fieldexist}
\begin{biz}
We use induction on $d$. The claim clearly holds if $d=1$.
Now let $d>1$ and let $r$ be a prime divisor of
$d$. By the induction hypothesis,
there is a field with $q=p^{(d/r)}$ elements.
By Theorem~\ref{fermat-factors-thm}, each of the irreducible factors, in $\F_q[x]$,  of the 
the polynomial $f(x)=x^{q^r}-x$
has degree either~1 or~$r$.
Further, 
$f'(x)=(x^{q^r}-x)'=-1$, and so, by Lemma~\ref{többes},  $f(x)$ is square-free.
Over $\F_q$, the number of linear factors of $f(x)$ is at most $q$, 
and so is the degree of their product.
Hence there exist at least 
$(q^r-q)/r \geq 1$ 
polynomials with degree $r$ that are irreducible in $\F_q[x]$.
Let $g(x)$ be such a polynomial. Then
the field $\F_q[x]/(g(x))$ is isomorphic to the field with  
$q^r=p^d$ elements.
\end{biz}

\begin{kov} \label{irred-letezik}
For each positive integer $d$, there is an irreducible polynomial
$f\in\F_p[x]$\index{polynomial!irreducible}  with degree
$d$.
\end{kov}
\begin{biz} Take a minimal polynomial over $\F_p$ 
of a primitive element in 
$\F_{p^d}$.
\end{biz}



A little bit later, in Theorem~\ref{veletlen-irred}, 
we will prove a stronger statement: 
a random polynomial in $\F_p[x]$ with degree $d$ is irreducible with high probability.


\subsubsection{Subfields of finite fields.}
The following theorem describes all subfields of a finite field.
\index{subfield} 
\begin{tetel}\label{resztest} 
The field $\F=\F_{p^n}$ contains a subfield isomorphic to
$\F_{p^k}$, if and only if $k\mid n$. In this case, 
there is exactly one subfield in $\F$ that is isomorphic to 
$\F_{p^k}$.
\end{tetel}
\begin{biz} 
The condition that  $k\mid n$ is necessary, since the larger field is a vector space over the smaller field, \index{vector space} 
and so $p^n=(p^k)^l$ must hold with a suitable integer $l$. 

Conversely, 
suppose that $k\mid n$, and let $f\in \F_p[x]$ be an irreducible
polynomial with degree $k$. Such a polynomial exists by
Corollary~\ref{irred-letezik}. 
Let $q=p^k$. Applying Theorem~\ref{Fermat}, 
we obtain, in $\F_p[x]/(f)$,  that
$x^q\equiv x \mypmod{f}$, which yields
$x^{p^n}=x^{q^l}\equiv x \mypmod{f}$. Thus $f$ must be a divisor of 
the polynomial $x^{p^n}-x$.
Using Theorem~\ref{fermat-decomp-thm}, we find that
$f$ has a root $\alpha$ in $\F$. Now we may prove in the usual way that
the subfield $\F_p(\alpha)$ is isomorphic to $\F_{p^k}$. 

The last assertion is valid, as the elements of 
$\F_q$ are exactly the roots of $x^q-x$ (Theorem~\ref{fermat-decomp-thm}), 
and this polynomial can have, in an arbitrary field, at most 
$q$ roots\index{root!of a polynomial}.
\end{biz}



\subsubsection{The structure of irreducible polynomials.} 
Next we prove an important property of the irreducible polynomials over
finite fields.\index{polynomial!irreducible}

\begin{tetel} \label{irred-szerk}
Assume that $\F_q\subseteq \F $ are finite fields, and let $\alpha\in \F$.
Let  $f\in \F_q[x]$ be the minimal polynomial of  $\alpha$  over $\F_q$ 
with leading coefficient~$1$,
and suppose that
$\fok f=d$.  Then
$$ f(x)=(x-\alpha)(x-\alpha^q)\cdots (x-\alpha^{q^{d-1}}) \koz . $$
Moreover, the elements $\alpha,\alpha^q,\ldots, \alpha^{q^{d-1}}$ are pairwise distinct.
\end{tetel}
\begin{biz} 
Let $f(x)=a_0+a_1x+\cdots +x^d$. If $\beta\in \F$ with
$f(\beta)=0$, then, using Lemma~\ref{Frobenius} and Theorem~\ref{Fermat},
we obtain
$$ 0=f(\beta)^q=(a_0+a_1\beta+\cdots +\beta^d)^q=a_0^q+a_1^q\beta^q +\cdots
+\beta^{dq}=a_0 +a_1\beta^q +\cdots +\beta^{qd}=f(\beta^q) \koz. $$
Thus $\beta^q$ is also a root of  $f$. 

As $\alpha$ is a root of $f$, the argument in the previous paragraph shows
that so are the elements
 $\alpha,\alpha^q,\ldots, \alpha^{q^{d-1}}$. Hence it suffices to show, that they are pairwise distinct. 
Suppose, by contradiction, that
$\alpha^{q^i}=\alpha^{q^j}$ and  that $0\leq i<j<d$. Let
$\beta=\alpha^{q^i}$ and let $l=j-i$. 
By assumption, $\beta=\beta^{q^l}$,
 which, by Lemma~\ref{minimalpolinom}, means that $f(x)\mid x^{q^l}-x$.
From Theorem~\ref{fermat-factors-thm}, we obtain, in this case, that
$d\mid l$, which is a contradiction, as 
$l<d$.
\end{biz}



This theorem shows that a polynomial $f$ 
which is irreducible over a finite field cannot have multiple roots.
Further, all the roots of $f$ can be obtained 
from a single root taking $q$-th powers repeatedly. 



\subsubsection{Automorphisms.}
In this section we characterise certain automorphisms of finite fields.
\begin{defi}
Suppose that $\F_q \subseteq \F$ are finite fields.
The map $\Psi: \F \rightarrow \F $ is an
\ki{$\F_q$-automorphism\inddef{automorphism}} of the field $\F$,
if it is an isomorphism between rings,\index{isomorphism}
and $\Psi(a)=a$ holds for all $a\in \F_q$.
\end{defi}

Recall that the map $\Phi=\Phi_q: \F \rightarrow \F $ is defined as follows: 
$\Phi(\alpha)=\alpha^q$ where $\alpha\in \F$.
\begin{tetel} The set of $\F_q$-automorphisms of the
field $\F=\F_{q^d}$ 
is formed by the maps $\Phi, \Phi^2,\ldots ,\Phi^d=id$.
\end{tetel}
\begin{biz}
By Lemma~\ref{Frobenius},
the map $\Phi:\F\rightarrow \F$ is a ring homomorphism.
The map $\Phi$ is obviously one-to-one, and hence it is also an isomorphism.
It follows from Theorem~\ref{Fermat}, that $\Phi$ leaves the elements
$\F_q$ fixed. 
Thus the maps $\Phi^j$ are $\F_q$-automorphisms of
$\F$.

Suppose that $f(x)=a_0+a_1x+\cdots +x^d\in \F_q[x]$, and $\beta\in \F$ with
$f(\beta)=0$, and that 
$\Psi$ is an $\F_q$-automorphism of $\F$. 
We claim that
$\Psi(\beta)$ is a root\index{root!of a polynomial} of $f$. Indeed,
$$ 0=\Psi(f(\beta))=\Psi(a_0)+\Psi(a_1)\Psi(\beta)+\cdots +\Psi(\beta)^d=
f(\Psi(\beta)) \koz . $$


Let $\beta$ be a primitive element of $\F$
\index{primitive element}
and assume now that $f\in \F_q[x]$ is a minimal polynomial of  $\beta$.
By the observation above and by Theorem~\ref{irred-szerk}, 
$\Psi(\beta)=\beta^{q^j}$,  with some $0\leq j<d$, 
that is,
$\Psi(\beta)=\Phi^j(\beta)$. Hence the images of a generating element of $\F$ 
under the automorphisms $\Psi$ and $\Phi^j$ coincide,
which gives $\Psi=\Phi^j.$
\end{biz}

\subsubsection{The construction of finite fields.\index{field!finite}}
Let $q=p^n$. By Theorem~\ref{maradekosztalygyuru} and Corollary~\ref{irred-letezik}, the field $\F_q$ can be written in the form $\F[x]/(f)$, 
where $f\in\F [x]$
is an irreducible polynomial with degree  $n$\index{polynomial!irreducible}. 
In  practical 
applications of field theory, for example 
in computer science, this is the most 
common method of constructing a finite field.
Using, for instance, the polynomial $f(x)=x^3+x+1$ in 
Example~\ref{Szamolasmaradekosztalygyuruben}, 
we may construct the field $\F_8$.
The following theorem shows that we have a good chance
of obtaining an irreducible polynomial by a random selection.
\begin{tetel} \label{veletlen-irred}
Let $f(x)\in \F_q[x]$ be a uniformly distributed random polynomial with 
degree $k>1$ and leading coefficient~$1$\index{random!polynomial}.
(Being uniformly distributed means that the probability of choosing $f$ is $1/q^k$.)
Then  $f$ is irreducible over $\F_q$ 
with probability at least $1/k-1/q^{k/2}$.
\index{polynomial!irreducible}
\end{tetel}
\begin{biz} First we estimate the number of
elements $\alpha\in \F_{q^k}$ for which
$\F_q(\alpha)=\F_{q^k}$. We claim that the number of such elements is at least
\vspace{-1mm}
$$ |\F_{q^k}|-\sum_{r\mid k}|\F_{q^{k/r}}| \koz , $$
where the summation runs for the distinct prime divisors $r$ of $k$. 
Indeed, if
$\alpha$ does not generate, over $\F_q$, the field $\F_{q^k}$, then it is 
contained in a maximal subfield of $\F_{q^k}$, and 
these maximal subfields are,
by Theorem~\ref{resztest}, 
exactly the fields of the form $\F_{q^{k/r}}$. The number of distinct prime divisors of $k$ are at most
$\lg k$, and so the number of such elements 
$\alpha$ is at least $q^k-(\lg k)q^{k/2}$. 
The minimal polynomials with leading coefficients~1 over $\F_q$ of such 
elements $\alpha $
\index{minimal polynomial} have degree $k$ and they are irreducible.
Such a polynomial is a minimal polynomial of exactly $k$ elements $\alpha$
(Theorem~\ref{irred-szerk}). Hence the number of distinct irreducible 
polynomials with degree $k$ and leading coefficient~1 in $\F_q[x]$ is at least
\vspace{-1mm}
$$ \frac{q^k}{k}-\frac {(\lg k)q^{k/2}}{k}\geq
\frac{q^k}{k}-q^{k/2} \koz , $$
\vspace{-1mm}
from which the claim follows.
\end{biz}



If, having $\F_q$, we would like to construct one of its extensions 
$\F_{q^k}$, then it is worth selecting a \ki{random} polynomial
$$ f(x)=a_0+a_1x+\cdots + a_{k-1}x^{k-1}+x^k\in \F_q[x]\koz. $$
In other words, we select uniformly distributed random coefficients 
$a_0,\ldots ,a_{k-1}\in\F_q$ 
independently. 
The polynomial so obtained is irreducible with a high probability
(in fact, with probability at least
$1/k-\epsilon$ if $q^k$ is large).
\index{polynomial!irreducible}
 Further, in this case, we also have
$\F_q[x]/(f)\cong \F_{q^k}$. 
We expect that we will have to select about $k$ polynomials before
we find an irreducible one.

We have seen in Theorem~\ref{fieldexist} that
field extensions \index{field extension} can be obtained using 
irreducible polynomials\index{polynomial!irreducible}. 
It is often useful if these polynomials have some further nice properties. 
The following lemma claims the existence of such polynomials.
\begin{lemma}\label{moreprob}
Let  $r$ be a prime. In a finite 
field $\F_q$ there exists an element which is not an $r$-th power 
if and only if
$q\equiv 1 \mypmod r$.
If $b\in \F_q$ is such an element, then the polynomial
$x^r-b$ \index{polynomial!irreducible} 
is irreducible in $\F_q[x]$, 
and so $\F_q[x]/(x^r-b)$ is a field with $q^r$ elements.
\end{lemma}
\begin{biz}
Suppose first that $r\nmid q-1$ and let $s$ be a positive integer
such that $sr\equiv 1 \mypmod{q-1}$.
If $b\in\F_q$ such that $b\neq 0$, then
$(b^s)^r=b^{sr}=bb^{sr-1}=b$, while if
$b=0$, then $b=0^r$. Hence, in this case, each of the elements of 
$\F_q$ is an $r$-th power.


Next we assume that $r\mid q-1$, and we let $a$ be a primitive element
in $\F_q$. Then, in $\F_q$,
the $r$-th powers are exactly the following $1+({q-1})/{r}$ elements:
$0, (a^r)^0,(a^r)^1,\ldots,(a^r)^{({q-1})/{r}-1}.$
Suppose now that $r^s\mid q-1$, but $r^{s+1}\nmid q-1$. 
Then the order of an element $b\in \F_q\setminus\{0\}$ is divisible by 
$r^s$ if and only if $b$ is not an 
$r$-th power. Let $b$ be such an element,
and let $g(x)\in\F_q[x]$
be an irreducible factor of the polynomial $x^r-b$.
Suppose that the degree of $g(x)$ is $d$; clearly, $d\leq r$.
Then $\K=\F_q[x]/(g(x))$ is a field with $q^d$ elements and, in $\K$, 
the equation $[x]^r=b$ holds.
Therefore the order of $[x]$ is divisible by $r^{s+1}$.
Consequently, $r^{s+1}\mid q^d-1$.
As $q-1$ is not divisible by $r^{s+1}$, we have
$r\mid (q^d-1)/(q-1)=1+q+\cdots+q^{d-1}$.
In other words $1+q+\ldots+q^{d-1}\equiv 0\mypmod{r}.$
On the other hand, as $q\equiv 1\mypmod{r}$,
we find $1+q+\cdots+q^{d-1}\equiv d\mypmod{r}$,
and hence $d\equiv 0\mypmod{r}$, which, since
$0<d\leq r$, can only happen
if $d=r$.
\end{biz}


In certain cases, we can use the previous lemma to boost the probability
of finding an irreducible polynomial.

\begin{allit} Let $r$ be a prime such that
$r\mid q-1$. Then, for a random  element $b\in\F_q^*$, the polynomial 
$x^r-b$ is irreducible in $\F_q[x]$ with probability at least
$1 - 1/r$.
\end{allit}
\begin{biz}
Under the conditions, the $r$-th powers in $\F_q^*$ constitute
the cyclic subgroup with order $(q-1)/r$.
Thus a random element $b\in\F_q^*$ is an $r$-th power with
probability $1/r$, and hence  the assertion follows from Lemma~\ref{moreprob}.
\end{biz}



\textit{Remark.} 
Assume that $r\mid (q-1)$,  and, if  $r=2$, then  assume also that 
$4\mid (q-1)$. In this case there is an element $b$ in $\F_q$ that is not 
an $r$-th power. We claim that that the residue class $[x]$ is not an $r$-th
power in $\F_q[x]/(x^r-b)\cong \F_q^r$.
Indeed, by the argument in the proof of Lemma~\ref{moreprob}, 
it suffices 
to show that
$r^2\nmid (q^r-1)/(q-1)$. 
By our assumptions, this is clear if
$r=2$. 
Now assume that $r>2$, and write $q\equiv 1+rt\mypmod {r^2}$.
Then, for all integers $i\geq 0$, we have $q^i\equiv 1+irt\mypmod {r^2}$, and so, by the assumptions,
$$
\frac{q^r-1}{q-1}=1+q+\cdots + q^{r-1}\equiv
r+\frac{r(r-1)}{2}rt\equiv r \mypmod{r^2}\koz.
$$ 



\begin{gyak}
\ujgyak 
Show that the polynomial $x^{q+1}-1$ can be factored as a product of linear
factors over the field $\F_{q^2}$.
\ujgyak
Show that the polynomial $f(x)=x^4+x+1$ is irreducible over $\F_2$, 
that is, $\F_2[x]/(f)\cong \F_{16}$. What is the order of the element 
 $[x]_f$ in the residue class ring?
Is it true that the element $[x]_f$ is primitive in
$\F_{16}$?
\ujgyak 
Determine the irreducible factors of $x^{31}-1$  
over the field $\F_2$.
\ujgyak 
Determine the subfields of $\F_{3^6}$.
\ujgyak 
Let $a$ and $b$ be positive integers. Show that there exists a finite field $\K$ 
containing
$\F_q$ such that $\F_{q^a}\subseteq \K$  
and $\F_{q^b}\subseteq \K$. What can we say about the number of elements in 
$\K$? 
\ujgyak 
Show that the number of irreducible polynomials\gyakindex{irreducible polynomial} with degree $k$ and leading coefficient~1
over $\F_q$ is at most $q^k/k$.
\ujgyak 
\textit{(a)} Let $\F$ be a field, 
let $V$ be an  $n$-dimensional vector space over $\F$, and let 
$A:V\rightarrow V$ be a linear transformation whose minimal polynomial 
coincides with its characteristic polynomial.\gyakindex{characteristic polynomial} 
Show that there exists a vector
$v\in V$ such that the images $v,Av,\ldots ,A^{n-1}v$ are linearly independent.\\
\textit{(b)} A set 
$S=\{ \alpha, \alpha^q, \ldots , \alpha^{q^{d-1}}\}$ 
 is said to be a \ki{normal basis}\inddef{normal basis} 
of $\F_{q^d}$ over  $\F_q$, if $\alpha \in \F_{q^d}$
and $S$ is a linearly independent set over $\F_q$. Show that
 $\F_{q^d}$ has a normal basis over  $\F_q$.
\textit{Hint.} Show that a minimal polynomial of the $\F_q$-linear map
 $\Phi: \F_{q^d}\rightarrow \F_{q^d}$ is
$x^d-1$, and use part~(a).
\end{gyak}


\section{Factoring  polynomials over finite fields}\label{sec:algebra3}\inddef{factorisation!of a polynomial} 

One of the problems that we often have to solve when performing 
symbolic computation is the \ki{factorisation} problem.
Factoring an algebraic expression means writing it as a product of simpler 
expressions.
Experience shows that this can be very 
helpful in the solution of a large variety of 
algebraic problems. In this section, we consider a
class of factorisation algorithms that can be used to factor 
polynomials in one variable over finite fields.

The input of the \ki{polynomial factorisation problem}
is a polynomial $f(x)\in \F_q[x]$.
Our aim is to compute a factorisation
\begin{equation} \label{felb}
f=f_1^{e_1}f_2^{e_2}\cdots f_s^{e_s}
\end{equation}
of $f$ where the polynomials $f_1, \ldots ,f_s $ are pairwise relatively prime and 
irreducible \index{irreducible polynomial|see{polynomial}}
over $\F_q$, and the exponents $e_i$ are positive integers.
By Theorem~\ref{ufd},
$f$ determines the polynomials $f_i$ and the exponents
$e_i$ essentially uniquely.


\begin{pelda} Let $p=23$ and
let  $$ f(x)=x^6-3x^5+8x^4-11x^3+8x^2-3x+1\koz .$$
Then it is easy to compute modulo 23 that
$$f(x)=(x^2-x+10)(x^2+5x+1)(x^2-7x+7) \koz.$$ 
None of the factors
$x^2-x+10$, $x^2+5x+1$, $x^2-7x+7$ has a root in
$\F_{23}$, and so
they are necessarily irreducible in $\F_{23}[x]$.
\end{pelda}

The factorisation algorithms are important computational tools,
and so they are implemented in most of the computer  algebra systems 
(Mathematica, Maple, etc). 
These algorithms are often used in the area of error-correcting codes and 
in cryptography. 

Our aim in this section 
is to present some of the basic ideas and building blocks that 
can be used to factor polynomials over finite fields.
We will place an emphasis on the existence of polynomial time algorithms.
The discussion of the currently best known 
methods is, however, outside the 
scope of this book.



\subsection{Square-free factorisation
\inddef{factorisation!of a polynomial!square-free}}\label{sff}
The factorisation problem in the previous section can efficiently be reduced 
to  the special case when the polynomial $f$ to be factored
is square-free;
\index{polynomial!square-free}\index{square-free polynomial|see{polynomial}}
that is, in~(\ref{felb}), $e_i=1$ for all $i$.
The basis of this reduction is Lemma~\ref{többes}
and the following simple result. Recall 
that the derivative of a polynomial $f(x)$  
\index{derivative!of a polynomial} 
is denoted by $f'(x)$.
\begin{lemma}
Let $f(x)\in \F_q[x]$ be a polynomial. If $f'(x)=0$,
then there exists a polynomial $g(x)\in\F_q[x]$ such that $f(x)=g(x)^p$.
\end{lemma}
\begin{biz}
Suppose that $f(x)=\sum_{i=0}^n a_ix^i$. Then
$f'(x)=\sum_{i=1}^n a_iix^{i-1}$. If the coefficient $a_ii$ 
is zero in $\F_q$ then  either $a_i=0$ or $p\mid i$.
Hence, if $f'(x)=0$ then $f(x)$ can be written as $f(x)=\sum_{j=0}^kb_jx^{pj}$.
Let $q=p^d$; then choosing $c_j=b_j^{p^{d-1}}$, we have
$c_j^p=b_j^{p^d}=b_j$, and so $f(x)=(\sum_{j=0}^kc_jx^j)^p$.
\end{biz}



If $f'(x)=0$, then, using the previous lemma,
a factorisation of $f(x)$ into square-free factors 
can be obtained from that of the 
polynomial
$g(x)$, which has smaller degree. 
On the other hand, if $f'(x)\neq 0$, then, by Lemma~\ref{többes},
the polynomial $f(x)/\lnko(f(x),f'(x))$ is already square-free
and we only have to factor
$\lnko(f(x),f'(x))$ into square-free factors.
The division of polynomials and computing the greatest common divisor
can be performed in polynomial time, by Theorem~\ref{euklideszi}.
In order to compute the polynomial 
$g(x)$, we need the solutions, in $\F_q$, of equations of the form $y^p=a$ with  $a\in \F_q$. If $q=p^s$, then
$y=a^{p^{s-1}}$ is a solution of such an equation, which, using 
\ki{fast exponentiation}\index{fast exponentiation}
(repeated squaring, see~33.6.1), can be obtained in polynomial time.

One of the two reduction steps can always be performed if $f$ is divisible by
a square of a polynomial with positive degree.


Usually  a polynomial can be written as a product of square-free factors in 
many different ways. 
For the sake of uniqueness, we define the \ki{square-free factorisation} of a 
polynomial $f\in\F[x]$ 
\inddef{factorisation!of a polynomial!square-free}
\index{square-free factorisation|see{factorisation}}
as the factorisation
$$f=f_1^{e_1}\cdots f_s^{e_s} \koz ,$$
where
$e_1<\cdots<e_s$ are integers, and the polynomials $f_i$ are 
relatively prime and square-free.
Hence we collect together 
the irreducible factors of $f$ with the same multiplicity.
The following algorithm computes
a square-free factorisation of $f$.
Besides the observations we made in this section, we also use
Lemma~\ref{egyszeres}. 
This lemma, combined with Lemma~\ref{többes}, guarantees that 
the product of 
the irreducible factors with multiplicity one of 
a polynomial $f$ over a finite field
is $f/\lnko(f,f').$


\begin{algN}{Square-Free-Factorisation($f$)}\inddef{\textsc{Square-Free-Factorisation}}
1 \'  $g\leftarrow f$\\
2 \'  $S\leftarrow\emptyset$ \\
3 \'  $m\leftarrow 1$\\
4 \'  $i\leftarrow 1$ \\
5 \'  \key{while} \= $\deg g\neq 0$ \\
6 \'              \> \key{do} \= \key{if} \= $g'=0$ \\
7 \'              \>          \>          \> \key{then} \= $g\leftarrow \sqrt[p]{g}$\\
8 \'              \>          \>          \>            \> $i\leftarrow i\cdot p$\\
9 \'              \>          \>          \> \key{else} \= $h\leftarrow g/\lnko(g,g')$\\
10 \'             \>          \>          \>            \> $g\leftarrow g/h$\\
11 \'             \>          \>          \>            \> \key{if} \= $\deg h\neq 0$ \\
12 \'             \>          \>          \>            \>          \> \key{then} $S\leftarrow S\cup(h,m)$\\	
13 \'             \>          \>          \>            \> $m\leftarrow m+i$\\
14 \' \key{return} $S$
\end{algN}

The degree of the polynomial $g$ decreases 
after each execution of the main loop, and the subroutines used in this algorithm 
run in polynomial time. Thus the method above can be performed in polynomial time.


\subsection{Distinct degree factorisation
\inddef{factorisation!of a polynomial!distinct degree}} 
\index{distinct degree factorisation|see{factorisation}}


Suppose that $f$ is a square-free polynomial. 
Now we factor $f$ as
\begin{equation} \label{kulfok}
f(x)=h_1(x)h_2(x)\cdots h_t(x)\koz,
\end{equation}
where, for $i=1,\ldots,t$, 
the polynomial $h_i(x)\in \F_q[x]$ is a product of irreducible polynomials 
with degree $i$. Though this step is not actually necessary for the solution of the 
factorisation problem, it is worth considering, as several of the 
known methods  can efficiently exploit the structure of the polynomials
$h_i$. 
The following fact serves as the starting point of the distinct degree factorisation.

\begin{tetel} 
\label{kulfok-tetel}
The polynomial $x^{q^d}-x$ is the product
of all the irreducible polynomials $f\in \F_q[x]$, each of which is taken with
multiplicity~$1$,
that have leading coefficient~$1$ and whose degree divides 
$d$.
\end{tetel}
\begin{biz}  As $(x^{q^d}-x)'=-1$, all 
the irreducible factors of this polynomial
occur with multiplicity one.
If $f\in \F_q[x]$ is irreducible and divides
$x^{q^d}-x$, then, 
by Theorem~\ref{fermat-factors-thm}, the degree of $f$ divides $d$.

Conversely, let  $f\in \F_q[x]$ be an irreducible polynomial with degree $k$ 
such that
$k\mid d$. Then, by Theorem~\ref{resztest}, $f$ has a root in
$\F_{q^d}$, which implies $f\mid x^{q^d}-x$.
\end{biz}



The theorem offers an efficient method for computing the polynomials 
$h_i(x)$. First we separate $h_1$ from $f$, and then, step by step, we separate
the product of the factors with higher degrees.


\begin{alg}{Distinct-Degree-Factorisation$(f)$\inddef{\textsc{Distinct-Degree-Factorisation}}}
1 \' $F\leftarrow f$\\
2 \' \key{for} \= $i\leftarrow 1$ \key{to} $\deg f$ \\
3 \'           \> \key{do} \= $h_i\leftarrow \lnko(F,x^{q^i}-x)$\\
4 \'           \>          \> $F\leftarrow F/h_i$\\
5 \' \key{return} $h_1,\ldots,h_{\deg f}$
\end{alg}



If, in this algorithm,
the polynomial $F(x)$ is constant, then we may stop, 
as the further steps will not give new factors.
As the polynomial $x^{q^i}-x$ may have large degree, computing 
$\lnko(F(x),x^{q^i}-x)$
must be performed with particular care. 
The important idea here is that the residue
$x^{q^i}\mypmod{F(x)}$ 
can be computed using fast exponentiation\index{fast exponentiation}.


The algorithm outlined above is suitable for testing whether a polynomial 
is irreducible,
\index{polynomial!irreducible}
which is one of the important problems that we encounter when constructing 
finite fields.
The algorithm presented here for distinct degree factorisation
can solve this problem efficiently.
For, it is obvious that a polynomial $f$ with degree $k$
is irreducible,\index{polynomial!irreducible}
if, in the factorisation~(\ref{kulfok}), we have $h_k(x)=f(x)$. 

The following algorithm for testing whether a polynomial is irreducible
is somewhat more efficient than the one sketched in the previous paragraph
and handles correctly also the inputs that are not square-free.

\begin{alg}{Irreducibility-Test$(f)$\inddef{\textsc{Irreducibility-Test}}}
1 \' $n\leftarrow \deg f$\\
2 \' \key{if} \= $x^{p^n}\not\equiv x\mypmod{f}$ \\
3 \'          \> \key{then} \key{return} "no"\\  
4 \' \key{for} \= the prime divisors $r$ of $n$  \\
5 \'           \> \key{do} \= \key{if} \= $x^{p^{n/r}}\equiv x\mypmod{f}$ \\
6 \'           \>          \>          \> \key{then} \key{return} "no"\\
7 \' \key{return} "yes"
\end{alg}

In lines~2 and~5, we check whether $n$ 
is the smallest among the positive integers $k$ for which
$f$ divides $x^{q^k}-x$. By Theorem~\ref{kulfok-tetel},
this is equivalent to the irreducibility of
$f$\index{polynomial!irreducible}.
If $f$ survives the test in line~2, then, by 
Theorem~\ref{kulfok-tetel}, 
we know that $f$ is square-free  and $k$ must divide 
$n$. Using at most $\lg n+1$ fast exponentiations
modulo $f$, we can thus decide if $f$ is irreducible. 


\begin{tetel} If the field $\F_q$ is given and $k>1$ is an integer, 
then the field $\F_{q^k}$ can be constructed using a randomised 
Las Vegas algorithm which runs 
in time polynomial in
$\lg q$ and $k$.
\end{tetel}
\begin{biz}  The algorithm is the following.

\begin{alg}{Finite-Field-Construction($q^k$)\inddef{\textsc{Finite-Field-Construction}}}
1 \' \key{for} \= $i\leftarrow 0$ to $k-1$\\
2 \'           \> \key{do} $a_i\leftarrow$ a random element (uniformly distributed) of $\F_q$ \\
3 \' $f\leftarrow x^k+\sum_{i=0}^{k-1}a_ix^i$\\
4 \' \key{if} \= {\sc{Irreducibility-Test}}$(f)=$\ "yes" \\
5 \'          \>  \key{then} \= \key{return} $\F_q[x]/(f)$\\
6 \'          \>  \key{else} \> \key{return} "fail"
\end{alg}
In lines~1--3, we choose a uniformly distributed 
random polynomial with leading coefficient~$1$ and degree~$k$. 
Then, in line~4, we efficiently check if $f(x)$ is irreducible.
By Theorem~\ref{veletlen-irred}, the polynomial $f$ is irreducible with a 
reasonably high probability.
\end{biz}

\vspace{-4mm} 
\subsection{The Cantor-Zassenhaus algorithm}
\nevindex{Cantor, David G.}\nevindex{Zassenhaus, Hans Julius (1912--1991)}
\inddef{Cantor-Zassenhaus algorithm}\label{cz}

In this section we consider the special case of the factorisation problem in which
$q$ is odd and the polynomial $f(x)\in \F_q[x]$ is of the form
\begin{equation} \label{felb1}
f=f_1f_2\cdots f_s \koz,
\end{equation}
where the $f_i$ are pairwise relatively prime irreducible polynomials in
\index{polynomial!irreducible}
$\F_q[x]$ with the same degree $d$, and we also assume that $s\geq 2$. 
Our motivation for investigating this special case is that a 
square-free distinct degree factorisation reduces the general factorisation 
problem to such a simpler problem.
If $q$ is even, then Berlekamp's\nevindex{Berlekamp, Elwyn Ralph} 
method, presented in Subsection~\ref{ber}, gives a deterministic polynomial time 
solution. There is a variation of the method discussed in 
the present section that works also for even $q$; see~Problem~\ref{CZalg2-fld}

\begin{lemma}
\label{cz-split-lm}
Suppose that $q$ is odd. Then there are
$(q^2-1)/2$ pairs  $(c_1,c_2)\in \F_q\times \F_q$ such that
exactly one of $c_1^{(q-1)/2}$ and $c_2^{(q-1)/2}$ is equal to~$1$.
\end{lemma}
\begin{biz}
Suppose that $a$ is a primitive element in
$\F_q$; that is, $a^{q-1}=1$, but
$a^k\neq 1$ for $0<k<q-1$.
Then
$\F_q\setminus\{0\}=\{a^s|s=0,\ldots,q-2\}$,
and further, as ${\left(a^{(q-1)/2}\right)}^2=1$, but
$a^{(q-1)/2}\neq 1$, we obtain that
$a^{(q-1)/2}=-1$.
Therefore $a^{s(q-1)/2}=(-1)^s$, and so
half of the element $c\in\F_q\setminus\{0\}$ give
$c^{(q-1)/2}=1$, while the other half give
$c^{(q-1)/2}=-1$. If $c=0$ then clearly
$c^{(q-1)/2}=0$. Thus there are $((q-1)/2)((q+1)/2)$
pairs $(c_1,c_2)$ such that
$c_1^{(q-1)/2}=1$, but
$c_2^{(q-1)/2}\neq 1$, and, obviously, we have the same number of pairs for which
the converse is valid.
Thus the number of pairs that satisfy the condition is
$(q-1)(q+1)/2 = (q^2-1)/2.$ 
\end{biz}
\begin{tetel}
\label{cz-split-thm}
Suppose that $q$ is odd and the polynomial
$f(x)\in \F_q[x]$ is of the form (\ref{felb1}) and has degree $n$.
Choose a uniformly distributed random polynomial 
$u(x)\in\F_q[x]$ with degree less than $n$. (That is,
choose pairwise independent, uniformly distributed scalars
$u_0,\ldots,u_{n-1}$, and consider the polynomial $u(x)=\sum_{i=0}^{n-1}u_ix^i$.) Then,  with probability at least 
$(q^{2d}-1)/(2q^{2d}) \geq 4/9$, the greatest common divisor
$$\lnko(u(x)^{\frac{q^d-1}{2}}-1,f(x))$$ 
is a proper divisor of $f(x)$.
\end{tetel}
\begin{biz}
The element $u(x)\mypmod{f_i(x)}$ corresponds to
an element of the residue class field $\F[x]/(f_i(x))\cong \F_{q^d}$.
By the Chinese remainder theorem
\index{Chinese remainder theorem!for polynomials}
(Theorem~\ref{chinese}), choosing the polynomial $u(x)$ uniformly implies
that the residues of 
$u(x)$ modulo the factors $f_i(x)$ are independent and uniformly 
distributed random polynomials. 
By Lemma~\ref{cz-split-lm}, the probability 
that exactly one of the residues of the polynomial 
$u(x)^{(q^d-1)/2}-1$ modulo $f_1(x)$ and $f_2(x)$ is zero is precisely
$(q^{2d}-1)/(2q^{2d})$. In this case the greatest common divisor in the theorem
is indeed a divisor of $f$. For, if
$u(x)^{(q^d-1)/2}-1\equiv 0\mypmod{f_1(x)}$, but
this congruence is not valid modulo $f_2(x)$, then 
the polynomial $u(x)^{(q^d-1)/2}-1$ is divisible by the factor
$f_1(x)$, but not divisible by $f_2(x)$, and so
its greatest common divisor with $f(x)$ is a proper divisor of $f(x)$.
The function 
$$
\frac{q^{2d}-1}{2q^{2d}}= \frac{1}{2}-\frac{1}{2q^{2d}}
$$ 
is strictly increasing in $q^d$, and it takes its smallest possible value
if $q^d$ is the smallest odd prime-power, namely~3.
The minimum is, thus, $1/2 - 1/18 = 4/9$.
\end{biz}

The previous theorem suggests the following randomised Las Vegas polynomial time 
algorithm for factoring a polynomial of the form~(\ref{felb1}) to a product of two factors.

\begin{alg}{Cantor-Zassenhaus-Odd\inddef{\textsc{Cantor-Zassenhaus-Odd}}$(f,d)$}
1 \' $n\leftarrow\deg f$ \\
2 \' \key{for} \= $i\leftarrow 0$ to $n-1$\\
3 \'           \> \key{do} $u_i\leftarrow$ a random element (uniformly distributed) of $\F_q$\\
4 \' $u\leftarrow \sum_{i=0}^{n-1}u_ix^i$\\
5 \' $g\leftarrow \lnko(u^{(q^d-1)/2}-1,f)$\\
6 \' \key{if} \= $0<\deg g<\deg f$ \\
7 \'          \>  \key{then} \= \key{return}$(g,f/g)$\\
8 \'          \>  \key{else} \> \key{return} "fail"
\end{alg}

If one of the polynomials in the output is 
not irreducible, then, as it is of the form~(\ref{felb1}),
it can be fed, as input, back into the algorithm.
This way we obtain a polynomial time randomised algorithm for factoring $f$.


In the computation of the greatest common divisor, the
residue $u(x)^{(q^d-1)/2}\mypmod{f(x)}$ should be computed using fast exponentiation.
\index{fast exponentiation}

Now we can conclude that the general factorisation problem~(\ref{felb}) 
\index{factorisation!of a polynomial} over a field
with odd order can be solved using a randomised polynomial time 
algorithm.

\subsection{Berlekamp's algorithm}\label{ber}
Here we will describe an
algorithm \nevindex{Berlekamp, Elwyn Ralph} that reduces the problem of factoring
polynomials to the 
problem of searching through the underlying field or its prime field.
We assume that
\begin{equation*}
f(x)=f_1^{e_1}(x)\cdots f_s^{e_s}(x)\koz , 
\end{equation*}
where the $f_i(x)$ 
are pairwise non-associate, irreducible \index{polynomial!irreducible} 
polynomials in $\F_q[x]$, and also that
$\deg f(x)=n$. The Chinese remainder theorem (Theorem~\ref{chinese})
gives an isomorphism 
between the rings $\F_q[x]/(f)$ and
$$\F_q[x]/(f_1^{e_1})\oplus\cdots \oplus \F_q[x]/(f_s^{e_s})\koz. $$
The isomorphism is given by the following map:
\begin{equation*}
[u(x)]_f\leftrightarrow 
([u(x)]_{f_1^{e_1}},\ldots,
[u(x)]_{f_s^{e_s}})\koz , 
\end{equation*}
where $u(x)\in \F_q[x]$. 
 
The most important technical tools in Berlekamp's algorithm are
the $p$-th and $q$-th power maps in the residue class ring $\F_q[x]/(f(x))$.
Taking $p$-th and $q$-th powers on both sides of the isomorphism above 
given by the Chinese remainder theorem, we obtain the following maps:
\begin{eqnarray}
\label{chinese-ppower-eq}
[u(x)]^p 
& \leftrightarrow &
([u(x)^p]_{f_1^{e_1}},\ldots,[u(x)^p]_{f_s^{e_s}})\koz , 
\end{eqnarray}
\begin{eqnarray}
\label{chinese-qpower-eq}
[u(x)]^q 
& \leftrightarrow &
([u(x)^q]_{f_1^{e_1}},\ldots,[u(x)^q]_{f_s^{e_s}})\koz . 
\end{eqnarray}

The \ki{Berlekamp subalgebra}\inddef{Berlekamp subalgebra} $B_f$
of the polynomial $f=f(x)$ 
is the subring of the residue class ring $\F_q[x]/(f)$ 
consisting of the fixed points of the 
$q$-th power map.
 Further, 
the \ki{absolute Berlekamp subalgebra}\inddef{Berlekamp subalgebra!absolute}  $A_f$ of $f$ consists of the fixed points  of the $p$-th power map.
In symbols,
\begin{eqnarray*}
B_f  = 
\{[u(x)]_f\in\F_q[x]/(f): \; [u(x)^q]_f=[u(x)]_f \}\koz ,
\end{eqnarray*}
\begin{eqnarray*}
 A_f  = 
 \{[u(x)]_f\in\F_q[x]/(f): \; [u(x)^p]_f=[u(x)]_f \}\koz .
\end{eqnarray*}

It is easy to see that $A_f\subseteq B_f$. 
The term subalgebra is used here,\index{subalgebra} 
because both types of Berlekamp subalgebras are subrings \index{subring}
in the residue class ring $\F_q[x]/(f(x))$ (that is they are closed under
addition and multiplication modulo
$f(x)$), and, in addition, $B_f$ 
is also linear subspace over $\F_q$,\index{subspace}
that is, it is closed under multiplication by the elements of 
$\F_q$. The absolute Berlekamp subalgebra 
$A_f$ is only closed under multiplication by the elements of the prime field $\F_p$.

The Berlekamp subalgebra $B_f$ is a subspace, as the map
$u\mapsto u^q-u\mypmod{f(x)}$ is an $\F_q$-linear 
map of $\F_q[x]/g(x)$ into itself, by Lemma~\ref{Frobenius}
and Theorem~\ref{Fermat}.
Hence a basis of $B_f$  can be computed as a solution of 
a homogeneous system of linear equations over $\F_q$, as follows.

For all $i\in\{0,\ldots,n-1\}$, compute the polynomial
$h_i(x)$ with degree at most $n-1$ that satisfies
$x^{iq}-x^i\equiv h_i(x)\mypmod{f(x)}$. 
For each $i$, such a polynomial
$h_i$ can be determined by fast exponentiation
using $O(\lg q)$ multiplications of polynomials and 
divisions with remainder.
Set
$h_i(x)=\sum_{j=0}^nh_{ij}x^j$.
The class $[u]_f$ of a polynomial $u(x)=\sum_{i=0}^{n-1} u_ix^i$ with degree less than
$n$ lies in the Berlekamp subalgebra if and only if
\begin{equation*}
\sum_{i=0}^{n-1} u_ih_i(x)=0 \koz ,
\end{equation*} 
which, considering the coefficient of
 $x^j$ for $j=0,\ldots, n-1$, 
leads to the following system of $n$ 
homogeneous linear equations  in $n$ variables:
\begin{equation*}
\sum_{i=0}^{n-1}h_{ij}u_i=0,\;\;(j=0,\ldots,n-1) \koz .
\end{equation*}


Similarly, computing a basis of the absolute Berlekamp subalgebra over $\F_p$
can be carried out by solving a system of $nd$ homogeneous linear equations 
in $nd$ variables over the prime field $\F_p$,
as follows.
We represent the elements of  $\F_q$ in the usual way, 
namely using polynomials with degree less than $d$
in $\F_p[y]$. We perform the operations modulo
$g(y)$,
where $g(y)\in\F_p[y]$ is an irreducible polynomial  with degree $d$
over the prime field $\F_p$. Then
the polynomial $u[x]\in \F_q[x]$ of degree less than $n$ can be written
in the form
$$
\sum_{i=0}^{n-1}\sum_{j=0}^{d-1}u_{ij}y^jx^i \koz,
$$ 
where $u_{ij}\in \F_p$.
Let, for all $i\in\{0,\ldots,n-1\}$ and for all
$j\in\{0,\ldots,d-1\}$, 
$h_{ij}(x)\in\F_q[x]$ be the unique polynomial with degree at most 
$(n-1)$ for which
$h_{ij}(x)\equiv (y^jx^i)^p-y^jx^i\mypmod{f(x)}$.
The polynomial $h_{ij}(x)$ is of the form
$\sum_{k=0}^{n-1}\sum_{l=0}^{d-1}h_{ij}^{kl}y^lx^k$. 
The criterion 
for being a member of the absolute Berlekamp subalgebra of $[u]$ with
$u[x]=\sum_{i=0}^{n-1}\sum_{j=0}^{d-1}u_{ij}y^jx^i$ 
is
\begin{equation*}
\sum_{i=0}^{n-1}\sum_{j=0}^{d-1}u_{ij}h_{ij}(x)=0\koz ,
\end{equation*}
which, considering the coefficients of the monomials 
$y^lx^k$, is equivalent to the following system of equations:
\begin{equation*}
\sum_{i=0}^{n-1}\sum_{j=0}^{d-1}h_{ij}^{kl}u_{ij}=0
\;\;
(k=0,\ldots,n-1,\,l=0,\ldots,d-1)\koz .
\end{equation*}
This is indeed a homogeneous system of linear equations
in the variables $u_{ij}$.
Systems of linear equations over fields can be solved in polynomial time
(see Section~31.4), the operations in the ring $\F_q[x]/(f(x))$  
can be performed in polynomial time,
and  the fast exponentiation also runs in polynomial time.
Thus the following theorem is valid.


\begin{tetel} Let $f\in \F_q[x]$. Then it is possible to compute
the Berlekamp subalgebras 
$B_f\leq \F_q[x]/(f(x))$ and   $A_f \leq \F_q[x]/(f(x))$, in the sense that
an $\F_q$-basis of $B_f$ and $\F_p$-basis of $A_f$ can be obtained,
using polynomial time deterministic algorithms.
\end{tetel}
  

By~(\ref{chinese-ppower-eq}) and~(\ref{chinese-qpower-eq}),
\begin{equation}
\label{chinese-berlekamp-eq}
B_f= 
\{[u(x)]_f\in\F_q[x]/(f): \;[u^q(x)]_{f_i^{e_i}} =[u(x)]_{f_i^{e_i}}
\,~ (i=1,\ldots,s)
\}
\end{equation}
and
\begin{equation}
\label{chinese-absberlekamp-eq}
A_f= 
\{[u(x)]_f\in\F_q[x]/(f): \;[u^p(x)]_{f_i^{e_i}} =[u(x)]_{f_i^{e_i}}
\, ~ (i=1,\ldots,s)
\}\koz .
\end{equation}


The following theorem shows that the elements of the Berlekamp subalgebra
can be characterised by their Chinese remainders.

\begin{tetel}
\begin{equation*}
B_f=
\{
[u(x)]_f \in\F_q[x]/(f):~ 
\exists
c_i\in \F_q{ \rm ~such\ that~ }
[u(x)]_{f_i^{e_i}}=[c_i]_{f_i^{e_i}} 
\;(i=1,\ldots,s)
\}
\end{equation*}
and
\begin{equation*}
A_f=
\{
[u(x)]_f \in\F_q[x]/(f):~
\exists
c_i\in \F_p { \rm ~such\ that~ }
[u(x)]_{f_i^{e_i}}=[c_i]_{f_i^{e_i}}
\;(i=1,\ldots,s)
\}\koz .
\end{equation*}
\end{tetel}

\begin{biz}
Using the Chinese remainder theorem,
\index{Chinese remainder theorem!for polynomials}
and equations~(\ref{chinese-berlekamp-eq}), 
(\ref{chinese-absberlekamp-eq}), we are only required to prove that
\begin{equation*}
u^q(x)\equiv u(x)\mypmod {g^e(x)}
\Longleftrightarrow
\exists c\in \F_q\mbox{~such that~}
u(x)\equiv c\mypmod {g^e(x)}\koz ,
\end{equation*}
and
\begin{equation*}
u^p(x)\equiv u(x)\mypmod {g^e(x)}
\Longleftrightarrow
\exists c\in \F_p\mbox{~such that~}
u(x)\equiv c\mypmod {g^e(x)}\koz 
\end{equation*}
where $g(x)\in \F_q[x]$ is an irreducible polynomial, 
$u(x)\in \F_q[x]$ is an arbitrary polynomial and
$e$ is a positive integer.
In both of the cases, the direction $\Leftarrow$ is a simple consequence of
Theorem~\ref{Fermat}.
As $\F_p=\{a\in\F_q\ |\ a^p=a\}$,
the implication
$\Rightarrow$ concerning the  absolute Berlekamp subalgebra 
follows from that concerning 
the Berlekamp subalgebra, and so it suffices to consider the latter.

The residue class ring  $\F_q[x]/(g(x))$ is a field, 
and so the polynomial $x^q-x$ has at most 
$q$ roots in $\F_q[x]/(g(x))$.
However, we already obtain 
$q$ distinct roots from Theorem~\ref{Fermat}, 
namely the elements of $\F_q$ 
(the constant polynomials modulo $g(x)$). Thus
\begin{equation*}
u^q(x)\equiv u(x)\mypmod{g(x)}
\Longleftrightarrow
\exists c\in \F_q\mbox{~such that~}
u(x)\equiv c\mypmod{g(x)}\koz .
\end{equation*}
Hence, if
$u^q(x)\equiv u(x)\mypmod{g^e(x)}$,
then
$u(x)$ is of the form $u(x)=c+h(x)g(x)$ where
$h(x)\in \F_q[x]$.  Let $N$ be an arbitrary positive integer.
Then
\begin{equation*}
u(x)\equiv u^q(x)\equiv u^{q^N}(x)
\equiv (c+h(x)g(x))^{q^N}
\equiv c+h(x)^{q^N}g(x)^{q^N}
\equiv c
\mypmod{g^{q^N}(x)}\koz .
\end{equation*} 
If we choose $N$ large enough so that $q^N\geq e$ holds, then, 
by the congruence above,
$u(x)\equiv c\mypmod{g^e(x)}$ also holds.
\end{biz}



An element $[u(x)]_f$ of  $B_f$ or $A_f$ is said to be
\ki{non-trivial} if there is no element
$c\in\F_q$   such that $u(x)\equiv c\mypmod{f(x)}$.
By the previous theorem and the Chinese remainder theorem,
this holds if and only if
there are $i,\ j$ such that
$c_i\neq c_j$.  Clearly a necessary condition is that
$s>1$, that is, $f(x)$ 
must have at least two irreducible factors.

\begin{lemma}
Let $[u(x)]_f$ be a non-trivial element of the Berlekamp subalgebra 
$B_f$. \index{Berlekamp subalgebra} 
Then there is an element $c\in\F_q$ such that the polynomial
$\lnko(u(x)-c,f(x))$ is a proper divisor of $f(x)$.
If $[u(x)]_f\in A_f$, then there exists such an element $c$
in the prime field $\F_p$. \index{prime field}
\end{lemma}

\begin{biz}
Let $i$ and $j$ be integers
such that  $c_i\neq c_j\in\F_q$,
$u(x)\equiv c_i\mypmod{f_i^{e_i}(x)}$, and
$u(x)\equiv c_j\mypmod{f_j^{e_j}(x)}$. Then, choosing
$c=c_i$, the polynomial $u(x)-c$
is divisible by $f_i^{e_i}(x)$, but not divisible by
$f_j^{e_j}(x)$. If, in addition, $u(x)\in A_f$, then
also $c=c_i\in\F_p$.
\end{biz}



Assume that we have a basis of $A_f$ at hand. 
At most one of the basis elements can be trivial, 
as a trivial element is a scalar multiple of~1.
If $f(x)$ is not a power of an irreducible polynomial, 
then there will surely be a non-trivial basis element
$[u(x)]_f$, 
and so, using the idea in the previous lemma, 
$f(x)$ can be factored two factors.

\begin{tetel} \label{Berlekamp1}  A polynomial $f(x)\in \F_q[x]$ can be
factored with a deterministic algorithm whose running time 
is polynomial in
$p$, $\fok f$, and $\lg q$.
\end{tetel}
\begin{biz} It suffices to show that $f$ can be factored to 
\textit{two} factors within the given time bound. 
The method can then be repeated.


\begin{alg}{Berlekamp-Deterministic$(f)$\inddef{\textsc{Berlekamp-Deterministic}}}
1 \' $S\leftarrow$ a basis of $A_f$\\
2 \' \key{if} \= $|S|>1$ \\
3 \'          \> \key{then} \= $u\leftarrow$ a non-trivial element of $S$ \\
4 \'          \>            \> \key{for} \= $c\in \F_p$ \\
5 \'          \>            \>           \> \key{do} \= $g\leftarrow \lnko(u-c,f)$\\
6 \'          \>            \>           \>          \> \key{if} \= $0<\deg g<\deg f$ \\
7 \'          \>            \>           \>          \>          \> \key{then} \key{return} $(g,f/g)$\\
8 \'          \> \key{else} \key{return} "a power of an irreducible" 
\end{alg}

In the first stage, in line~1, we determine a basis of the absolute Berlekamp subalgebra.
The cost of this is polynomial in $\fok f$ and 
$\lg q$. In the second stage (lines~2--8), 
after taking a non-trivial basis element $[u(x)]_f$,
we compute the greatest common divisors
$\lnko(u(x)-c,f(x))$  for all $c\in\F_p$.
The cost of this is polynomial in
 $p$ and $\fok f$. 

If there is no non-trivial basis-element,
then
$A_f$ is 1-dimensional and $f$ is the $e_1$-th power of the irreducible
polynomial $f_1$ where $f_1$ and $e_1$ can, for instance, be determined using
the ideas presented in Section~\ref{sff}.
\end{biz}



The time bound in the previous theorem
is  \textit{not polynomial} in the input size, as it contains
$p$ instead of $\lg p$. However, if $p$ is small compared to the other 
parameters
(for instance in coding theory we often have $p=2$),
then the running time of the algorithm will be polynomial in the input size.

\begin{kov}  Suppose that $p$ can be bounded by a polynomial function of 
 $\fok f$ and $\lg q$. Then the irreducible factorisation 
of $f$ can be obtained in polynomial time.
\end{kov}

The previous two results
are due to
E. R. Berlekamp.\nevindex{Berlekamp, Elwyn Ralph} 
The most important open problem in the area discussed here 
is the existence of
a deterministic polynomial time method for factoring polynomials.
The question is mostly of theoretical interest,
since 
the randomised polynomial time methods, 
such as the a Cantor
\nevindex{Cantor, David G.}-Zassenhaus
\nevindex{Zassenhaus, Hans Julius (1912--1991)} algorithm, are very efficient in practice. 




\subsubsection{Berlekamp's randomised algorithm}
We can obtain a good randomised algorithm using  Berlekamp\nevindex{Berlekamp, Elwyn Ralph}
subalgebras.\index{Berlekamp subalgebra} 
Suppose  that $q$ is odd, and, as before, $f\in \F_q[x]$ is the polynomial
to be factored.



Let $[u(x)]_f$ be a random element in the Berlekamp subalgebra 
$B_f$. An argument, similar to the one in the analysis of the 
Cantor\nevindex{Cantor, David G.}-Zassenhaus\nevindex{Zassenhaus, 
Hans Julius (1912--1991)} algorithm
shows 
that, provided $f(x)$ has at least two irreducible factors, 
the greatest common divisor
$\lnko(u(x)^{(q-1)/2}-1,f(x))$ is a proper divisor of $f(x)$ with
probability at least~4/9.
Now we present a variation of this idea that uses less random bits:
instead of choosing a random element from
$B_f$, we only choose a random element from $\F_q$.

\begin{lemma}
\label{berlekamp-split-lm}
Suppose that $q$ is odd and
let $a_1$ and $a_2$ be two distinct elements of $\F_q$. 
Then there are at least
$(q-1)/2$ elements $b\in\F_q$ such that
exactly one of the elements $(a_1+b)^{(q-1)/2}$ 
and $(a_2+b)^{(q-1)/2}$
is~$1$.
\end{lemma}

\begin{biz}
Using the argument at the beginning of the proof of 
Lemma~\ref{cz-split-lm},
one can easily see that there are $(q-1)/2$ elements in the set 
$\F_q\setminus\{1\}$ whose
$(q-1)/2$-th power is $-1$.
It is also quite easy to check, 
for a given element $c\in\F_q \setminus \{1\}$, that there is a unique
$b\neq -a_2$ such that
$c=(a_1+b)/(a_2+b)$. 
Indeed, the required 
$b$ is the solution of a linear equation.

By the above, there are 
$(q-1)/2$ elements  $b\in \F_q \setminus \{-a_2\}$ such that
$$
\left(\frac{a_1+b}{a_2+b}\right)^{(q-1)/2}=-1\koz .
$$ 
For such a $b$,
one of the elements $(a_1+b)^{(q-1)/2}$ and
$(a_2+b)^{(q-1)/2}$ is equal to $1$ and the other is equal to $-1$.
\end{biz}
\begin{tetel}
\label{berlekamp-split-thm}
Suppose that $q$ is odd
and the polynomial $f(x)\in\F_q[x]$ has at least two irreducible
factors in $\F_q[x]$. Let $u(x)$ be a non-trivial element in the
Berlekamp subalgebra $B_f$.\index{Berlekamp subalgebra}
If we choose a uniformly distributed random element
$b\in \F_q$, then, with probability at least
$(q-1)/(2q) \geq 1/3$, 
the greatest common divisor 
$\lnko((u(x)+b)^{(q-1)/2}-1,f(x))$ 
is a proper divisor of the polynomial $f(x)$.
\end{tetel}
\begin{biz}
Let $f(x)=\prod_{i=1}^sf_i^{e_i}(x)$,
where the factors $f_i(x)$ are pairwise 
distinct irreducible polynomials. The element $[u(x)]_f$ 
is a non-trivial element of the Berlekamp subalgebra, 
and so there are  indices
$0<i,j\leq s$ and elements $c_i\neq c_j\in\F_q$ such that
$u(x)\equiv c_i\mypmod {f_i^{e_i}(x)}$ and 
$u(x)\equiv c_j\mypmod {f_j^{e_j}(x)}$.
Using  Lemma~\ref{berlekamp-split-lm} with
$a_1=c_i$ and $a_2=c_j$,
we find, 
for a random element $b\in \F_q$, that the probability 
that exactly one of the elements
$(c_i+b)^{(q-1)/2}-1$ and $(c_j+b)^{(q-1)/2}-1$ is zero is  at 
least $(q-1)/(2q)$.
If, for instance, 
$(c_i+b)^{(q-1)/2}-1=0,$ but
$(c_j+b)^{(q-1)/2}-1\neq 0$, then
$(u(x)+b)^{(q-1)/2}-1\equiv 0\mypmod{f_i^{e_i}(x)}$ 
but
$(u(x)+b)^{(q-1)/2}-1\neq 0\mypmod {f_j^{e_j}(x)}$, 
that is, the polynomial $(u(x)+b)^{(q-1)/2}-1$  is divisible by
${f_i^{e_i}(x)}$, but not divisible by $f_j^{e_j}(x)$.
Thus the greatest common divisor 
$\lnko(f(x), (u(x)+b)^{(q-1)/2}-1)$ is a proper divisor of $f$.  

The quantity $(q-1)/(2q) = 1/2 - 1/(2q)$ is a strictly increasing function
in $q$, and so it takes its smallest value 
for the smallest odd prime-power, namely 3.
The minimum is 1/3.
\end{biz}



The previous theorem gives   the following algorithm
for factoring a polynomial to two factors.

\begin{alg}{Berlekamp-Randomised$(f)$\inddef{\textsc{Berlekamp-Randomised}}}
1 \' $S\leftarrow$ a basis of  $B_f$\\
2 \' \key{if} \= $|S|>1$ \\
3 \'          \> \key{then} \= $u\leftarrow$  a non-trivial elements of $S$\\
4 \'          \>            \> $c\leftarrow$ a random element (uniformly distributed) of $\F_q$ \\
5 \'          \>            \> $g\leftarrow \lnko((u-c)^{(q-1)/2}-1,f)$\\
6 \'          \>            \> \key{if} \= $0<\deg g<\deg f$ \\
7 \'          \>            \>          \> \key{then} \= \key{return} $(g,f/g)$\\
8 \'          \>            \>          \> \key{else} \> \key{return} "fail"\\ 
9 \'         \> \key{else}  \>\key{return} "a power of an irreducible" 
\end{alg}


\begin{gyak}
\ujgyak 
Let $f(x)\in \F_p[x]$ be an irreducible polynomial, and 
let $\alpha$ be an element of the field $\F_p[x]/(f(x))$.
Give a polynomial time 
algorithm for computing $\alpha ^{-1}$.
\textit{Hint.} Use the result of Exercise~\ref{eukl-feladat}
\ujgyak 
Let $f(x)=x^7+x^6+x^5+x^4+x^3+x^2+x+1\in \F_2[x]$. Using the 
{\sc Distinct-Degree-Factorisation} algorithm,
\gyakindex{factorisation!of a polynomial!distinct degree} 
determine the factorisation~(\ref{kulfok}) of~$f$.
\ujgyak 
Follow the steps of the  Cantor-Zassenhaus algorithm to factor the polynomial
$x^2+2x+9\in \F_{11}[x]$.
\ujgyak 
Let $f(x)=x^2-3x+2\in \F_5[x]$. Show that
$\F_5[x]/(f(x))$ coincides with the absolute Berlekamp subalgebra of 
$f$, \gyakindex{Berlekamp subalgebra!absolute} that is,
$A_f=\F_5[x]/(f(x))$. 
\ujgyak 
Let $f(x)=x^3-x^2+x-1\in \F_7[x]$. Using Berlekamp's algorithm,
determine the irreducible factors of 
$f$: first find a non-trivial element in the Berlekamp subalgebra
$A_f$,\gyakindex{Berlekamp subalgebra!absolute} 
then use it to factor $f$. 
\end{gyak}


\vspace{-2mm}
\section{Lattice reduction\label{sec:algebra4}}
Our aim in the rest of this chapter is to present the 
Lenstra-Lenstra-Lov�sz algorithm for factoring polynomials with rational 
coefficients.\nevindex{Lenstra, Hendrik Willem, Jr.}\nevindex{Lenstra, Arjen Klaas}
\nevindex{Lov�sz, L�szl�} First we study a geometric problem, which 
is interesting also in its own right, namely finding short lattice vectors.
Finding a shortest non-zero lattice vector\index{lattice vector!shortest} 
\index{lattice vector} is hard:
by a result of Ajtai,\nevindex{Ajtai, Mikl�s} 
if this problem could be solved in polynomial time with a 
randomised algorithm, then so could all the problems in the complexity class
$NP$.\index{NP}
For a lattice with dimension $n$, 
the lattice reduction method presented in this chapter
\index{lattice reduction}
outputs, in polynomial time, a lattice vector whose length is not greater 
than $2^{(n-1)/4}$ times the length of a shortest non-zero lattice vector.
\newpage

  
\subsection{Lattices}
First, we recall a couple of concepts related to real vector spaces.
\index{vector space}
Let $\R^n$ denote the collection
of real vectors of length $n$. It is routine to check that 
$\R^n$ is a vector space over the field $\R$. 
The \ki{scalar product} of two vectors 
$u=(u_1,\ldots ,u_n)$ and $v=(v_1,\ldots ,v_n)$ in $\R^n$ is defined as 
the number
\index{scalar product} 
$(u,v)=u_1v_1+u_2v_2+\cdots +u_nv_n$. 
The quantity $|u|=\sqrt{(u,u)}$ 
is called the \ki{length} of the vector $u$. 
The vectors $u$ and $v$ are said to be 
\ki{orthogonal}\inddef{orthogonal vectors} 
if $(u,v)=0.$ A basis
$b_1, \ldots, b_n$ of the space $\R^n$  
is said to be orthonormal, \index{basis!orthonormal}
if, for all $i$,  $(b_i,b_i)=1$  and, for all $i$ and $j$ such that
$i\neq j$,  we have $(b_i,b_j)=0$.

The rank\index{rank!of a matrix} and the
determinant of a real matrix,\index{determinant} 
and definite matrices\index{matrix!definite} are discussed in Section~31.1.
\begin{defi}
A set $L\subseteq \R^n$ is said to be a 
\ki{lattice,}\inddef{lattice} if 
$L$ is a subgroup\index{subgroup} with respect to addition,
and $L$ is discrete,\index{discrete set} in the sense that
each bounded region of
$\R^n$ contains only finitely many points of
$L$.
The \ki{rank} of the lattice $L$ \inddef{rank!of a lattice} 
is the dimension of the subspace generated by $L$.
Clearly, the rank of $L$ 
coincides with the cardinality of a maximal linearly independent
subset of $L$. \index{linear independence} 
If $L$ has rank $n$, then $L$ is said to be a 
\ki{full} lattice\index{lattice!full}.
The elements of  $L$ are called
\ki{lattice vectors}\inddef{lattice vector} or 
\ki{lattice points.}\inddef{lattice point} 
\end{defi}
\begin{defi}
Let $b_1,\ldots,b_r$ be linearly independent 
elements of a lattice
$L\subseteq \R^n$. 
If all the elements of $L$ can be written as linear combinations
of the elements $b_1,\ldots,b_r$ with integer coefficients,
\index{linear combination}
then the collection $b_1,\ldots,b_r$ is said to be a
\ki{basis}\inddef{basis!of a lattice} of $L$.
\end{defi}
In this case, as the vectors $b_1,\ldots,b_r$ are linearly 
independent, all vectors of $\R^n$ can uniquely be written
as real linear combinations of $b_1,\ldots,b_r$.


By the following theorem,
the lattices are precisely those additive subgroups of $\R^n$ that
have bases.

\begin{tetel}
\label{lattice-basis-thm}
Let $b_1,\ldots,b_r$ be linearly independent vectors in
$\R^n$ and let $L$ be the set of integer linear combinations
of $b_1,\ldots,b_r$.
Then  $L$ is a lattice and the vectors
 $b_1,\ldots,b_r$ form a basis of $L$.
Conversely, if $L$ is a lattice in $\R^n$, then it has a basis.
\end{tetel}
\begin{biz}
Obviously, $L$ is a subgroup, that is, it is closed under addition
and subtraction.
In  order to show that it is discrete, let us assume 
that
$n=r$.  This assumption means no loss of generality, as 
the subspace spanned by $b_1,\ldots,b_r$ is isomorphic to 
$\R^r$. 
In this case,
$\phi:(\alpha_1,\ldots,\alpha_n)\mapsto 
\alpha_1b_1+\ldots+\alpha_n b_n$ 
is an invertible linear map of $\R^n$ onto itself. \index{linear mapping}
Consequently, both $\phi$ and $\phi^{-1}$ are continuous.
Hence the image of a discrete set under 
$\phi$ is also discrete.
As $L=\phi(\Z^n)$, it suffices to show that $\Z^n$
is discrete in $\R^n$. 
This, however, is obvious: if $K$ is a bounded region in
$\R^n$, then there is a positive integer $\rho$,
such that the absolute value of 
each of the coordinates
of the elements of $K$  is at most
$\rho$. Thus $\Z^n$ has at most 
$(2\lfloor\rho\rfloor+1)^n$ elements in $K$.

The second assertion is proved by induction on 
$n$.
If $L=\{0\}$, then we have nothing to prove. Otherwise, by discreteness,
there is a shortest non-zero vector, $b_1$ say, in $L$.
We claim that the vectors of 
$L$ that lie on the line $\{\lambda b_1\ |\ \lambda\in\R\}$ 
are exactly the integer multiples of  $b_1$.
Indeed, suppose that $\lambda$ is a real number and
consider the vector $\lambda b_1\in L$.
As usual,  $\{\lambda\}$ denotes the fractional part of $\lambda$.
Then $0\neq |\{\lambda\}b_1|<|b_1|$, yet
$\{\lambda\}b_1=\lambda b_1-[\lambda]b_1$,
that is $\{\lambda\}b_1$ is the difference of two 
vectors of $L$, and so is itself in $L$.
This, however, contradicts to the fact that 
$b_1$ was a shortest non-zero vector in $L$. 
Thus our claim holds.


The claim verified in the previous paragraph shows that the 
theorem is valid when $n=1$.
Let us, hence, assume that $n>1$. 
We may write an element of $\R^n$ as the sum of two vectors, 
one of them is parallel to $b_1$ and the other one is 
orthogonal to $b_1$:
$$v=v^* + \frac{(v,b_1)}{(b_1,b_1)} b_1 \koz .$$ 
Simple computation shows that
$(v^*,b_1)=0$, and the map $v\mapsto v^*$ is linear.
Let $L^*=\{v^*|v\in L\}$. We show that
 $L^*$ is a lattice in the subspace, or hyperplane, 
$H\cong \R^{n-1}$ formed by the 
vectors orthogonal to $b_1$.
The map
$v\mapsto v^*$ is linear, and so
$L^*$ is closed under addition and subtraction. 
In order to show that it is discrete, 
let $K$ be a bounded region in $H$. We are required to show that
only finitely many points of $L^*$ are in 
$K$. 
Let $v\in L$ be a vector such that $v^*\in K$. Let
$\lambda$ be the integer that is closest to the number 
 $(v,b_1)/(b_1,b_1)$
and let $v'=v-\lambda b_1$. Clearly,
 $v'\in L$ and $v'^*=v^*$. Further, we also have
that $|(v',b_1)/(b_1,b_1)| = |(v-\lambda b_1,b_1)/(b_1,b_1)| \leq 1/2$,
and so the vector $v'$ lies in the bounded region
$K\times \{\mu b_1:~ - 1/2 \leq \mu \leq 1/2 \}$.
However, there are only finitely many vectors 
$v'\in L$ in this latter region, 
and so $K$ also has only finitely many lattice vectors $v^*=v'^*\in L^*$. 

We have, thus, shown that 
$L^*$ is a lattice in $H$, and, 
by the induction hypothesis, it has a basis. Let 
$b_2,\ldots,b_r\in L$ be lattice vectors such that
the vectors $b_2^*,\ldots,b_r^*$ form a basis of the lattice $L^*$.
Then, for an arbitrary lattice vector $v\in L$, the vector $v^*$ can be written
in the form
$\sum_{i=2}^r\lambda_i b_i^*$ where the coefficients $\lambda_i$
are integers. Then
$v'=v-\sum_{i=2}^r\lambda_i b_i\in L$ and, 
as the map $v\mapsto v^*$ is linear,
we have $v'^*=0$. This, however, implies that $v'$ is a lattice vector
on the line $\lambda b_1$,
and so $v'=\lambda_1b_1$ with 
some integer $\lambda_1$. Therefore
$v=\sum_{i=1}^r\lambda_ib_i$, that is, 
$v$ is an integer linear combination 
of the vectors $b_1,\ldots,b_r$.
Thus the vectors $b_1,\ldots,b_r$ form a basis of $L$.
\end{biz}




A lattice $L$ is always full \index{lattice!full} 
in the linear subspace spanned by $L$.
\index{subspace} 
Thus, without loss of generality,  we will  consider only 
full lattices, and, in the sequel, by a lattice we will always mean a \textit{full lattice}
\index{lattice!full}. 



\begin{pelda} Two familiar lattices in $\R^2$: \\
1. The \ki{square
lattice} \index{square lattice} is the lattice
in $\R^2$ with basis  $b_1=(1,0),\ b_2=(0,1)$.\\
2. The \ki{triangular lattice}\index{triangular lattice} is the lattice with 
basis
$b_1=(1,0)$, $b_2=(1/2,(\sqrt 3)/2)$.
\end{pelda}

The following simple fact will often be used.

\begin{lemma}
Let $L$ be a lattice in $\R^n$, and let $b_1,\ldots,b_n$ be a basis of 
$L$.
If we reorder the basis vectors 
$b_1,\ldots,b_n$, or if we add to a basis vector 
an integer linear combination of the 
other basis vectors,
then the collection so obtained will also form a basis of $L$.
\end{lemma}
\begin{biz}
Straightforward.
\end{biz}



Let $b_1,\ldots,b_n$ be a basis in  $L$. The Gram matrix  of 
$b_1,\ldots,b_n$ \index{Gram matrix}\nevindex{Gram, Jorgen Pedersen (1850--1916)} 
is the matrix $B=(B_{ij})$ with entries $B_{ij}=(b_i,b_j)$.
The matrix  $B$ is positive definite, \index{matrix!positive definite}
since it is of the form $A^TA$ where $A$ is a full-rank matrix 
(see Theorem~31.6). Consequently, $\det B$\index{determinant} is a positive real number.

\begin{lemma}
Let $b_1,\ldots,b_n$ and $w_1,\ldots,w_n$ be
bases of a lattice $L$ and let $B$ and
$W$ be the matrices $B_{ij}=(b_i,b_j)$ and $W_{ij}=(w_i,w_j)$.
Then the determinants of  $B$ and $W$ coincide.
\end{lemma}  
\begin{biz}
For all $i=1,\ldots,n$, the vector $w_i$ is of the form
$w_i=\sum_{j=1}^n\alpha_{ij}b_j$ where
 the $\alpha_{ij}$ are integers.
Let $A$ be the matrix with entries $A_{ij}=\alpha_{ij}$.
Then, as
\begin{eqnarray*} 
(w_i,w_j) &=&
(\sum_{k=1}^n\alpha_{ik}b_k,\sum_{l=1}^n\alpha_{jl}b_l)
= 
\sum_{k=1}^n\alpha_{ik}\sum_{l=1}^n(b_k,b_l)\alpha_{jl} \koz ,
\end{eqnarray*}
we have $W=ABA^T$, and so $\det W=\det B(\det A)^2$. The number
$\det W/\det B=(\det A)^2$ is a non-negative integer, 
since the entries of $A$ are integers.
Swapping the two bases, 
the same argument shows 
that $\det B/\det W$ is also a non-negative integer.
This can only happen if 
$\det B=\det W$.
\end{biz}
\begin{defi}[The determinant of a lattice]
The  determinant 
of a lattice $L$ \inddef{determinant!of a lattice} 
is $\det L=\sqrt {\det B}$ where
 $B$ is the Gram matrix\index{Gram matrix} of a basis of $L$. \index{basis!of a lattice}
\end{defi}


By the previous lemma,
$\det L$ is independent of the choice of 
the basis.
The quantity $\det L$ has a geometric meaning, as 
$\det L$ is the volume\index{volume} of the solid body, the so-called parallelepiped,
formed by the vectors 
$\{\sum_{i=1}^n\alpha_{i}b_i:~0\leq \alpha_1,\ldots,\alpha_n\leq 1\}$.
\index{parallelepiped} 

\begin{megj} Assume that the coordinates of the vectors  $b_i$ in 
an orthonormal basis of $\R^n$
\index{basis!orthonormal} are
$\alpha_{i1},\ldots,\alpha_{in}$
($i=1,\ldots,n$). Then the Gram matrix $B$ of the vectors $b_1,\ldots,b_n$
is $B=AA^T$ where
$A$ is the matrix $A_{ij}=\alpha_{ij}$.
Consequently, if  $b_1,\ldots,b_n$ is a basis of a lattice 
$L$, then $\det L=|\det A|.$
\end{megj}

\begin{biz}
The assertion follows from 
the equations $(b_i,b_j)=\sum_{k=1}^n\alpha_{ik}\alpha_{jk}$.
\end{biz}

\subsection{Short lattice vectors}
We will need a fundamental result in convex geometry.
In order to prepare for this, we introduce some simple notation.
Let $H\subseteq \R^n$. The set $H$ is said to be
\ki{centrally symmetric,\index{centrally symmetric set}} if $v\in H$ implies $-v\in H$.
The set $H$ is \ki{convex,\index{convex set}} 
if $u,v\in H$ implies $\lambda u+(1-\lambda)v\in H$ for all
$0\leq \lambda \leq 1$.
    

\begin{tetel}[Minkowski's Convex Body Theorem]
\index{Minkowski's Convex Body Theorem}
\nevindex{Minkowski, Hermann (1864--1909)}
Let $L$ be a lattice in  $\R^n$ and let 
$K\subseteq\R^n$  be a centrally symmetric, bounded, closed, convex set.
Suppose that the volume of $K$ is at least
$2^n\det L$. Then $K\cap L\neq \{0\}$.
\end{tetel}

\begin{biz}
By the conditions, the volume of the set  $(1/2)K:=\{(1/2)v:~v\in K\}$  is
at least $\det L$.
Let $b_1,\ldots,b_n$ be a basis of the lattice $L$ and let
$P=
\{\sum_{i=1}^n\alpha_{i}b_i:~0\leq \alpha_1,\ldots,\alpha_n< 1\}$
be the corresponding half-open parallelepiped. 
Then each of the vectors in  $\R^n$ can be written uniquely
in the form $x+z$ where
$x\in L$ and $z\in P$. For an arbitrary lattice vector $x\in L$, we let
$$K_x= (1/2) K\cap (x+P)=
(1/2) K\cap \left \{x+z:~z\in P \right \} \koz .$$ 
As the sets
$(1/2) K$ and $P$ are bounded, so is the set
$$(1/2) K - P = \left \{u-v:~u\in (1/2) \cdot K,~v\in P \right \}.$$
As $L$ is discrete,  $L$ only has finitely many points in 
$(1/2) K - P$;
that is,
$K_x=\emptyset$, except for finitely many $x\in L$.
Hence $S=\{x\in L:~ K_x\neq \emptyset\}$ is a finite set, 
and, moreover, the set $(1/2)K$ is the disjoint union 
of the sets $K_x$ ($x\in S$).
Therefore, the total volume of these sets is at least
$\det L$. For a given $x\in S$, we set
$P_x=K_x-x=\{z\in P:~x+z\in (1/2) K\}.$ Consider the closure $\overline P$ and 
${\overline{P_x}}$ of the sets
 $P$ and
$P_x$, respectively:
$${\overline P}=
\left \{\sum_{i=1}^n\alpha_{i}b_i:~0\leq \alpha_1,\ldots,\alpha_n\leq 1 \right \}$$
and
${\overline{P_x}} = \left \{z\in {\overline{P}}:~x+z\in (1/2) K \right \}.$
The total volume of the 
closed sets ${\overline {P_x}}\subseteq {\overline P}$ 
is at least as large as the volume of the set
$\overline{P}$, and so these sets cannot be disjoint:
there are $x\neq y\in S$ and $z\in {\overline P}$ such that
$z\in {\overline {P_x}}\cap {\overline {P_y}}$,
that is,  $x+z\in (1/2) K$ and $y+z\in (1/2) K.$  
As $(1/2) \cdot K$ is centrally symmetric,
we find that $-y-z\in (1/2) \cdot K$. As $(1/2)K$  is convex,
we also have $(x-y)/2=((x+z)+(-y-z))/2 \in (1/2) K$.
Hence $x-y\in K$. On the other hand,
the difference $x-y$ of two lattice points lies in $L\setminus \{0\}$.
\end{biz}



Minkowski's theorem is sharp.  
For, let $\epsilon>0$ be an arbitrary positive number,
and let $L=\Z^n$ be the lattice of points with integer coordinates
in $\R^n$. Let $K$ be the set of vectors $(v_1,\ldots ,v_n)\in \R^n$ 
for which
$-1+\epsilon \leq v_i\leq 1-\epsilon$
($i=1,\ldots ,n$). Then $K$ is bounded, closed, convex, centrally symmetric with respect to the origin, its volume is 
$(1-\epsilon)^n2^n\det L$, yet $L\cap K=\{0\}$.


\begin{kov} \label{Minkowski-kov}
Let $L$ be a lattice in $\R^n$. Then
 $L$ has a lattice vector $v\neq 0$ whose length is at most
$\sqrt{n}\sqrt[n]{\det L}$. 
\end{kov}
\begin{biz}
Let $K$ be the following centrally symmetric cube with side length
$s=2\sqrt[n]{\det L}$: 
$$ K=\{(v_1,\ldots, v_n)\in \R^n:~-s/2\leq v_i\leq s/2,~i=1,\ldots, n\} \koz . $$
The volume of the cube 
$K$ is exactly $2^n\det L$, and
so it contains a non-zero lattice vector. 
However, the vectors in $K$ have length at most
$\sqrt{n}\sqrt[n]{\det L}$.
\end{biz}



We remark that, for $n>1$, we can find an even shorter lattice vector, if
we replace the cube in the proof of the previous assertion by a suitable ball.

 


\subsection{Gauss' algorithm for two-dimensional lattices}
Our goal is to design an algorithm that finds a non-zero short
vector in a given lattice.
In this section we consider this problem for 
two-dimensional lattices, which is the 
simplest non-trivial case.
Then there is an elegant, instructive, and efficient algorithm that finds short
lattice vectors.
This algorithm also serves as a basis for the higher-dimensional cases.
Let $L$ be a lattice with basis 
$b_1,b_2$ in $\R^2$.

\begin{alg}{Gauss($b_1,b_2$)}\inddef{\textsc{Gauss}}\index{Gauss' algorithm!for lattices}
\nevindex{Gauss, Johann Carl Friedrich (1777--1855)}
1 \' $(a,b) \leftarrow (b_1,b_2)$\\
2 \' \key{forever} \= \\
3 \'               \> \key{do} \= $b\leftarrow$  the shortest lattice 
vector on the line $b-\lambda a$\\
4 \'               \>          \= \key{if} \= $|b|<|a|$ \\
5 \'               \>          \>          \> \key{then} \= $b\leftrightarrow a$\\
6 \'               \>          \>          \> \key{else} \> \key{return} $(a,b)$
\end{alg}


In order to analyse the procedure, the following facts will be useful.


\begin{lemma}
\label{gauss-red1-lm}
Suppose that $a$ and $b$ are two linearly independent vectors in the plane
$\R^2$, and let $L$ be the lattice generated by them.
The vector $b$ 
is a shortest 
non-zero vector of $L$ 
on the line $b-\lambda a$ 
if and only if 
\index{lattice vector!shortest}
\begin{equation}
\label{gauss-red1-eq}
\left| (b,a)/(a,a) \right| \leq 1/2 \koz .
\end{equation}
\end{lemma}
\begin{biz}
We write $b$ as the sum of 
a vector parallel to $a$ and a vector orthogonal to $a$:
\begin{equation}
\label{gauss-star-eq}
b= (b,a)/(a,a) a + b^* \koz .
\end{equation}
Then, as the vectors $a$ and $b^*$ are orthogonal,
\begin{equation*}
|b-\lambda a|^2=
\left | \left(\frac{(b,a)}{(a,a)}-\lambda \right)a+b^* \right |^2=
\left( \frac{(b,a)}{(a,a)}-\lambda \right) ^2|a|^2+|b^*|^2\koz .
\end{equation*}
This quantity takes its smallest value for  the integer 
$\lambda$ that is the closest to
the number $(b,a)/(a,a)$.
Hence $\lambda=0$ gives the minimal value if and only if~(\ref{gauss-red1-eq}) 
holds. 
\end{biz}
\begin{lemma}
\label{gauss-red2-lm}
Suppose that the linearly independent vectors  $a$ and $b$ form a basis
for a lattice $L\subseteq \R^2$ and that inequality~(\ref{gauss-red1-eq}) 
holds.
Assume, further, that
\begin{equation}
\label{gauss-red2-def-eq}
|b|^2\geq (3/4)|a|^2 \koz . 
\end{equation}
Write $b$, as in~(\ref{gauss-star-eq}), as the sum of the vector $((b,a)/(a,a))a$, which is
parallel to
$a$, and the vector $b^*=b - ((b,a)/(a,a))a$, which is orthogonal to $a$.
Then
\begin{equation}
\label{gauss-red2-eq}
|b^*|^2\geq (1/2)|a|^2 \koz.
\end{equation}
Further, either $b$ or $a$ is a shortest non-zero vector in $L$.
\end{lemma}
\begin{biz}
By the assumptions,
\begin{equation*}
|a|^2\leq \frac{4}{3}|b|^2=\frac{4}{3}|b^*|^2+
\frac{4}{3} \left( (b,a)/(a,a) \right)^2|a|^2
\leq
\frac{4}{3}|b^*|^2+ (1/3)|a|^2 \koz .
\end{equation*}
Rearranging the last displayed line, 
we obtain  $|b^*|^2\geq (1/2)|a|^2.$

The length of a vector  $0\neq v=\alpha a+\beta b\in L$ can be computed as
\begin{equation*}
|\alpha a+\beta b|^2=
|\beta b^*|^2+\left( \alpha+\beta (b,a)/(a,a) \right)^2|a|^2
\geq \beta^2|b^*|^2\geq (1/2)\beta^2|a|^2,
\end{equation*}
which implies 
$|v|>|a|$ whenever $|\beta|\geq 2$.
If $\beta=0$ and $\alpha\neq 0$, then $|v|=|\alpha|\cdot|a|\geq |a|.$ 
Similarly, $\alpha=0$ and $\beta\neq 0$ gives
$|v|=|\beta|\cdot |b|\geq |b|$.
It remains to consider the case when $\alpha\neq 0$ and $\beta=\pm 1.$
As $|-v|=|v|$, we may assume that $\beta=1.$ In this case, however, 
$v$ is of the form $v=b-\lambda a$  ($\lambda=-\alpha$), and, by 
Lemma~\ref{gauss-red1-lm}, 
the vector $b$ is a shortest lattice vector on this line.
\end{biz}
\begin{tetel}
Let $v$ be a shortest non-zero lattice
vector in $L$. \index{lattice vector!shortest} 
Then
Gauss' algorithm
\index{Gauss' algorithm!for lattices} 
terminates after $O(1+\lg (|b_1|/|v|))$ iterations, 
and the resulting vector $a$
is a shortest non-zero vector in $L$.
\end{tetel}
\begin{biz}
First we verify that, during the course of the algorithm, 
the vectors  $a$ and $b$ will always form a basis
for the lattice $L$.
If, in line~3, we replace
$b$ by a vector of the form $b'=b-\lambda a$,
then, as $b=b'+\lambda a$,
the pair $a,\ b'$ remains a basis of  $L$.
The swap in line~5 only concerns the order of the basis vectors.
Thus $a$ and $b$ is always a basis of $L$, as we claimed.

By Lemma~\ref{gauss-red1-lm}, 
inequality (\ref{gauss-red1-eq}) holds after the first step (line~3) in the loop,  
and so we may apply Lemma~\ref{gauss-red2-lm}
to the scenario before lines 4--5.
This shows that if  none of $a$ and $b$ is shortest,
then
$|b|^2\leq (3/4) |a|^2.$ 
Thus, except perhaps for the last execution of the loop,
after each swap in line~5, 
the length of $a$ is decreased by a factor of at least 
$\sqrt{3/4}$.
Thus we obtain the bound for the number of executions of the loop.
Lemma~\ref{gauss-red2-lm}
implies also that 
the vector $a$ at the end is a shortest non-zero vector in 
$L$.
\end{biz}



Gauss' algorithm
\index{Gauss' algorithm!for lattices} 
gives an efficient polynomial time method for computing a shortest vector in the lattice
$L\subseteq \R^2$.
The analysis of the algorithm
gives the following interesting theoretical consequence.
\begin{kov} \label{sik-kov}
Let $L$ be a lattice in $\R^2$, and let $a$ be a shortest non-zero 
lattice vector 
in  $L$.
\index{lattice vector!shortest} 
Then $|a|^2 \leq (2/\sqrt 3)\det L.$
\end{kov}
\begin{biz}
Let $b$ be a vector in $L$ such that $b$ is 
 linearly independent of
$a$ and~(\ref{gauss-red1-eq}) holds. Then
\begin{equation*}
|a|^2\leq  |b|^2 = |b^*|^2+ \left(\frac{(b,a)}{(a,a)}\right)^2|a|^2
\leq |b^*|^2+\frac{1}{4}|a|^2\koz ,
\end{equation*}
which yields $(3/4) |a|^2\leq |b^*|^2$.
The area of the fundamental parallelogram
can be computed using the well-known
formula
$$\mbox{area}=\mbox{base}\cdot\mbox{height}\koz,$$
and so 
$\det L=|a||b^*|$. The number $|b^*|$ can now be bounded by the previous 
inequality.
\end{biz}

\subsection{A Gram-Schmidt orthogonalisation and weak reduction}
\index{Gram-Schmidt orthogonalisation}
\nevindex{Gram, Jorgen Pedersen (1850--1916)}\nevindex{Schmidt, Erhard (1876--1959)}

Let $b_1,\ldots,b_n$ be a linearly independent collection of vectors
in $\R^n$. For an index $i$ with $i\in\{1,\ldots,n\}$, 
we let $b_i^*$ denote the component of $b_i$ that is orthogonal to the
subspace spanned by 
$b_1,\ldots,b_{i-1}$.
That is,
$$b_i=b_i^*+\sum_{j=1}^{i-1}\lambda_{ij}b_j \koz ,$$
where
$$(b_i^*,b_j)=0\quad\mbox{for}\quad j=1,\ldots,i-1 \koz .$$
Clearly $b_1^*=b_1$. 
The vectors  
$b_1^*,\ldots,b_{i-1}^*$ span the same subspace as the vectors
$b_1,\ldots,b_{i-1}$, and so, with  suitable coefficients $\mu_{ij}$, 
we may write
\begin{equation}
\label{grsch-decomp-eq}
b_i=b_i^*+\sum_{j=1}^{i-1}\mu_{ij}b_j^*\koz ,
\end{equation}
and 
$$(b_i^*,b_j^*)=0,\;\;\; \mbox{if~}j\neq i \koz .$$
By the latter equations, the vectors
$b_1^*,\ldots,b_{i-1}^*,b_i^*$ form an orthogonal system, and so
\begin{equation}
\label{grsch-coeff-eq}
\mu_{ij}=\frac{(b_i,b_j^*)}{(b_j^*,b_j^*)} \;\; ~~~ (j=1,\ldots,i-1)\koz .
\end{equation}

The set of the vectors $b_1^*,\ldots,b_n^*$ is said to be the \ki{Gram-Schmidt
orthogonalisation} of the vectors
$b_1,\ldots,b_n$.
\inddef{Gram-Schmidt orthogonalisation}
\begin{lemma}
Let $L\subseteq \R^n$ be a lattice with basis $b_1,\ldots,b_n$. Then
\begin{equation*}
\det L=\prod_{i=1}^n|b_i^*|\koz .
\end{equation*}
\end{lemma}
\begin{biz}
Set  $\mu_{ii}=1$ and $\mu_{ij}=0$, if $j>i$. Then
$b_i^*=\sum_{k=1}^n\mu_{ik}b_k$, and so
$$
(b_i^*,b_j^*)=\sum_{k=1}^n\mu_{ik}\sum_{l=1}^n(b_k,b_l)\mu_{jl}\koz,
$$
that is, $B^*=MBM^T$ where $B$ and $B^*$ are 
the Gram matrices\index{Gram matrix} of the collections 
$b_1,\ldots,b_n$ and 
$b_1^*,\ldots,b_n^*$, respectively, and 
$M$ is the matrix with entries 
$\mu_{ij}$.
The matrix   $M$  is a lower triangular matrix
with ones in the main diagonal,
and so $\det M=\det M^T=1$.
As  $B^*$ is a diagonal matrix, we obtain
$\prod_{i=1}^n|b_i^*|^2=\det B^*=(\det M)(\det B)(\det M^T)=\det B$. 
\end{biz}

\begin{kov}[Hadamard inequality] \label{hadamard}
\index{Hadamard inequality}
\nevindex{Hadamard, Jacques Salomon (1865--1963)}
$\prod_{i=1}^n|b_i|\geq \det L.$
\end{kov}
\begin{biz}
The vector  
$b_i$ can be written as the sum of the vector
 $b_i^*$ and a vector orthogonal to $b_i^*$, 
and hence $|b_i^*|\leq |b_i|$. 
\end{biz}



The vector  $b_i^*$ is the component of 
 $b_i$ orthogonal to the subspace spanned by the vectors $b_1,\ldots,b_{i-1}$.
Thus
$b_i^*$ does not change if we subtract a linear combination 
of the vectors $b_1,\ldots,b_{i-1}$ from $b_i$.
If, in this linear combination, the coefficients are integers, 
then the new sequence
$b_1,\ldots,b_n$ will be a basis of the same lattice as the original.
Similarly to the first step of the loop in 
Gauss'
algorithm, we can make\index{Gauss' algorithm!for lattices} 
the numbers $\mu_{ij}$ in~(\ref{grsch-coeff-eq}) small.
The input of the following procedure is a basis $b_1,\ldots,b_n$ of a lattice 
$L$. 

\begin{alg}{Weak-Reduction$(b_1,\ldots,b_n)$}\inddef{\textsc{Weak-Reduction}}
1 \' \key{for}\= $j\leftarrow n-1$ \key{downto} $1$ \\
2 \'          \> \key{do} \= \key{for} \= $i\leftarrow j+1$ \key{to} $n$ \\
3 \'          \> 		  \>           \> $b_i\leftarrow b_i-\lambda b_j,$ 
				where $\lambda$ is the integer nearest the number  $(b_i,b_j^*)/(b_j^*,b_j^*)$ \\
4 \' \key{return} $(b_1,\ldots,b_n)$
\end{alg}

\begin{defi}[Weakly reduced basis]
A basis $b_1,\ldots,b_n$ of a lattice
is said to be \ki{weak\-ly reduced}\inddef{basis!of a lattice!weakly reduced} 
if the 
coefficients $\mu_{ij}$ in~(\ref{grsch-coeff-eq}) 
satisfy
\begin{equation*}
|\mu_{ij}|\leq \frac{1}{2}\quad\mbox{for}\quad 1\leq j<i\leq n\koz .
\end{equation*}
\end{defi}

\begin{lemma}
The basis given by
the procedure \textsc{Weak-Reduction} is weakly reduced.
\index{basis!of a lattice!weakly reduced} 

\end{lemma}
\begin{biz}
By the remark preceding the algorithm, we obtain that the vectors
 $b_1^*,\ldots,b_n^*$ never change.
Indeed, 
we only subtract linear combinations of vectors with index less than $i$ from
$b_i$.
Hence
the inner instruction does not change the value of $(b_k,b_l^*)$ with
$k\neq i$. The values of the  $(b_i,b_l^*)$
do not change  for $l>j$ either. On the other hand, the instruction achieves,
with the new $b_i$, that
 the inequality $|\mu_{ij}|\leq 1/2$ holds:
$$ |(b_i-\lambda b_j^*,b_j^*)|=|(b_i,b_j^*)-\lambda(b_j^*,b_j^*)|=
|(b_i,b_j^*)-\lambda(b_j^*,b_j^*)|\leq \frac{1}{2}(b_j^*,b_j^*) \koz .$$
By the observations above, this inequality remains valid during
the execution  of the
procedure.
\end{biz}



\subsection{Lov�sz-reduction}
First we define, in an arbitrary dimension, a property of the bases that
usually turns out to be 
useful. The definition will be of a technical nature. Later we will
see that these bases are interesting, in the sense that they consist of 
short vectors. This property will make them widely applicable.


\begin{defi}
A basis $b_1,\ldots,b_n$ of a lattice $L$ is said to be 
\ki{(Lov�sz-)reduced}\index{basis!of a lattice!reduced}
\nevindex{Lov�sz, L�szl�} 
if
\begin{itemize}
\item
it is weakly reduced, \index{basis!of a lattice!weakly reduced}
\end{itemize}
and, using the notation introduced for the Gram-Schmidt orthogonalisation,
\index{Gram-Schmidt orthogonalisation} 
\begin{itemize}
\item
$|b_i^*|^2\leq (/3) |b_{i+1}^*+\mu_{i+1,i}b_i^*|^2$ for all
$1\leq i<n$.
\end{itemize}
\end{defi}


Let us observe the analogy of the conditions above to the inequalities
that we have seen when investigating 
Gauss' algorithm.\index{Gauss' algorithm!for lattices} 
For $i=1$, $a=b_1$ and $b=b_2$, being weakly reduced ensures
that $b$ is a shortest vector on the line $b-\lambda a$.
The second condition is equivalent to the inequality 
$|b|^2\geq (3/4) |a|^2$,
but here it is expressed in terms of the Gram-Schmidt basis.
For a general index $i$,
the same is true, if $a$ plays the r\^ole of the vector 
$b_i$, and $b$ plays the r\^ole of 
the component of the vector $b_{i+1}$ that is orthogonal to 
the subspace spanned by $b_1,\ldots,b_{i-1}$.


\begin{alg}{Lov�sz-Reduction($b_1,\ldots,b_n)$}\inddef{\textsc{Lov�sz-Reduction}}
1 \' \key{forever} \= \\
2 \'               \> \key{do} $(b_1,\ldots,b_n)\leftarrow$\textsc{Weak-Reduction$(b_1,\ldots,b_n)$}
\index{\textsc{Weak-Reduction}} \\
3 \'               \> find an index $i$ for which the second condition of
being reduced is violated \\
4 \'               \> \key{if} \= there is such an $i$ \\
5 \'               \>          \> \key{then} \= $b_i\leftrightarrow b_{i+1}$ \\ 
6 \'               \>          \> \key{else} \> \key{return} $(b_1,\ldots,b_n)$
\end{alg}


\begin{tetel}
Suppose that in the lattice $L\subseteq \R^n$ each of the 
pairs of the lattice vectors has an integer scalar product.
Then the swap in the 5th line of the \textsc{Lov�sz-Reduction} 
occurs at most $\lg_{4/3}(B_1\cdots B_{n-1})$ times where
$B_i$ is the upper left 
$(i\times i)$-subdeterminant \index{subdeterminant} 
of the Gram matrix of the initial basis $b_1,\ldots,b_n$.\index{Gram matrix}
\end{tetel}
\begin{biz}
The determinant $B_i$ is 
the determinant of the Gram matrix
of $b_1,\ldots,b_i$, and,
by the observations we made at the discussion of the 
Gram-Schmidt orthogonalisation,
\index{Gram-Schmidt orthogonalisation} 
$B_i=\prod_{j=1}^i|b_j^*|^2$. This, of course, implies that
$B_{i}=B_{i-1}|b_{i}^*|^2$  for $i>1$. 
By the above,
the procedure \textsc{Weak-Reduction} cannot change the vectors $b_i^*$,
and so it does not change the product $\prod_{j=1}^{n-1} B_j$ either.
Assume, in line~5 of the procedure, that
a swap $b_i\leftrightarrow b_{i+1}$ takes place.
Observe that, unless $j=i$,
the sets $\{b_1,\ldots,b_j\}$ do not change, and
neither do the determinants $B_j$.
The r\^ole of the vector $b_i^*$ is taken over 
by the vector $b_{i+1}^*+\mu_{i,i+1}b_i$, whose length,
because of the conditions of the swap, is at most 
$\sqrt{3/4}$ times the length of  $b_i^*$.
That is, the new $B_i$  is at most $3/4$ times the old.
By the observation above, the 
new value of $B=\prod_{j=1}^{n-1} B_j$ will also be at most 
$3/4$ times the old one. 
Then the assertion follows from the fact that
the quantity $B$ remains a positive integer.
\end{biz}

\begin{kov} \label{lovasz-kov}
Under the conditions of the previous theorem, 
the cost of the procedure \textsc{Lov�sz-Reduction} is at most
$O(n^5\lg nC)$ arithmetic operations with rational numbers where
$C$ is the maximum of 
$2$ and the quantities $|(b_i,b_j)|$ with $i,j=1,\ldots,n$. 
\end{kov}
\begin{biz}
It follows from the  
Hadamard inequality\index{Hadamard inequality} that
\begin{equation*}
B_i\leq \prod_{j=1}^i\sqrt{(b_1,b_j)^2+\ldots+(b_i,b_j)^2}
\leq (\sqrt{i} C)^i\leq (\sqrt{n}C)^n\koz .
\end{equation*}
Hence $B_1\cdots B_{n-1}\leq(\sqrt{n}C)^{n(n-1)}$ and
$\lg_{4/3}(B_1 \ldots B_{n-1}) =O(n^2\lg nC)$.
By the previous theorem, this is the number of iterations
in the algorithm.
The cost of the
Gram-Schmidt orthogonalisation\index{Gram-Schmidt orthogonalisation} 
is $O(n^3)$ operations, and the cost of weak reduction is
$O(n^2)$ scalar product computations, each of which can be performed using
$O(n)$ operations (provided 
the vectors are represented by their coordinates
in an orthogonal basis\index{basis!orthogonal}). 
\end{biz}



One can show that the length of the integers that
occur during the run of the algorithm
(including the numerators and the denominators of 
the fractions in the Gram-Schmidt orthogonalisation)
will be below a  polynomial bound.


\subsection{Properties of reduced bases}

Theorem~\ref{LLL-main} of this section
gives a summary of the properties of 
reduced bases that turn out to be useful in their applications.
We will find that a reduced basis consists of relatively short vectors.
More precisely, 
$|b_1|$  will approximate, 
within a constant factor depending only on the dimension,
the length of a shortest non-zero
lattice vector. \index{lattice vector!shortest} 
\begin{lemma} 
\label{lll-prop-lm}
Let us assume that the vectors  $b_1,\ldots,b_n$ form a reduced basis
\index{basis!of a lattice!reduced} of a lattice $L$.
Then, for $1\leq j\leq i\leq n$,
\begin{eqnarray}\label{lll-prop-lm-eq}
(b^*_i,b^*_i)\geq 2^{j-i} (b_{j}^*,b_{j}^*)\koz .
\end{eqnarray}
In particular,
\begin{eqnarray}\label{lll-prop-lm-speq}
(b^*_i,b^*_i)\geq 2^{1-i} (b_{1}^*,b_{1}^*)\koz .
\end{eqnarray}
\end{lemma}
\begin{biz}
Substituting $a=b_i^*,$  
$b=b_{i+1}^* + ((b_{i+1},b_i^*))/((b_i^*,b_i^*)b_i^*)$, 
Lemma~\ref{gauss-red2-lm} gives, for all $1\leq i< n$, that
$$(b^*_{i+1},b^*_{i+1})\geq (1/2) (b_{i}^*,b_{i}^*) \koz .$$
Thus, inequality~(\ref{lll-prop-lm-eq}) follows by induction.
\end{biz}



Now we can formulate the fundamental theorem of reduced bases.

\begin{tetel} \label{LLL-main}
Assume that the vectors  $b_1,\ldots,b_n$ form a reduced basis of 
a lattice $L$.
\index{basis!of a lattice!reduced}
Then \newline
(i) $|b_1|\leq 2^{(n-1)/4}(\det L)^{(1/n)}$.\newline 
(ii) $|b_1|\leq 2^{(n-1)/2} |b|$ for all lattice vectors
$0\neq b\in L$. In particular, the length of $b_1$ is not greater than
$2^{(n-1)/2}$ times the length of a shortest non-zero
\index{lattice vector!shortest} lattice vector.\newline
(iii) $|b_1|\cdots |b_n|\leq 2^{(n(n-1))/4}\det L.$ 
\end{tetel}
\begin{biz}
(i) Using inequality (\ref{lll-prop-lm-speq}), 
$$(\det L)^2=
\prod_{i=1}^n (b_i^*,b_i^*)\geq
\prod_{i=1}^n ({{2^{1-i}}}(b_1,b_1))
={{2^{\frac{-n(n-1)}2}}}(b_1,b_1)^n \koz ,$$
and so assertion~(i) holds.

(ii) Let $b=\sum_{i=1}^n z_ib_i\in L$ with $z_i\in\Z$ be a lattice vector.
Assume that $z_j$ is the last non-zero coefficient
and write 
$b_j=b_j^*+v$ where $v$ is a linear combination of the vectors 
$b_1,\ldots,b_{j-1}$.
Hence
$b=z_jb_j^*+w$ where $w$ lies in the subspace spanned by 
$b_1,\ldots,b_{j-1}$.
As $b_j^*$ is orthogonal to this subspace,
$$(b,b)=z_j^2(b_j^*,b_j^*)+(w,w)\geq 
(b_j^*,b_j^*)
\geq {2^{1-j}}(b_1,b_1)
\geq {2^{1-n}}(b_1,b_1)
\koz ,$$
and so assertion~(ii) is valid.

(iii) First we show that $(b_i,b_i)\leq 2^{i-1}(b_i^*,b_i^*)$. 
This inequality is obvious if 
$i=1$, and so we assume that $i>1$. 
Using the decomposition~(\ref{grsch-decomp-eq}) 
of the vector $b_i$ and the fact that the basis is weakly reduced, we obtain that
\begin{eqnarray*}
(b_i,b_i)&=&
\sum_{j=1}^i\left({\frac{(b_i,b_j^*)}{(b_j^*,b_j^*)}}\right)^2(b_j^*,b_j^*) \\
&\leq& (b_i^*,b_i^*)+ {\frac{1}{4}}\sum_{j=1}^{i-1}(b_j^*,b_j^*)
\leq (b_i^*,b_i^*)+{\frac{1}{4}}\sum_{j=1}^{i-1}2^{i-j}(b_i^*,b_i^*) \\
&\leq&
(2^{i-2}+1)(b_i^*,b_i^*)
\leq 2^{i-1}(b_i^*,b_i^*)\koz .
\end{eqnarray*}
Multiplying these inequalities for $i=1,\ldots,n$,
\begin{eqnarray*}
\prod_{i=1}^n (b_i,b_i)&\leq& \prod_{i=1}^n 2^{i-1}(b_i^*,b_i^*)
=2^{\frac{n(n-1)}2}\prod_{i=1}^n (b_i^*,b_i^*)=
2^{\frac{n(n-1)}2}(\det L)^2\koz ,
\end{eqnarray*}
which is precisely the inequality in~(iii).
\end{biz}



It is interesting to compare assertion~(i) in the previous theorem 
and Corollary~\ref{Minkowski-kov} after Minkowski's theorem.
\index{Minkowski's Convex Body Theorem}
\nevindex{Minkowski, Hermann (1864--1909)} 
Here 
we obtain a weaker bound for the length of $b_1$, but this vector can be 
obtained by an efficient algorithm.
Essentially, the existence of the basis that satisfies 
assertion~(iii) was first shown by Hermite using
\nevindex{Hermite, Charles (1822--1901)} 
the tools in the proofs of Theorems~\ref{lattice-basis-thm} 
and~\ref{LLL-main}. 
Using a Lov�sz-reduced basis, the cost of finding a shortest vector in a lattice with dimension $n$ 
is at most polynomial in the input size and 
in $3^{n^2}$; see Exercise~\ref{shortest-coord}.

\begin{gyak}
\ujgyak
\textit{The triangular lattice\gyakindex{triangular lattice} is optimal.} 
Show that the bound in Corollary~\ref{sik-kov} is sharp.
More precisely, let 
$L\subseteq \R^2$ be a full lattice and let  $0\neq a\in L$ be a shortest
vector in $L$.
Verify that the
inequality  $|a|^2 = (2/\sqrt{3}) \det L$ holds if and only if 
$L$ is similar to the triangular lattice.
\ujgyak
\textit{The denominators of the Gram-Schmidt numbers.
\gyakindex{Gram-Schmidt orthogonalisation}} 
Let us assume that the Gram matrix of a basis $b_1,\ldots,b_n$ 
\index{Gram matrix} has only integer entries. 
Show that the numbers $\mu_{ij}$ in~(\ref{grsch-coeff-eq}) 
can be written in the form
$\mu_{ij}=\zeta_{ij}/\prod_{k=1}^{j-1}B_k$
where the $\zeta_{ij}$ are integers
and $B_k$ is the determinant of the Gram matrix of the vectors 
$b_1,\ldots,b_k$.
\ujgyak
\textit{The length of the vectors in a reduced basis.
\gyakindex{basis!of a lattice!reduced}} 
Let $b_1,\ldots,b_n$ be a reduced basis of a lattice $L$ 
and let us assume that the numbers 
$(b_i,b_i)$ are integers.
Give an upper bound depending only on $n$ and $\det L$ for the length of the 
vectors $b_i$. More precisely, prove that
$$|b_i| \leq 2^{\frac{n(n-1)}{4}}\det L \koz .$$
\ujgyak 
\textit{The coordinates of a shortest 
lattice vector.\gyakindex{lattice vector!shortest}} 
\label{shortest-coord}
Let $b_1,\ldots,b_n$ be a reduced basis of a lattice $L$.
Show that each of the  shortest vectors in $L$ is of the form
$\sum z_ib_i$ where $z_i\in \Z$ and
$|z_i|\leq 3^n$.
Consequently, for a bounded  $n$, one can find a shortest non-zero
lattice vector in polynomial time.


\textit{Hint.} Assume, for some lattice vector $v=\sum z_ib_i$, that
$|v|\leq |b_1|$. Let us write $v$ in the basis $b_1^*,\ldots,b_n^*$:
$$v=\sum_{j=1}^n(z_j+\sum_{i=j+1}^n\mu_{ij}z_i)b_j^* \koz .$$
It follows from the assumption that each of the components of $v$ 
(in the orthogonal basis) 
is at most as long as
$b_1=b_1^*$:
$$\left|z_j+\sum_{i=j+1}^n\mu_{ij}z_i\right|\leq \frac{|b_1^*|}{|b_j^*|} \koz .$$
Use then the inequalities  $|\mu_{ij}|\leq 1/2$ 
and~(\ref{lll-prop-lm-speq}).
\end{gyak}

\section{Factoring polynomials in $\Q[x]$\label{sec:algebra5}}

In this section we study the problem of factoring polynomials with 
rational coefficients.
The input of the 
\ki{factorisation problem}\index{factorisation!of a polynomial} is a polynomial $f(x)\in \Q[x]$.
Our goal is 
to compute a factorisation 
\begin{equation} \label{felb-Q}
f=f_1^{e_1}f_2^{e_2}\cdots f_s^{e_s},
\end{equation}
where the polynomials
$f_1, \ldots ,f_s $ are pairwise relatively prime, and irreducible over
$\Q$,\index{polynomial!irreducible}
and the numbers $e_i$ are positive integers.
By Theorem~\ref{ufd}, $f$ determines, essentially uniquely,
the polynomials $f_i$ and the exponents
$e_i$.


\subsection{Preparations}
First we reduce the problem (\ref{felb-Q}) to another problem that can be 
handled more easily.
\begin{lemma} \label{Z-vissza}
We may assume that the polynomial $f(x)$ has integer coefficients and it
has leading coefficient~$1$.
\end{lemma}
\begin{biz} 
Multiplying by 
the common denominator of the 
coefficients, we may assume that
$f(x)=a_0+a_1x+\cdots +a_nx^n\in \Z[x]$. Performing the
substitution
$y=a_nx$, we obtain  the polynomial
$$g(y)=
{{a_n}^{n-1}}f\left({\frac{y}{a_n}}\right)=
y^n+\sum_{i=0}^{n-1} a_n^{n-i-1}a_iy^i \koz , $$
which has integer coefficients and its leading coefficient is~1. 
Using a factorisation of $g(y)$,
a factorisation of $f(x)$ can be obtained efficiently.
\end{biz}


\subsubsection{Primitive polynomials, Gauss' lemma.} 
\begin{defi}
A polynomial $f(x)\in\Z[x]$ is said to be \inddef{polynomial!primitive} 
\ki{primitive,} if the greatest common divisor of its coefficients is~$1$.
\end{defi}

A polynomial 
$f(x)\in\Z[x]\setminus\{0\}$ can be written in a unique way as the
product of an integer and a primitive polynomial in 
$\Z[x]$. Indeed, if $a$ is 
the greatest common divisor of the coefficients, then 
$f(x)=a (1/a) f(x)$. 
Clearly, $(1/a) f(x)$ is a primitive polynomial with integer coefficients.

\begin{lemma}[Gauss' Lemma]
\index{Gauss lemma!on primitive polynomials}
If $u(x),\ v(x)\in\Z[x]$ are primitive polynomials, then so is
the product $u(x)v(x)$.
\end{lemma}
\begin{biz}
We argue by contradiction and assume that $p$ is a prime number 
that divides all the coefficients of $uv$.
Set $u(x)=\sum_{i=0}^n u_ix^i$, $v(x)=\sum_{j=0}^mv_jx^j$ and
let $i_0$ and $j_0$ be the smallest indices such that
$p\nmid u_{i_0}$ and $p\nmid v_{j_0}$. Let
$k_0=i_0+j_0$ and consider the coefficient of $x^{k_0}$ in the product
$u(x)v(x)$. This coefficient is
\begin{equation*}
\sum_{{i+j}=k_0}u_iv_j=
u_{i_0}v_{j_0}+
\sum_{i=0}^{i_0-1}u_iv_{k_0-i}
+\sum_{j=0}^{j_0-1}u_{k_0-j}v_j\koz .
\end{equation*}
Both of the sums on the right-hand side of this equation are divisible by $p$, 
while $u_{i_0}v_{j_0}$ is not,
and hence the coefficient of $x^{k_0}$ in $u(x)v(x)$  cannot be divisible
by $p$ after all.
This, however, is a contradiction.
\end{biz}

\begin{allit} \label{f-all}
Let us assume that 
$g(x),\ h(x)\in \Q[x]$ are polynomials with rational coefficients and 
leading coefficient~$1$ such that
the product $g(x)h(x)$ has integer coefficients.
Then the polynomials $g(x)$ and $h(x)$ have integer coefficients.
\end{allit}
\begin{biz}
Let us multiply $g(x)$ and $h(x)$ by the least common multiple
 $c_g$ and
$c_h$, respectively, 
of the denominators of their coefficients. 
Then the polynomials $c_gg(x)$ and
$c_hh(x)$ are primitive polynomials with integer coefficients.
Hence, by Gauss' Lemma, so is the product
$c_gc_hg(x)h(x)=(c_gg(x))(c_hh(x))$.
As the coefficients 
of $g(x)h(x)$ are integers, each of its coefficients is divisible by the 
integer $c_gc_h$.
Hence $c_gc_h=1$, and so $c_g=c_h=1$. Therefore $g(x)$ and
$h(x)$ are indeed polynomials with integer coefficients.
\end{biz}



One can show similarly, for a polynomial $f(x)\in \Z[x]$, that factoring 
$f(x)$ in 
$\Z[x]$ is equivalent to factoring the 
primitive part of $f(x)$ in  $\Q[x]$ and factoring
an integer, namely the greatest common divisor of the coefficients


\subsubsection{Mignotte's bound.} 

As we work over an infinite field,
\nevindex{Mignotte, Maurice} 
we have to pay attention to the size of the results in our computations.

\begin{defi}
The \ki{norm} 
of a polynomial $f(x)=\sum_{i=0}^na_ix^i\in\C[x]$ with complex coefficients
\inddef{norm!of a polynomial} is the real number
$\polnorm{f(x)}=\sqrt{\sum_{i=0}^{n}|a_i|^2}$.
\end{defi}



The inequality $\max_{i=0}^n |a_i|\leq \polnorm{f(x)}$ implies that 
a polynomial $f(x)$ with integer coefficients
can be described using $O(n\lg\polnorm{f(x)})$ bits.

\begin{lemma}
\label{landau-ineq-lm}
Let $f(x)\in\C[x]$ be a polynomial with complex coefficients.
Then, for all $c\in\C$, we have
\begin{equation*}
\polnorm{(x-c)f(x)}=\polnorm{({\overline{c}}x-1)f(x)}\koz ,
\end{equation*}
where ${\overline {c}}$ is the usual conjugate 
of the complex number  $c$.
\end{lemma}
\begin{biz}
Let us assume that $f(x)=\sum_{i=0}^na_ix^i$ 
and set $a_{n+1}=a_{-1}=0$.
Then
\begin{equation*}
(x-c)f(x)=\sum_{i=0}^{n+1}(a_{i-1}-ca_i)x^i\koz ,
\end{equation*}
and hence
\begin{eqnarray*}
\polnorm{(x-c)f(x)}^2
&=&
\sum_{i=0}^{n+1}|a_{i-1}-ca_i|^2
=
\sum_{i=0}^{n+1}
(|a_{i-1}|^2+|ca_i|^2
-a_{i-1}{\overline{ca_i}}
-{\overline{a_{i-1}}}ca_i)
\\
&=&
\polnorm{f(x)}^2+|c|^2\polnorm{f(x)}^2
-\sum_{i=0}^{n+1}
(a_{i-1}{\overline{ca_i}}
+
{\overline{a_{i-1}}}ca_i)\koz .
\end{eqnarray*}
Performing similar computations with the right-hand side of the equation in 
the lemma, we obtain that
\begin{equation*}
({\overline c}x-1)f(x)=\sum_{i=0}^{n+1}
({\overline{c}}a_{i-1}-a_i)x^i\koz ,
\end{equation*}
and so
\begin{eqnarray*}
\polnorm{({\overline{c}}x-1)f(x)}^2
&=&
\sum_{i=0}^{n+1}|{\overline{c}}a_{i-1}-a_i|^2
=
\sum_{i=0}^{n+1}
(|{\overline{c}}a_{i-1}|^2+|a_i|^2
-{\overline{c}}a_{i-1}{\overline{a_i}}
-c{\overline{a_{i-1}}}a_{i})
\\
&=&
\polnorm{f(x)}^2+|c|^2\polnorm{f(x)}^2
-\sum_{i=0}^{n+1}
(a_{i-1}{\overline{ca_i}}
+
{\overline{a_{i-1}}}ca_i)\koz.
\end{eqnarray*}
The proof of the lemma is now complete.
\end{biz}
\begin{tetel}[Mignotte] \label{mignotte}
\index{Mignotte's theorem}
Let us assume that the polynomials $f(x),g(x)\in \C[x]$ have complex coefficients
and leading coefficient~$1$ and that
$g(x)|f(x)$. If $\deg(g(x))=m$, then
 $\polnorm{g(x)}\leq 2^m\polnorm{f(x)}$.
\end{tetel}
\begin{biz}
By the fundamental theorem of algebra, $f(x)=\prod_{i=1}^n(x-\alpha_i)$
where $\alpha_1,\ldots,\alpha_n$ are the  complex roots 
of the polynomial $f(x)$ (with multiplicity).
Then there is a subset $I\subseteq \{1,\ldots,n\}$ such that 
$g(x)=\prod_{i\in I}(x-\alpha_i)$.
First we claim, for an arbitrary set $J\subseteq \{1,\ldots,n\}$, 
that
\begin{equation}
\label{landau-ineq}
\prod_{i\in J}|\alpha_i|\leq \polnorm{f(x)}\koz .
\end{equation}
If $J$ contains an integer $i$ with
$\alpha_i=0$, then this inequality will trivially hold.
Let us hence assume
that  $\alpha_i\neq 0$ for every
$i\in J$. Set
${\overline {J}}=\{1,\ldots,n\}\setminus J$
and $h(x)=\prod_{i\in {\overline{J}}}(x-\alpha_i)$.
Applying Lemma~\ref{landau-ineq-lm} several times, we obtain
that
\begin{equation*}
\polnorm{f(x)}=
\polnorm{\prod_{i\in J}(x-\alpha_i)h(x)}=
\polnorm{\prod_{i\in J}({\overline{\alpha_i}}x-1)h(x)}=
|\prod_{i\in J}{\overline{\alpha_i}}|\cdot\polnorm{u(x)}\koz ,
\end{equation*}
where $u(x)=\prod_{i\in  J}(x-1/{\overline{\alpha_i}})h(x)$.
As the leading coefficient of $u(x)$ is~1, $\polnorm{u(x)}\geq 1$, and
so
\begin{equation*}
|\prod_{i\in J}\alpha_i|=
|\prod_{i\in J}\overline{\alpha_i}|=
\polnorm{f(x)}/\polnorm{u(x)}\leq \polnorm{f(x)}\koz .
\end{equation*}

Let us express the coefficients of $g(x)$ 
using its roots:
\begin{eqnarray*}
g(x)&=&\prod_{i\in I}(x-\alpha_i)=
\sum_{J\subseteq I}\left((-1)^{|J|}
\prod_{j\in J}\alpha_jx^{m-|J|}\right)
\\
&=&
\sum_{i=0}^m
(-1)^{m-i}
\left(\sum_{J\subseteq I,|J|=m-i}\prod_{j\in J}\alpha_j\right)x^i\koz .
\end{eqnarray*} 
For an arbitrary polynomial 
$t(x)=t_0+\cdots +t_kx^k$, the inequality
$\polnorm{t(x)}\leq |t_0|+\cdots +|t_k|$ is valid. Therefore, using
inequality~(\ref{landau-ineq}), we find that
\begin{eqnarray*}
\polnorm{g(x)}
&\leq&
\sum_{i=0}^m
\left|\sum_{J\subseteq I,|J|=m-i}\prod_{j\in J}\alpha_j\right|
\\
&\leq&
\sum_{J\subseteq I}
\left|\prod_{j\in J}\alpha_j\right|
\leq 2^m\polnorm{f(x)}\koz .
\end{eqnarray*} 
The proof is now complete.
\end{biz}

\begin{kov}
The bit size of the irreducible factors in $\Q[x]$
 of an $f(x)\in\Z[x]$ with
leading coefficient~$1$ is polynomial in the bit size of 
$f(x)$.
\end{kov}



\subsubsection{Resultant and  good reduction.}
Let $\F$ be an arbitrary field, and let $f(x),\ g(x)\in \F[x]$ be polynomials with degree 
$n$ and $m$, respectively: $f=a_0+a_1x+\ldots+a_nx^n$,
$g=b_0+b_1x+\ldots+b_mx^m$ where $a_n\neq 0\neq b_m$.
We recall the concept of the  \ki{resultant} from Chapter~3.  
The resultant of $f$ and $g$ is the determinant of the 
$((m+n)\times (m+n))$-matrix \nevindex{Sylvester, James Joseph (1814--1897)}
\index{Sylvester matrix}\index{determinant}
\begin{equation}
\label{res-matrix-eq}
M=
\left(
\begin{array}{ccccccccc}
a_0 & a_1 & a_2 & a_3 & \cdots & a_{n}
\\
 & a_0 & a_1 & a_2 & \cdots & a_{n-1} & a_{n}
\\
& & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots
\\
& & & a_0 & a_1& \cdots & a_{n-2} & a_{n-1} & a_{n}
\\
b_0 & b_1 & \cdots & b_{m-1} & b_{m}
\\
 & b_0 & b_1 & \cdots & b_{m-1} & b_{m}
\\
 & & b_0 & b_1 & \cdots & b_{m-1} & b_{m}
\\
& & & \ddots & \ddots & \ddots & \ddots & \ddots
\\
  & & & & b_0 & b_1 & \cdots & b_{m-1} & b_{m}.
\end{array}
\right).
\end{equation}
The matrix above is usually referred to as the Sylvester matrix.  
The blank spaces in the Sylvester matrix represent zero entries.


The resultant provides  information 
about the common factors of  $f$ and $g$. 
One can use it to express, particularly elegantly, the fact 
that two polynomials are relatively prime:
\begin{equation} \label{res-eq}
\lnko(f(x),g(x))=1 \Leftrightarrow Res(f,g)\neq 0\koz .
\end{equation}



\begin{kov}
Let $f(x)=a_0+a_1x+\cdots +a_nx^n \in\Z[x]$ be a square-free (in 
$\Q[x]$), non-constant polynomial.
Then $Res(f(x),f'(x))$  is an integer. Further, assume that
$p$ is a prime not dividing $na_n$. 
Then the polynomial
$f(x)\mypmod{p}$ is square-free in
$\F_p[x]$ if and only if
$p$ does not divide $Res(f(x),f'(x))$.
\end{kov}
\begin{biz}
The entries of the Sylvester
matrix corresponding to $f(x)$ and 
$f'(x)$ are integers, and so is its determinant. 
The polynomial $f$ has no multiple roots over $\Q$, 
and so, by Exercise~\ref{diszkrimin}, 
$\lnko(f(x),f'(x))=1$, which gives, using
(\ref{res-eq}), 
that $Res(f(x),f'(x))\neq 0$. Let  $F(x)$ denote the polynomial $f$ reduced
modulo $p$. Then it follows from our assumptions that
 $Res(F(x),F'(x))$ is precisely the residue of  
$Res(f(x),f'(x))$ modulo $p$. 
By Exercise~\ref{diszkrimin}, the polynomial  $F(x)$
is square-free precisely when
$\lnko(F(x),F'(x))=1$, which is equivalent to
$Res(F(x),F'(x))\neq 0$. This amounts to saying that $p$ 
does not divide the integer $Res(f(x),f'(x))$.
\end{biz}
\begin{kov} \label{primkov}
If $f(x)\in \Z[x]$ is a square-free polynomial with degree $n$,
then there is a prime
$p=O((n\lg n+2n \lg \polnorm{f})^2)$
(that is, the absolute value of 
$p$ is polynomial in the bit size of $f$)
such that the polynomial $f(x)\mypmod{p}$ is square-free in
$\F_p[x]$.
\end{kov}

\begin{biz} By the Prime Number Theorem\index{Prime Number Theorem}
(Theorem~33.37), for  large enough $K$, the product of the primes in the interval 
$[1,K]$ is at least $2^{(0.9K/\ln K)}$.

Set $K=\left((n+1)\lg n+2n \lg\polnorm{f}\right)^2$. 
If $K$ is large enough, then
\begin{equation}
\label{noname-may30-eq}
p_1 \cdots p_l\geq 2^{(0.9K/\ln K)}>2^{\sqrt K}
\geq n^{n+1}\polnorm{f}^{2n}\geq n^{n+1}\polnorm{f}^{2n-1}|a_n|
\end{equation}
where $p_1,\ldots,p_l$ are primes not larger than $K$,
and $a_n$ is the leading coefficient of $f$.


Let us suppose, for the primes $p_1,\ldots,p_l$, that
$f(x)\mypmod{p_i}$ is not square-free in
$\F_{p_i}[x]$.
Then the product $p_1\cdots p_l$ 
divides $Res(f(x),f'(x))\cdot na_n$, and so
\begin{equation*}
p_1\cdots p_l\leq |Res(f,f')|\cdot|na_n|
\leq
\polnorm{f}^{n-1}\cdot\polnorm{f'}^n\cdot|na_n|
\leq n^{n+1} \polnorm{f}^{2n-1}|a_n|\koz .
\end{equation*}
(In the last two inequalities, we used 
 the Hadamard inequality,\index{Hadamard inequality} and the fact that
$\polnorm{f'(x)}\leq n\polnorm{f(x)}$.) 
This contradicts to inequality~(\ref{noname-may30-eq}), which must be valid because of the choice of 
$K$.
\end{biz}



We note that using the Prime Number Theorem more carefully, 
one can obtain a stronger bound for $p$.


\subsubsection{Hensel lifting.}
\nevindex{Hensel, Kurt Wilhelm Sebastian (1861--1913)}
\index{Hensel lifting}

We present a general procedure that can be used to obtain, 
given a factorisation modulo a prime $p$, a factorisation
modulo $p^N$ of a polynomial with integer coefficients.

\begin{tetel}[Hensel's lemma] \label{hensel-lemma}
\inddef{Hensel's lemma}
Suppose that $f(x),\ g(x),\ h(x)\in\Z[x]$
are polynomials with leading
coefficient~$1$ such that
$f(x)\equiv g(x)h(x)\mypmod{p}$, and, in addition, 
$g(x)\mypmod{p}$ and
$h(x)\mypmod{p}$ are relatively prime in
$\F_p[x]$. Then, for an arbitrary positive integer $t$, 
there are polynomials $g_t(x),\ h_t(x)\in\Z[x]$ 
such that
\begin{itemize}
\item
both of the leading coefficients of $g_t(x)$ and $h_t(x)$ are equal to $1$,
\item
$g_t(x)\equiv g(x)\mypmod{p}$ and
$h_t(x)\equiv h(x)\mypmod{p}$,
\item
$f(x)\equiv g_t(x)h_t(x)\mypmod{p^{t}}$.
\end{itemize}
Moreover, the polynomials
 $g_t(x)$ and $h_t(x)$ satisfying the conditions above are unique
modulo $p^t$.
\end{tetel}
\begin{biz}
From the conditions concerning the leading coefficients,
we obtain that
$\deg f(x)=\deg g(x)+\deg h(x),$ and, further, that
$\deg g_t(x)=\deg g(x)$ and $\deg h_t(x)=\deg h(x),$ provided the
suitable polynomials $g_t(x)$  and $h_t(x)$ indeed exist. 
The existence is proved by induction on 
$t$. In the initial step, $t=1$ and the choice  
$g_1(x)=g(x)$ and $h_1(x)=h(x)$ is as required.

The induction step $t\rightarrow t+1$:
let us assume that there exist 
polynomials $g_t(x)$ and $h_t(x)$ that are well-defined modulo $p^t$
and satisfy the conditions.
If the polynomials 
$g_{t+1}(x)$ and $h_{t+1}(x)$ exist, then they
must satisfy the conditions imposed on 
$g_t(x)$ and $h_t(x)$. As $g_t(x)$ and $h_t(x)$ are unique modulo $p^t$,
we may write $g_{t+1}(x)=g_t(x)+p^{t}\delta_g(x)$
and
$h_{t+1}(x)=h_t(x)+p^{t}\delta_h(x)$
where
$\delta_g(x)$ and $\delta_h(x)$ 
are polynomials with integer coefficients. The condition concerning the leading coefficients
guarantees that $\deg\delta_g(x)<\deg g(x)$ 
and that $\deg\delta_h(x)<\deg h(x)$. 

By the induction hypothesis,
$f(x)=g_t(x)h_t(x)+p^t\lambda(x)$ where
$\lambda(x)\in \Z[x]$. The observations about the degrees of the 
polynomials $g_t(x)$ and $h_t(x)$
imply that the degree of $\lambda(x)$ is smaller than $\deg f(x)$.
Now we may compute that
\begin{eqnarray*}
g_{t+1}(x)h_{t+1}(x)-f(x) &=&
g_t(x)h_t(x)-f(x)+p^th_t(x)\delta_g(x)+ \\ 
&+& p^tg_t(x)\delta_h(x)+p^{2t}\delta_g(x)\delta_h(x)
\\
&\equiv&
-p^t\lambda(x)+
p^t h_t(x)\delta_g(x)+p^t g_t(x)\delta_h(x)
\mypmod{p^{2t}}\koz .
\end{eqnarray*}
As $2t>t+1$, the congruence above holds 
modulo $p^{t+1}$. Thus
$g_{t+1}(x)$ and $h_{t+1}(x)$ satisfy the conditions if and only if
\begin{eqnarray*}
p^th_t(x)\delta_g(x)+p^tg_t(x)\delta_h(x)
\equiv p^t\lambda(x) \mypmod{p^{t+1}}\koz.
\end{eqnarray*}
This, however, amounts to saying,
after cancelling $p^t$ from both sides, that
\begin{eqnarray*}
h_t(x)\delta_g(x)+g_t(x)\delta_h(x)
\equiv \lambda(x) \mypmod{p} \koz.
\end{eqnarray*}
Using the congruences $g_t(x)\equiv g(x)\mypmod{p}$ and
$h_t(x)\equiv h(x)\mypmod{p}$ we obtain that this is equivalent to the congruence
\begin{equation} \label{hensel-eq}
h(x)\delta_g(x)+g(x)\delta_h(x)
\equiv \lambda(x) \mypmod{p} \koz.
\end{equation}
Considering the inequalities
$\deg\delta_g(x)<\deg g_t(x)$ and
$\deg\delta_h(x)<\deg h_t(x)$ and the fact that in
$\F_p[x]$ the polynomials $g(x)\mypmod{p}$ and
$h(x)\mypmod{p}$ are relatively prime,
we find that equation (\ref{hensel-eq}) can be solved uniquely in
$\F_p[x]$. For, if $u(x)$ and $v(x)$ form a solution to
$u(x)g(x)+v(x)h(x)\equiv 1\mypmod{p}$, then, by Theorem~\ref{euklideszi},  
the polynomials 
\begin{eqnarray*}
\delta_g(x)&=&v(x)\lambda(x)\mypmod{g(x)}\koz ,
\end{eqnarray*}
and
\begin{eqnarray*}
\delta_h(x)&=&u(x)\lambda(x)\mypmod{h(x)}
\end{eqnarray*}
form a solution of~(\ref{hensel-eq}).
The uniqueness of the solution follows from the bounds on the degrees, and from
the fact that
 $g(x)\mypmod{p}$ and
$h(x)\mypmod{p}$ relatively prime. The details of this are left to the reader.
\end{biz}

\begin{kov}\label{hc} Assume that $p$,  and the polynomials 
$f(x),\ g(x),\ h(x)\in \Z[x]$ satisfy the conditions of 
Hensel's lemma. Set $\fok f =n$ and let $N$ be a positive integer.
Then the polynomials $g_N(x)$ and $h_N(x)$ can be obtained using 
$O(Nn^2)$ arithmetic operations modulo $p^N$.
\end{kov}  
\begin{biz} The proof of Theorem~\ref{hensel-lemma} suggests the following algorithm. 

\begin{alg}{Hensel-Lifting\inddef{\textsc{Hensel-Lifting}}$(f,g,h,p,N)$}
1 \' $(u(x),v(x))\leftarrow$ is a solution, in $\F_p[x]$, of $u(x)g(x)+v(x)h(x)\equiv 1\mypmod p$ \\ 
2 \' $(G(x),H(x))\leftarrow (g(x),h(x))$\\
3 \' \key{for} \= $t\leftarrow 1$ \key{to} $N-1$ \\ 
4 \'           \> \key{do} \= $\lambda(x)\leftarrow (f(x)-G(x)\cdot H(x))/p^t$\\
5 \'           \>          \> $\delta_g(x)\leftarrow v(x)\lambda(x)$ reduced 
modulo ${g(x)}$ (in $\F_p[x]$)\\
6 \'           \>          \> $\delta_h(x)\leftarrow u(x)\lambda(x)$ reduced
modulo ${h(x)}$ (in $\F_p[x]$)\\
7 \'           \>          \> $(G(x),H(x))\leftarrow(G(x)+p^t\delta_g(x),H(x)+p^t\delta_h(x))$\ (in $(\Z/(p^{t+1}))[x]$)\\ 
8 \' \key{return} $(G(x),H(x))$
\end{alg}

The polynomials $u$ and $v$ can be obtained using $O(n^2)$ operations in 
$\F_p$ (see Theorem~\ref{euklideszi} and the remark following it). 
An iteration $t\rightarrow t+1$ consists of a constant number of 
operations with polynomials,
and the cost of one run of the main loop is 
$O(n^2)$ operations
(modulo $p$ and $p^{t+1}$). The total cost of reaching $t=N$ is $O(Nn^2)$ 
operations.
\end{biz}



\subsection{The Berlekamp-Zassenhaus algorithm}
\nevindex{Berlekamp, Elwyn Ralph}\nevindex{Zassenhaus, Hans Julius (1912--1991)}


The factorisation problem 
(\ref{felb-Q}) was efficiently reduced to the case in which
the polynomial $f$ has integer coefficients and leading coefficient~1.
We may also assume that 
$f(x)$ has no multiple factors in $\Q[x]$.
Indeed, in our case $f'(x)\neq 0$, and so the possible
 multiple factors of $f$ can be separated using the idea that we already
used over finite fields as follows.
By Lemma~\ref{többes}, 
the polynomial $g(x)=f(x)/(f(x),f'(x))$ is already square-free,
and, using Lemma~\ref{egyszeres}, it suffices to find its 
factors with multiplicity one.
From Proposition~\ref{f-all}, 
we can see that $g(x)$ has integer coefficients and leading coefficient~1.
Computing the greatest common divisor and dividing polynomials can be
performed efficiently,
and so the reduction can be carried out in polynomial time.
(In the computation of the greatest common divisor, 
the intermediate expression swell 
\index{expression swell!intermediate} 
can be avoided using the techniques used in number theory.)


In the sequel we assume that the polynomial
$$ f(x)=x^n+\sum_{i=0}^{n-1}a_ix^i\in\Z[x] $$ 
we want to factor
is square-free, its coefficients are integers, and its leading 
coefficient is~1. 



The fundamental
idea of the Berlekamp-Zassenhaus algorithm is
that we  compute the irreducible factors of 
$f(x)$ modulo
$p^N$ where $p$ is a suitably chosen prime and
$N$ is large enough.
If, for instance, $p^N>2\cdot 2^{n-1}\polnorm{f}$, and
we have already computed the coefficients of a factor 
modulo $p^N$, then, 
by Mignotte's theorem, we can obtain the coefficients of a factor in $\Q[x]$.


From now on, we will also assume that $p$ is a prime such that
the polynomial $f(x)\mypmod{p}$  is square-free in 
$\F_p[x]$.
Using linear search such a prime $p$
can be found in polynomial time
(Corollary~\ref{primkov}). One can even assume 
that 
$p$ is polynomial in the bit size of $f(x)$.


The irreducible factors in  $\F_p[x]$ of the polynomial $f(x)\mypmod{p}$ 
can be found using Berlekamp's deterministic method
 (Theorem~\ref{Berlekamp1}).
Let  $g_1(x),\ldots,g_r(x)\in\Z[x]$ be polynomials, all with leading coefficient~1, 
such that
the $g_i(x)\mypmod{p}$ are the irreducible 
factors of the polynomial $f(x)\mypmod{p}$ in
$\F_p[x]$.


Using the technique 
of Hensel's lemma (Theorem~\ref{hensel-lemma}) and Corollary~\ref{hc}, 
the system $g_1(x),\ldots,g_r(x)$ can be lifted 
modulo $p^N$. 
To simplify the notation, 
we assume now that $g_1(x),\ldots,g_r(x)\in\Z[x]$ are polynomials with leading 
coefficients~1 such that
\begin{eqnarray*}
f(x)\equiv g_1(x)\cdots g_r(x)\mypmod{p^N}
\end{eqnarray*}
and the $g_i(x)\mypmod{p}$ are the irreducible factors of 
the polynomial $f(x)\mypmod{p}$
in $\F_p[x]$.

Let $h(x)\in\Z[x]$ be an irreducible factor with leading coefficient~1 
of the polynomial $f(x)$ 
in $\Q[x]$. Then there is a uniquely determined set
$I\subseteq\{1,\ldots,r\}$
for which
\begin{eqnarray*}
h(x)\equiv \prod_{i\in I}g_i(x)\mypmod {p^N}\koz .
\end{eqnarray*}
Let  $N$ be the smallest integer  such that
$p^N\geq 2\cdot2^{n-1}\polnorm{f(x)}$. 
Mignotte's bound 
shows that the polynomial 
$\prod_{i\in I}g_i(x)\mypmod {p^N}$
on the right-hand side, if its coefficients are represented by the residues with 
the smallest absolute values, 
coincides with $h$.


We found that determining the 
irreducible factors of  $f(x)$ is equivalent to finding 
minimal subsets $I\subseteq \{1,\ldots,r\}$ for which there is a 
polynomial $h(x)\in\Z[x]$ with leading coefficient~1 such that
$h(x)\equiv \prod_{i\in I}g_i(x)\mypmod {p^N}$, the absolute values of the 
coefficients of $h(x)$  
are at most 
$2^{n-1}\polnorm{f(x)}$, 
and, moreover, $h(x)$ divides $f(x)$.
This can be checked by examining 
at most $2^{r-1}$ sets $I$.
The cost of examining a single $I$ is polynomial
in the size of $f$.

To summarise, we obtained the following method to factor, in 
$\Q[x]$, 
a square-free polynomial $f(x)$ with integer coefficients and leading coefficient~1.




\begin{alg}{Berlekamp-Zassenhaus$(f)$\inddef{\textsc{Berlekamp-Zassenhaus}}}
1 \' $p\leftarrow$ a prime $p$ such that
$f(x)\mypmod{p}$ 
is square-free in $\F_p[x]$\\ 
\' \>
and
$p=O((n\lg n+2n \lg \polnorm{f})^2)$\\
2 \' $\{g_1,\ldots,g_r\}\leftarrow$ the irreducible factors of 
$f(x)\mypmod{p}$  
in $\F_p[x]$\\
\' \> (using Berlekamp's deterministic method)\\
3 \' $N\leftarrow \lfloor\log_p(2^{\fok f}\cdot\polnorm{f})\rfloor+1$
\algnewpage
4 \' $\{g_1,\ldots,g_r\}\leftarrow$ the Hensel lifting 
of the system $\{g_1,\ldots,g_r\}$
\index{Hensel lifting} modulo $p^N$\\ 
5 \' ${\cal I}\leftarrow$ the collection of minimal subsets $I\neq \emptyset$ 
of $\{1,\ldots r\}$ 
such that\\
\' \> $g_I\leftarrow \prod_{i\in I}g_i$ reduced  modulo $p^N$ divides
$f$\\
6 \' \key{return} $\{\prod_{i\in I}g_i\,:\,I\in{\cal I}\}$
\end{alg}





\begin{tetel}
Let $ f(x)=x^n+\sum_{i=0}^{n-1}a_ix^i\in\Z[x]$ 
be a square-free polynomial with integer coefficients and leading 
coefficient~$1$, and let $p$ be a prime number such that
the polynomial $f(x)\mypmod{p}$  is square-free
in $\F_p[x]$ and 
$p=O((n\lg n+2n \lg \polnorm{f})^2)$. 
Then the irreducible factors of the polynomial $f$ in $\Q[x]$
can be obtained by the Berlekamp-Zassenhaus algorithm.
The cost of this algorithm is polynomial in $n$, $\lg \polnorm{f(x)}$ and $2^r$ where $r$ is the number of irreducible factors of the polynomial
$f(x)\mypmod{p}$ in $\F_p[x]$.
\end{tetel} 


\begin{pelda}{(Swinnerton-Dyer polynomials)}
\nevindex{Swinnerton-Dyer, Peter}
\label{SwD-pl}
Let
\begin{equation*}
f(x)=\prod (x\pm \sqrt{2} \pm\sqrt{3} 
\pm \cdots \pm \sqrt{p_l})\in\Z[x]\koz ,
\end{equation*}
where $2, 3, \ldots ,p_l$ are the first  $l$ prime numbers, and the 
product is taken over all possible
$2^l$  combinations of the signs $+$ and $-$.  The degree of $f(x)$
is $n=2^l$, and one can show that it is irreducible in $\Q[x]$.
On the other hand, for all primes $p$,
the polynomial 
$f(x)\mypmod{p}$ is the product of factors with degree at most~2. 
Therefore these polynomials represent hard cases 
for the Berlekamp-Zassenhaus algorithm, 
as 
we need to examine about $2^{n/2-1}$  sets $I$ to find out that $f$ is irreducible.
\end{pelda}


\subsection{The LLL algorithm}
\inddef{LLL algorithm!for factoring polynomials}

Our goal in this section is to present the
Lenstra\nevindex{Lenstra, Hendrik Willem, Jr.}-Lenstra\nevindex{Lenstra, 
Arjen Klaas}-Lov�sz\nevindex{Lov�sz, L�szl�} algorithm
(LLL algorithm) for factoring polynomials $f(x)\in \Q[x]$.
This was the first polynomial time method for solving the polynomial factorisation
problem over $\Q$. Similarly to the
Berlekamp-Zassenhaus method, the
LLL algorithm starts with a factorisation of 
$f$ modulo $p$ and then uses 
Hensel lifting.\index{Hensel lifting} 
In the final stages of the work, it uses lattice reduction
\index{lattice reduction} 
to find a proper divisor of $f$, provided one exists. The powerful idea of the LLL algorithm is that 
it replaced the search, which may have exponential complexity,  in the 
Berlekamp-Zassenhaus algorithm
by an efficient lattice reduction.

Let $ f(x)\in \Z[x]$ be a square-free polynomial with 
leading coefficient~1 such that $\fok f=n>1$,  
and let $p$ be a prime such that
the polynomial $f(x)\mypmod{p}$  is square free in
$\F_p[x]$ and 
$p=O((\lg n+2n \lg \polnorm{f})^2)$.
\begin{lemma}
\label{lll-factor-lm}
Suppose that
$f(x)\equiv g_0(x)v(x)\mypmod{p^N}$ where
$g_0(x)$ and $v(x)$ are polynomials with integer coefficients and leading 
coefficient~$1$.
Let $g(x)\in \Z[x]$ with $\fok g(x)=m<n$ and assume that
$g(x)\equiv g_0(x)u(x)\mypmod{p^N}$ for some polynomial
$u(x)$ such that $u(x)$ has integer coefficients and 
$\fok u(x)=\fok g(x)-\fok g_0(x)$. 
Let us further assume that $\polnorm{g(x)}^n\polnorm{f(x)}^m<p^N$. 
Then
$\lnko(f(x),g(x))\neq 1$ in $\Q[x]$.
\end{lemma}
\begin{biz}
Let $d=\deg v(x)$. By the assumptions,
\begin{eqnarray*}
f(x)u(x)\equiv g_0(x)u(x)v(x)
\equiv g(x)v(x)\mypmod{p^N}\koz .
\end{eqnarray*}
Suppose that $u(x)=\alpha_0+\alpha_1x+\ldots+\alpha_{m-1}x^{m-1}$ and 
$v(x)=\beta_0+\beta_1x+\ldots+\beta_{n-1}x^{n-1}.$
(We know that $\beta_d=1$. If $i>d$, then $\beta_i=0$,
and similarly, if $j>\deg u(x)$, then $\alpha_j=0$.)
Rewriting the congruence, we obtain
\begin{eqnarray*}
x^dg(x)+\sum_{j\neq d}\beta_jx^jg(x)
-\sum_i\alpha_ix^if(x)\equiv 0 \mypmod{p^N}\koz .
\end{eqnarray*}
Considering the coefficient vectors of the polynomials $x^jg(x)$ and $x^if(x)$,
this congruence amounts to saying 
that adding to the $(m+d)$-th row of the Sylvester matrix
(\ref{res-matrix-eq}) 
a suitable linear combination of the other  rows 
results in a row in which all the elements are
divisible by $p^N$. 
Consequently, 
$\det M\equiv 0\mypmod{p^N}$. The
Hadamard inequality\index{Hadamard inequality} 
(Corollary~\ref{hadamard}) yields that
$|\det M|\leq \polnorm{f}^m\polnorm{g}^n<p^N$,
but this can only happen if $\det M=0$. However,
$\det M=Res(f(x),g(x))$, and so, by~(\ref{res-eq}), 
$\lnko(f(x),g(x))\neq 1$.
\end{biz}


\subsubsection{The application of lattice reduction.}\index{lattice reduction} Set
\begin{equation*}
N=\lceil \log_p (2^{2n^2}\polnorm{f(x)}^{2n})\rceil
= O(n^2+n\lg \polnorm{f(x)}) \koz .
\end{equation*}
Further, we let $g_0(x)\in\Z[x]$ be a polynomial with leading coefficient~1
such that $g_0(x)\mypmod{p^N}$ is an irreducible factor of
$f(x)\mypmod{p^N}$. Set
$d=\deg g_0(x)<n$.
Define the set $L$ as follows:
\begin{equation} \label{L-definition}
L=\{g(x)\in\Z[x]:~\fok g(x)\leq n-1,\;
\exists h(x)\in \Z[x], \mbox{ with } g\equiv hg_0
\mypmod{p^N}
\}\koz .
\end{equation}

Clearly, $L$ is closed under addition of polynomials.
We identify a polynomial with degree less than $n$ with its coefficient vector 
of length  $n$.
Under this identification, 
$L$ becomes a lattice\index{lattice} in $\R^n$.
Indeed, it is not too hard to show (Exercise~\ref{racs-bazis}) that the 
polynomials
\begin{equation*}
p^N1,p^Nx,\ldots,p^Nx^{d-1},
\,g_0(x),xg_0(x),\ldots,x^{n-d-1}g_0(x)\koz,
\end{equation*}
or, more precisely, their coefficient vectors, form a basis of $L$.
\index{basis!of a lattice}


\begin{tetel} \label{LLL-korrekt}
Let $g_1(x)\in\Z[x]$ be a polynomial with degree less than $n$ such that
the coefficient vector of $g_1(x)$ is the first element in a Lov�sz-reduced basis of $L$.
\index{basis!of a lattice!reduced} 
Then $f(x)$ is irreducible in $\Q[x]$ if and only if
$\gcd(f(x),g_1(x))=1$.
\end{tetel}
\begin{biz}
As $g_1(x)\neq 0$,  it is clear that
$\gcd(f(x),g_1(x))=1$ whenever $f(x)$ is irreducible. 
In order to show the implication in the other direction, let us assume that
$f(x)$ is reducible
and let $g(x)$ be a proper divisor of $f(x)$ such that
$g(x)\mypmod{p}$ is divisible by $g_0(x)\mypmod{p}$
in $\F_p[x]$. Using Hensel's lemma\index{Hensel's lemma} 
(Theorem~\ref{hensel-lemma}),
we conclude that
$g(x)\mypmod{p^N}$ is divisible by $g_0(x)\mypmod{p^N}$, that is, 
$g(x)\in L$. Mignotte's theorem\index{Mignotte's theorem} 
(Theorem~\ref{mignotte})
shows that
\begin{equation*}
\polnorm{g(x)}\leq2^{n-1}\polnorm{f(x)}\koz . 
\end{equation*}
Now, if we use the properties
of reduced bases
(second assertion of Theorem~\ref{LLL-main}), 
then we obtain
\begin{equation*}
\polnorm{g_1(x)}\leq 2^{(n-1)/2}\polnorm{g(x)}
<2^n\polnorm{g(x)}\leq 2^{2n}\polnorm{f(x)}\koz ,
\end{equation*}
and so
\begin{equation*}
\polnorm{g_1(x)}^n\polnorm{f(x)}^{\fok g_1}
\leq
\polnorm{g_1(x)}^n\polnorm{f(x)}^n
<
2^{2n^2}\polnorm{f(x)}^{2n}
\leq p^N\koz . 
\end{equation*}
We can hence apply Lemma~\ref{lll-factor-lm},
which gives  $\gcd(g_1(x),f(x))\neq 1$.
\end{biz}



Based on the previous theorem, the LLL algorithm can be outlined as follows 
(we only give a version for factoring to two factors).
The input is a square-free 
polynomial $ f(x)\in \Z[x]$ with integer coefficients and 
leading coefficient~1 such that $\fok f=n>1$.

\begin{algN}{LLL-Polynomial-Factorisation$(f)$\inddef{\textsc{LLL-Polynomial-Factorisation}}}
1 \' $p\leftarrow$ a prime $p$ such that $f(x)\mypmod{p}$ 
is square-free in $\F_p[x]$\\ 
\' \>
and $p=O((n\lg n+2n \lg \polnorm{f})^2)$\\
2 \' $w(x)\leftarrow$
an irreducible factor $f(x)\mypmod{p}$ in
$\F_p[x]$\\
\' \> 
(using Berlekamp's deterministic method)\\
3 \' \key{if} \= $\deg w=n$ \\
4 \'          \> \key{then} \= \key{return} "irreducible"\\
5 \'          \> \key{else} \> $N\leftarrow \lceil \log_p ((2^{2n^2}\polnorm{f(x)}^{2n})\rceil
=O(n^2+n\lg(\polnorm{f(x)})$\\
6 \'          \>            \> $(g_0,h_0)\leftarrow\index{Hensel lifting} \textsc{Hensel-Lifting}(f,w,f/w\mypmod{p},p,N)$\\
7 \'          \>            \> $(b_1,\ldots,b_n)\leftarrow$ a basis of the lattice $L\subseteq \R^n$ in (\ref{L-definition})\\
8 \'          \>            \> $(g_1,\ldots,g_n)\leftarrow\textsc{Lov�sz-Reduction}(b_1,\ldots,b_n)$\\
9 \'          \>            \> $f^*\leftarrow \lnko(f,g_1)$\\
10 \'         \>            \> \key{if} \= $\fok f^*>0$ \\
11 \'         \>            \>          \> \key{then} \= \key{return} $(f^*,f/f^*)$\\
12 \'         \>            \>          \> \key{else} \> \key{return} "irreducible"
\end{algN}

\begin{tetel} 
Using the LLL algorithm, 
the irreducible factors in $\Q[x]$ of a polynomial $f\in \Q[x]$
can be obtained deterministically in polynomial time.
\end{tetel}
\begin{biz}
The general factorisation problem, using the method introduced at the 
discussion of
the Berlekamp-Zassenhaus procedure,
can be reduced to the case in which the polynomial
$f(x) \in \Z[x]$
is square-free and has leading coefficient~1. 
By the observations made there, the steps in
lines 1--7 can be performed in polynomial time.
In line~8, the Lov�sz reduction can be carried out efficiently
(Corollary~\ref{lovasz-kov}). In line~9, we may use a modular version
of the Euclidean algorithm
to avoid intermediate expression swell (see Chapter~\ref{chapter:CompAlg}).

The correctness of the method is asserted by Theorem~\ref{LLL-korrekt}. 
The LLL algorithm can be applied repeatedly to factor the polynomials 
in the output, 
in case they are not already irreducible.
\end{biz}

One can show that the Hensel lifting costs
$O(Nn^2)=O(n^4+n^3\lg \polnorm{f})$ operations with moderately sized integers.
The total cost of the version of the LLL algorithm above is
$O(n^5\lg(p^N))=O(n^7+n^6\lg \polnorm{f})$.

\begin{gyak}
\ujgyak \label{diszkrimin} 
Let $\F$ be a field and let $0\neq f(x)\in \F[x]$. The 
polynomial $f(x)$ has no irreducible factors with multiplicity greater than one if 
and only if $\lnko(f(x),f'(x))=1$. 
\textit{Hint.} In one direction, one can use Lemma~\ref{többes}, and
use Lemma~\ref{egyszeres} in the other.
\vspace{-4mm}
\ujgyak\label{racs-bazis} 
Show that the polynomials
\begin{equation*}
p^N1,p^Nx,\ldots,p^Nx^{d-1},
\,g_0(x),xg_0(x),\ldots,x^{n-d-1}g_0(x)
\end{equation*}
form a basis of the lattice in~(\ref{L-definition}).\index{basis!of a lattice} 
\textit{Hint.} It suffices to show that the polynomials
$p^Nx^j$ ($d\leq j<n $) can be expressed 
with the given polynomials.
To show this, divide $p^Nx^j$ by $g_0(x)$ and compute the 
remainder.
\end{gyak}

\begin{fld}
\ujfld{The trace in finite fields\felindex{trace!in a finite field}}
{Let $\F_{q^k}\supseteq \F_q$ be finite fields. 
The  definition of the trace map  $tr=tr_{k,q}$ on $\F_{q^k}$ is as follows:
if $\alpha\in \F_{q^k}$ then
$$ tr(\alpha)=\alpha+ \alpha^q+\cdots +\alpha^{q^{k-1}} \koz . $$
\vspace{-4mm}
\begin{description}
\item[\textit{a.}]
Show that the map $tr$ is
$\F_q$-linear\felindex{linear mapping} and its image\felindex{image} 
is precisely $\F_q$. 
\textit{Hint.} 
Use the fact that $tr$ is defined using a 
polynomial with degree $q^{k-1}$ to show that $tr$ is not identically zero.
\item[\textit{b.}] Let $(\alpha, \beta)$ be a uniformly distributed random
pair of elements from 
$\F_{q^k}\times \F_{q^k}$. Then the probability that 
$tr(\alpha)\neq tr(\beta)$ is $1 - 1/q$.
\end{description}  
}
\vspace{-4mm}
\ujfld{\label{CZalg2-fld}The Cantor-Zassenhaus algorithm for fields of characteristic~2
\felindex{Cantor-Zassenhaus algorithm!in characteristic~2}}
{Let $\F=\F_{2^m}$ and let  $f(x)\in \F[x]$ be a polynomial of the form
\begin{equation} \label{felbCZ}
f=f_1f_2\cdots f_s,
\end{equation}
where the $f_i$ are pairwise relatively prime and irreducible polynomials
with degree $d$ in $\F[x]$. Also assume that $s\geq 2$. 

\begin{description}
\item[\textit{a.}]  Let $u(x)\in\F[x]$ 
be a uniformly distributed random polynomial 
with degree less than $\fok f$. Then 
the greatest common divisor
$$\lnko(u(x)+u^2(x)+\cdots + u^{2^{md-1}}(x) ,f(x))$$ 
is a proper divisor of $f(x)$ with probability at least $1/2$.

\textit{Hint.} Apply the previous exercise taking
$q=2$ and $k=md$, and follow the argument in
Theorem~\ref{cz-split-thm}. 
\item[\textit{b.}]  
Using part~(a),  
give a randomised polynomial time method 
for factoring a polynomial of the form~(\ref{felbCZ}) over $\F$. 
\end{description}
}
\vspace{-4mm}
\ujfld{Divisors and zero divisors\index{zero divisor}}
{Let $\F$ be a field. The ring 
$R$ \index{ring}
is said to be an $\F$-\ki{algebra}\inddef{algebra} 
(in case $\F$ is clear from the context,  $R$ is simply called an 
algebra), if $R$ is a vector space
\felindex{vector space} over $\F$, and
$(ar)s=a(rs)=r(as)$ holds for all $r,s\in S$ and $a\in \F$. 
It is easy to see that 
the rings $\F[x]$ and $\F[x]/(f)$ are $\F$-algebras.

Let $R$ be a finite-dimensional $\F$-algebra. 
For an arbitrary  $r\in R$, we may consider
the map $L_r:R\rightarrow R$ defined as  $L_r(s)=rs$ for
$s\in  R$. The map $L_r$ is $\F$-linear,
\index{linear mapping} and so we may speak about its minimal polynomial
$m_r(x)\in \F[x]$,\index{minimal polynomial} its characteristic polynomial
$k_r(x)\in \F[x]$,
\felindex{characteristic polynomial} and its trace $Tr(r)=Tr(L_r)$.
\felindex{trace!of a linear mapping} In fact, if  $U$ is an ideal in \index{ideal} 
$R$, then $U$ is an invariant subspace
\felindex{subspace!invariant} of $L_r$, and so we can restrict
$L_r$ to $U$, and we may consider 
the minimal polynomial, the characteristic polynomial, and the trace of the restriction.

\begin{description}
\item[\textit{a.}] Let $f(x),\ g(x)\in \F[x]$ with $\fok f >0$.  
Show that the residue
class $[g(x)]$ is a zero divisor in the ring $\F[x]/(f)$  if and only if 
$f$ does not divide $g$ and $\gcd(f(x),g(x))\neq 1.$  

\item[\textit{b.}] Let  $R$ be an algebra over $\F$, 
and let $r\in R$ be an element with  minimal polynomial $f(x)$. 
Show that if $f$ is not irreducible over $\F$, then $R$ contains a zero 
divisor.
To be precise,
if $f(x)=g(x)h(x)$ is a non-trivial factorisation ($g,h\in \F[x]$), 
then $g(r)$ and  $h(r)$ form a pair of zero divisors,  
that is, both of them are non-zero, but their product is zero.
\end{description}
}
\vspace{-4mm}
\ujfld{Factoring polynomials over algebraic number fields}
{\begin{description}
\vspace{-4mm}
\item[\textit{a.}] Let $\F$ be a field with characteristic zero
and let $R$ be a finite-dimensional 
$\F$-algebra with an identity element.\index{algebra} 
Let us assume that 
$R=S_1\oplus S_2$ where $S_1$  and  $S_2$ are non-zero
$\F$-algebras. Let $r_1,\ldots ,r_k$ be a basis of $R$ over
$\F$.\index{basis!of a vector space} Show that
 there is a $j$ such that $m_{r_j}(x)$ is not irreducible in $\F[x]$.

\textit{Hint.} 
This exercise is for readers who are familiar with the elements
of linear algebra.
Let us assume that the minimal polynomial of $r_j$
\felindex{minimal polynomial} is the irreducible polynomial
$m(x)=x^d-a_1x^{d-1}+\cdots +a_d$. Let 
$k_i(x)$ be the characteristic 
polynomial of $L_{r_j}$\felindex{characteristic polynomial} on the invariant
subspace
$U_i$ (for $i\in\{1,2\}$).
Here $U_1$ and $U_2$ are the sets of elements of the form 
$(s_1,0)$ and $(0,s_2)$, respectively where
$s_i\in S_i$. Because of our conditions, we can find suitable
exponents $d_i$ such that
$k_i(x)=m(x)^{d_i}$. This implies that the trace $T_i(r_j)$ of 
the map $L_{r_j}$  on the subspace
$U_i$ 
is $T_i(r_j)=d_ia_1$. Set  $e_i=\dim _{\F}U_i$. Obviously,
$e_i=d_id$, which gives $ T_1(r_j)/e_1=T_2(r_j)/e_2$. 
If the assertion of the exercise is false,
then the latter equation holds for all $j$, 
and so, as the trace is linear, 
\felindex{trace!of a linear mapping} 
it holds for all $r\in R$.
This, however, leads to a contradiction:
if $r=(1,0)\in S_1\oplus S_2$ (1 denotes 
the unity in $S_1$), then clearly
$T_1(r)=e_1$ and $T_2(r)=0.$
\newpage
\item[\textit{b.}] Let 
$\F$  be an \ki{algebraic number field,}\index{algebraic number field}
that is, a field of the form $\Q(\alpha)$ where
$\alpha\in \C,$ and there is an irreducible polynomial
\index{polynomial!irreducible} $g(x)\in \Z[x]$ such that
$g(\alpha)=0$.  Let $f(x)\in  \F[x]$ 
be a square-free polynomial \index{polynomial!square-free} and
set $R=\F[x]/(f)$. Show that $R$  is a finite-dimensional algebra over
\index{algebra} $\Q$. 
More precisely,
if $\fok g=m$ and $\fok f =n,$ then the elements of the form 
$\alpha^i [x]^j$ 
($0\leq i< m$, $0\leq j< n$) form a basis 
\index{basis!of a vector space} over $\Q$.
\item[\textit{c.}] Show that if 
$f$ is reducible over  $\F$, then there are 
$\Q$-algebras $S_1,\ S_2$ 
such that $R\cong S_1\oplus S_2$. 

\textit{Hint.} 
Use the Chinese remainder theorem
\index{Chinese remainder theorem!for polynomials}.
\item[\textit{d.}] Consider the polynomial 
$g$ above and suppose that  a field $\F$ and a polynomial $f\in \F[x]$ are given.
Assume, further, that $f$ is square-free and is not irreducible
over $\F$. The polynomial
$f$ can be factored to the product of two non-constant polynomials in polynomial time.


\textit{Hint.} By the previous remarks, the minimal polynomial $m(y)$ over $\Q$  of 
at least one of the elements $\alpha^i [x]^j$ ($0\leq i\leq m$, $0\leq j\leq n$) is not irreducible in $\Q[y]$.
Using the  LLL algorithm, $m(y)$ can be factored
\felindex{LLL algorithm!for factoring polynomials} 
efficiently in $\Q[y]$. 
From a factorisation of $m(y)$, a zero divisor of $R$
can be obtained, and this can be used 
to find a proper divisor of $f$ in $\F[x]$.
\end{description}
}
\end{fld}

\begin{fejmegj}
The abstract algebraic concepts discussed in this chapter
can be found in many textbooks; see, for instance,
Hungerford's\nevindex{Hungerford, Thomas W.} book~\cite{Hungerford90}. 


The theory of finite fields and the related algorithms  are the theme
of the excellent 
books by Lidl\nevindex{Lidl, Rudolf} and
Niederreiter\nevindex{Niederreiter, Harald}~\cite{Lidl-Niederreiter86}
and Shparlinski\nevindex{Shparlinski, Igor E.} \cite{Shparlinski99}.


Our main algorithmic topics,
namely the factorisation of polynomials and lattice reduction 
are thoroughly treated 
in the book by von zur Gathen\nevindex{Gathen, Joachim von zur} 
and Gerhard\nevindex{Gerhard, J�rgen} 
\cite{Gathen-Gerhard99}. 
We recommend the same book to the readers who are interested in the efficient
methods to solve the basic problems concerning polynomials.
Theorem~8.23 of that book estimates the cost of 
multiplying polynomials by the 
Sch�nhage\nevindex{Sch�nhage, Arnold}-Strassen\nevindex{Strassen,
Volker} method, while Corollary~11.6 is concerned with the cost of the 
asymptotically fast implementation of the Euclidean algorithm.
Ajtai's result about shortest lattice vectors was published in 
\cite{Ajtai98}.



The method by Kaltofen\nevindex{Kaltofen, Erich L.} and
Shoup\nevindex{Shoup, Victor J.} is a randomised algorithm for factoring 
polynomials over finite fields, and currently 
it has one of the best time bounds among the known algorithms.
The expected number of $\F_q$-operations in this algorithm is
$O(n^{1.815}\lg q)$ where $n=\fok f$. 
Further competitive methods were suggested by 
von zur Gathen\nevindex{Gathen, Joachim von zur} 
and 
Shoup\nevindex{Shoup, Victor J.}, and also by Huang and Pan.
\nevindex{Huang, Ming-Deh}\nevindex{Pan, Victor Y.}
The number of operations required by the latter is
$O(n^{1.80535}\lg q)$, if $\lg q< n^{0.00173}.$ 
Among the deterministic methods, the one by 
von zur Gathen\nevindex{Gathen, Joachim von zur} 
and Shoup\nevindex{Shoup, Victor J.} 
is the current champion. Its cost is
$\widetilde{O}(n^2+n^{3/2}s+n^{3/2}s^{1/2}p^{1/2})$ operations
in $\F_q$ where $q=p^s.$ 
An important related problem is constructing the field 
$\F_{q^n}$. The fastest randomised method is by Shoup.\nevindex{Shoup, Victor J.}
Its cost is $O{\sim}(n^2+n\lg q).$  
For finding a square-free factorisation, 
Yun\nevindex{Yun, David Y. Y.} gave an algorithm that requires
${\widetilde O}(n)+O(n \lg(q/p))$ field operations in $\F_q$.

The best methods to solve the problem of lattice reduction and that of 
factoring polynomials over the rationals use modular and numerical techniques.
After slightly modifying the definition of reduced bases,  
an algorithm using ${\widetilde O}(n^{3.381}\lg^2 C)$ \textit{bit operations}
for the former problem 
was presented by
Storjohann.\nevindex{Storjohann, Arne} 
(We use the original definition introduced in the paper by
Lenstra\nevindex{Lenstra, Hendrik Willem, Jr.}, Lenstra\nevindex{Lenstra, Arjen
Klaas} and Lov�sz\nevindex{Lov�sz, L�szl�} \cite{Lenstra-Lenstra-Lovasz82}.)
We also mention
Sch\"onhage's\nevindex{Sch\"onhage, Arnold} method using
$\widetilde{O}(n^6+n^4\lg^2 l)$ bit operations for factoring polynomials with
integer coefficients ($l$ is the length of the coefficients). 

Besides factoring polynomials with rational coefficients, 
lattice reduction can also be used to solve lots of other problems:
to break knapsack cryptosystems and random number generators based on
linear congruences, simultaneous Diophantine approximation, to
find integer linear dependencies among real numbers (this problem
plays an important r\^ole in experiments that attempt to find mathematical
identities). These and other related problems are discussed in the 
book~\cite{Gathen-Gerhard99}.

A further exciting application 
area is the numerical solution of Diophantine equations.
One
can read about these developments in
in the books by Smart\nevindex{Smart, Nigel P.} \cite{Smart98} and
Ga�l\nevindex{Ga�l, Istv�n} \cite{Gaal02}.
The difficulty of finding a shortest lattice vector was verified in
Ajtai's\nevindex{Ajtai, Mikl�s} paper \cite{Ajtai98}.

Finally we remark that the practical implementations of the 
polynomial methods involving 
lattice reduction are not competitive with the implementations of the 
Berlekamp-Zassenhaus algorithm, which, in the worst case,
has exponential complexity.
Nevertheless, the basis reduction performs very well in practice: 
in fact it is usually much faster than its  theoretically proven speed.
For some of the problems in the application areas listed above, we do not
 have another useful method.

The work of the authors was supported in part by grants
NK72845 and T77476 of the Hungarian Scientific Research Fund.
\end{fejmegj}
\index{algebra|)}


