\documentclass[10pt]{article}

\usepackage{amsfonts,algorithm,algorithmic}

\newcommand{\Vol}{\mathrm{Vol}}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

\lecture{13}{October 26, 2005}{Madhu Sudan}{Michael Manapat}

In today's lecture, we'll complete the analysis of the LLL algorithm and
finish factoring over $\Q[\mathrm{X}]$ (details will be left to the exercises).

\section{LLL Analysis}

Let $b_1,\ldots,b_n \in \Z^n$ be lattice points and let $\L(b_1,\ldots,b_n)$
be the lattice generated by $b_1,\ldots,b_n$, i.e., the set of all $\Z$-linear
combinations of $b_1,\ldots,b_n$:
\[
\L(b_1,\ldots,b_n) = \left\{ \sum_{i = 1}^n \lambda_i b_i : \lambda_i \in \Z \right\}.
\]
Our goal is to find a short vector in $\L$.

Before continuing, we recall some notational conventions:
\begin{itemize}

\item $b_i^*$ will denote the projection of $b_i$ in the direction orthogonal
	  to the subspace generated by $b_1,\ldots,b_{i - 1}$, and

\item $b_i(j)$ will denote the projection of $b_i$ to the subspace orthogonal
      to the one generated by $b_1,\ldots,b_{i - 1}$.

\end{itemize}

Note that the by the way the Gram-Schmidt orthogonalization procedure works, each
$b_i$ is a linear combination (over $\R$) of the $b_j^*$, $j \leq i$:
\[
b_i = \sum_{j = 1}^i \mu_{ij} b_j^*.
\]
The matrix $\{\mu_{ij}\}$ is then a lower-triangular matrix with $1$s on the
diagonal.

Now we can describe the LLL algorithm:

\begin{algorithm}
\begin{algorithmic}[1]
\STATE Step 1: Gram-Schmidt Reduction
\FOR{$i = 1$ to $n$}
\FOR{$j = i - 1$ to $1$}
\STATE $m \leftarrow \mathrm{round}(\mu_{ij})$
\STATE $b_i \leftarrow b_i - mb_j$
\ENDFOR
\ENDFOR
\STATE Step 2: Swap
\IF{there is an $i$ such that $\|b_i(i - 2)\| \leq \frac{3}{4}\|b_{i - 1}(i - 2)\|$}
\STATE swap $b_i$ and $b_{i - 1}$
\STATE go to Step 1
\ELSE
\STATE stop and output $b_1$
\ENDIF
\end{algorithmic}
\end{algorithm}

\subsection{LLL Potential Function}

Let $\Vol_i(b_1,\ldots,b_i)$ denote the volume of the parallelpiped formed
by the vectors $b_1,\ldots,b_i$ in Euclidean space. In the case of $n$
vectors in $n$-space, this volume is just the determinant of the matrix whose
columns are the coefficients of the $b_j$. Equivalently, this volume is the
product of the lengths of the $b_j^*$:
\[
\Vol_i(b_1,\ldots,b_i)) = \prod^i_{j = 1} \| b_j^* \|.
\]
Now we define a potential function $\Phi$ by
\[
\Phi = \prod_{i = 1}^n \Vol_i(b_1,\ldots,b_i).
\]
We can get a sense of the running time of the LLL algorithm by making the
following observations:
\begin{itemize}

\item $\Phi$ is always an integer (each $\Vol_i$ is clearly an integer, being the
determinant of an integer matrix).

\item $\Phi$ remains unchanged in step 1 of the algorithm.

\item $\Phi$ decreases by a factor of $3/4$ in step 2 if a swap is made ($\Vol_{i - 1}$
decreases by $3/4$, but all other volumes remain unchanged).

\item At the start, $\|b_i^*\| \leq n2^l$, so initially $\Phi \leq (n2^l)^{n^2}$,
i.e., $\Phi \leq 2^{\mathrm{poly}(l, n)}$.

\end{itemize}
Since the potential function is decreasing exponentially fast, and initially has a value
that is exponential in a polynomial of $l$ and $n$, we can conclude that the number
of repeated loops (i.e., the number of times steps 1 and 2 are executed) is
polynomial in $l$ and $n$.

Now we turn to the correctness of the algorithm.

\begin{lemma}
If $b_1,\ldots,b_n$, $b_1^*,\ldots,b_n^*$, and $\{\mu_{ij}\}$ as earlier satisfy
\begin{enumerate}

\item for all $i > j$, $|\mu_{ij}| \leq 1/2$, and
\item for all $i$, $\|b_i(i - 2)\| > \frac{3}{4}\|b_{i - 1}(i - 2)\|$,

