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