\end{enumerate}
then for all nonzero vectors $v \in \L(b_1,\ldots,b_n)$, $\|b_1\| \leq 2^n\|v\|$.
\end{lemma}

\noindent Clearly the second condition in
the lemma is satisfied after the algorithm terminates (step 2 clearly
ensures this). We leave it as an easy exercise to show that the reduction
procedure in step 1 results in a matrix $\{\mu_{ij}\}$ all of whose entries
are bounded in magnitude by $1/2$. We will prove the claim in two steps.

\begin{claim}
For all $b_i$, $b_j^*$, and $v \in \L(b_1,\ldots,b_n) \setminus \{0\}$, 
$\|v\| \geq \min \{ \|b_i^*\| \}$.
\end{claim}

\begin{proof}
We can write
\[
v = \sum \lambda_i b_i = \sum \lambda_i^* b_i^*,
\]
where the $\lambda_i \in \Z$ and the $\lambda_i^* \in \R$. Since the $b_j^*$ are
orthogonal, we have
\[
\|v\|^2 = \sum |\lambda_i^*|^2 \|b_i^*\|^2,
\]
so it is enough to show that some $\lambda_i^*$ has magnitude at least 1.

Now $b_i = \sum_j \mu_{ij} b_j^*$, so
\[
v = \sum_i \lambda_i \left( \sum_j \mu_{ij} b_j^* \right),
\]
and thus
\[
\lambda_i^* = \sum_{j \geq i} \mu_{ji} \lambda_j.
\]
Let $k$ be the largest index such that $\lambda_k \neq 0$. Then
\[
\lambda_k^* = \sum_{j \geq k} \mu_{jk} \lambda_j = \mu_{kk} \lambda_k = \lambda_k.
\]
Since $\lambda_k \in \Z$, we conclue that $|\lambda_k^*| \geq 1$, whence the
desired conclusion follows.
\end{proof}

\begin{claim}
For all $i$, $\|b_i^*\| \leq 2\|b_{i + 1}^*\|$.
\end{claim}

\begin{proof}
This follows from the inequality
\[
\|b_i^*\| \geq 
	\sqrt{ \left(\frac{3}{4}\right)^2 - \left(\frac{1}{2}\right)^2 } \|b_{i - 1}(i - 2)\| \geq \frac{1}{2} \|b_{i - 1}^*\|,
\]
which one can deduce by drawing a picture of the vectors $b_i^*$ and $b_{i - 1}^*$ in the plane.
\end{proof}

\noindent Given the preceding claims, the conclusion of the lemma, and thus the correctness
of the LLL algorithm, follows easily.

\section{Factoring}

Given a polynomial $f \in \Z[X]$ of degree at most d and coefficients bounded
in magnitude by $2^n$, we find a factor of $f$ as follows:
\begin{enumerate}

\item If the greatest common divisor of $f$ and its derivative $f'$ is nontrivial,
output that factor and stop.

\item Find a prime $p$ such that the gcd of the images of $f$ and $f'$ in $\F_p[X]$
is also trivial.

\item Factor $f$ as $f = gh \pmod{p^t}$ in $\F_p[X]$, where $g$ and $h$ are monic and relatively
prime and $g$ is irreducible in $\F_p[X]$.

\item Use Hensel Lifting to find monic polynomials $G$ and $H$ such that $f = GH \pmod{p^t}$.

\item Find $\bar{g}$ and $\bar{G}$ of appropriate degree such that
$\bar{g}(X) = G(X)\bar{G}(X) \pmod{p^t}$.

\item If $\bar{g}$ and $f$ have a nontrivial gcd, output that gcd; otherwise, output
``f is irreducible.''

\end{enumerate}

\subsection{Exercises}

We conclude with a series of exercises that address the details of the above procedure:
\begin{enumerate}

\item If $f$ and $g$ are relatively prime polynomials of degree $d$, with coefficients
in the range $-c,\ldots,c$, then the resultant is bounded by $O(dc)^{O(d)}$.

\item If$f = g^* h^*$ over the integers and $g^*$ factors into irreducible polynomials
in the form $g(x)g_1(x)\cdots g_k(x) \pmod{p}$, then $g^*$ is a candidate polynomial
for the $\bar{g}$ of step 5.

\item If $f = gh$ over $\Z[X]$, with the degree of $f$ at most $d$ and the coefficients
of $f$ bounded by $2^n$, then the coefficients of $g$ are bounded by $O(d)^{O(d)} 2^n$.

\item Prove that the $g^*$ of exercise 2 divides any $\bar{g}$ reported in step 5.

\end{enumerate}

\end{document}