\documentclass[10pt]{article}
\usepackage{amsmath, amssymb, amsthm, amsfonts, bbm}
\usepackage{enumerate}
\DeclareMathOperator*{\argmin}{argmin}
%\usepackage{epsfig}
\begin{document}
\input{preamble.tex}
\newcommand{\bbQ}{\mathbb{Q}}
\newcommand{\bbZ}{\mathbb{Z}}
\renewcommand{\mod}{\mathrm{mod}\ }
\newcommand{\coeffs}{\mathrm{coeffs}}
\newcommand{\Res}{\mathrm{Res}}
\newcommand{\inbrace}[1]{\left \{ #1 \right \}}
\newcommand{\inparen}[1]{\left ( #1 \right )}
\newcommand{\insquare}[1]{\left [ #1 \right ]}
\newcommand{\inangle}[1]{\left \langle #1 \right \rangle}
\newcommand{\infork}[1]{\left \{ \begin{matrix} #1 \end{matrix} \right .}
\newcommand{\inmat}[1]{\begin{matrix} #1 \end{matrix}}
\newcommand{\inbmat}[1]{\begin{bmatrix} #1 \end{bmatrix}}
\newcommand{\insqmat}[1]{\insquare{\begin{matrix} #1 \end{matrix}}}
\newcommand{\inabs}[1]{\begin{vmatrix} #1 \end{vmatrix}}
\newtheorem{problem}{Problem}
\lecture{10}{Mar 9, 2015}{Madhu Sudan}{Pritish Kamath}
%%%% body goes in here %%%%
\section{Introduction}
In last class we saw Hensel Lifting and how to factorize bivariate polynomials over finite fields. In this lecture we will see how to factor univariate polynomials over $\bbQ$. Apart from the technique of Hensel lifting, another important routine in this algorithm will be the Lenstra-Lenstra-Lovasz (LLL) algorithm for obtaining an approximation for the Shortest Vector problem in lattices. A preliminary version of this algorithm was given by Gauss, which albeit works only for 2 dimensions.
%SVP is hard to approximate to within $\poly(n)$ factor. We give a $2^n$ approximation.
\section{Factorizing in $\bbQ[x]$}
Suppose we want to factorize $f \in \bbZ[X]$ which has degree $n$ and $|\coeffs(f)| \le 2^{O(n)}$ (where we define $|\coeffs(f)|$ to be the sum of absolute values of the coefficients of $f$). We can assume without loss of generality that $f$ is square-free\footnote{otherwise $\gcd(f,f')$ would have been a non-trivial factor of $f$ already}. Suppose $f = A.B$ where $A$ is irreducible. But first, we need to know that the factors of $f$ have small coefficients, otherwise we will not be able to even represent them efficiently. To this end, we have the following lemma:
\begin{lemma} \label{claim:factors_bound}
All factors $f_i$ of $f$ have $|\coeffs(f_i)| \le 2^{\poly(n)}$, where $\deg(f) \le n$ and $|\coeffs(f)| \le 2^{O(n)}$
\end{lemma}
\begin{proof}
The main idea is that all complex roots of $f$ have magnitude $\le 2^{\poly(n)}$. This is because the leading term of $f$ will dominate all the other terms if $|x| > 2^{\Omega(n)}$, and thus $f$ cannot have roots outside a certain radius around $0$. Thus, writing $g$ as $\prod_{\alpha} (x-\alpha)$ we get that $|\coeffs(g)| \le 2^{\poly(n)}$.
\end{proof}
\noindent We take an approach similar to what we did for bivariate factorization.
\begin{enumerate}[(a)]
\item We find a ``nice'' prime $p$, and polynomials $g$ and $h$ such that $f = g.h (\mod p)$ where $g$ is irreducible, monic, rel. prime to $h$ with $\deg_x(g), \deg_x(h) \ge 1$.
\item We lift $g$ and $h$ to get $f = g_t h_t (\mod p^t)$ where $g_t = g (\mod p)$ and $h_t = h (\mod p)$.
\item Find $\widetilde{A}$ s.t. $1 \le \deg(\widetilde{A}) < \deg(f)$ of minimum degree s.t. $\exists \widetilde{h}$ s.t. $\widetilde{A} = g_t . \widetilde{h} (\mod p^t)$ and $|\coeffs(\widetilde{A})| < M = 2^{\poly(n)}$
\item $\gcd(\widetilde{A}, f)$ gives a non-trivial factor of $f$.
\end{enumerate}
%Any factor of $f$ = $K \prod_{\alpha \in S} (x-\alpha)$ where $S$ is the set of roots of $f$ and $K$ is the leading coefficient.
%Uniqueness of Hensel Lifting: If $f = gh(\mod I)$, we obtain $f = g_1 h_1(\mod I^2)$ such that $g_1 = g(\mod I)$ and $h_1 = h (\mod I)$ such that if $g_2h_2 = g_1h_1(\mod I^2)$ and $g_2$, $h_2$ satisfy above conditions, then $\exists u \in I$ such that $g_1 = g_2(1-u)$ and $h_1 = h_2(1+u)$.
%[For every level of lifting for $f$, there is a consistent lifting for $A$. See Lecture 9 Madhu's notes]
\noindent Steps (a) and (b) are very natural, following bivariate factorization over finite fields. We now justify step (d). We know that $A$ is such that $|\coeffs(A)| \le M_1 = M$ (from Claim \ref{claim:factors_bound}) and $\widetilde{A}$ is such that $|\coeffs(\widetilde{A})| \le M$ and $\deg(A), \deg(\widetilde{A}) < n$. From Hensel lifting we know that there exist $h_1$ and $h_2$ such that $\alpha A = g_t h_1(\mod p^t)$ and $\beta \widetilde{A} = g_t h_2 (\mod p^t)$. And hence $\alpha A + \beta \widetilde{A} = g_t(\alpha h_1 + \beta h_2) (\mod p^t)$.\\
\noindent Suppose for contradiction that $A \!\nmid\! \widetilde{A}$. Then $R = \Res(A, \widetilde{A}) \in \bbZ$ (see Lecture 8. Also follows easily from Bezout's theorem). We have that $R < n! M^{2n} \ll p^t$ (we choose $p$ and $t$ large enough for this to hold). But then $R = g_t \widetilde{h} (\mod p^t)$ for some $\widetilde{h}$. This is a contradiction because $g_t \widetilde{h}$ is a polynomial with non-zero degree and leading coefficient less than $p^t$, but $R \in \bbZ$. Hence $A | \widetilde{A}$.\\
\noindent Thus, once we find the $\widetilde{A}$ as in Step (iii), we can get $A = \gcd(\widetilde{A}, f)$ which will be a non-trivial factor of $f$.
\section{Shortest Vector Problem: realizing Step (c)}
\begin{problem}
Given $f, g, M, p, t$, find $\widetilde{A}$ as in Step (c) of approach.
\end{problem}
\noindent We want to find $\widetilde{A}$ such that $\widetilde{A} = g.\widetilde{h} (\mod p^t)$. We think of polynomials in $\bbZ^{ 0$ such that $B_\delta(x) \cap L = \set{x}$\\
{\em additive:} $\forall x, y \in L$, $x-y \in L$
\end{definition}
\begin{problem}[Shortest vector problem]
Given a basis $v_1, \cdots, v_k \in \bbZ^k$. Find $\alpha_1, \cdots, \alpha_k$ that minimizes $\norm{\sum_{i=1}^k \alpha_i v_i}_2$
\end{problem}
\subsection{Known results about SVP}
Ajtai showed that SVP is NP-hard under randomized reductions \cite{ajtai95}. But we only need to approximate SVP here. That is, find $\alpha_1, \cdots, \alpha_k$ such that $\norm{\sum_{i=1}^k \alpha_i v_i}_2 \le \gamma(k).\beta$ where the minimum of $\norm{\sum_{i=1}^k \alpha_i v_i}_2$ is $\beta$.
In that sense, Ajtai only showed that $\gamma = 1$ is NP-hard. Daniele Micciancio (grad student at MIT then) was given Ajtai's paper to read and do something about it. He showed achieving $\gamma = \sqrt{2}$ is also NP-hard under randomized reductions \cite{micciancio01}. Further work in this area has shown that $\gamma(k) = 2^{\log^{1-\delta}(k)}$ is also `hard'. Modern Cryptography relies on the hardness of $\gamma(k) = k^{10}$ or so.
However for our purposes, it suffices to have a $\gamma$-approximation, where $\gamma = 2^k$. The Lenstra-Lenstra-Lovasz algorithm gives such an approximation in polynomial time \cite{LLL82}.
\section{Gauss's algorithm for 2-dim}
In this lecture, we will only study Gauss' algorithm which works in the two dimensional case, although the LLL algorithm can be thought of as a generalization of Gauss' algorithm.
\begin{problem}
Given vectors $v_1, v_2 \in \bbZ^2$, find $\alpha_1, \alpha_2$ minimizing $\norm{\alpha_1 v_1 + \alpha_2 v_2}_2$
\end{problem}
The algorithm is similar in flavor to Euclid's GCD algorithm. We start with two vectors $s$ and $b$, where $s$ is smaller than $b$. We repeatedly take $(s,b)$ to $(s, b' = b-s)$. The algorithm is as follows,\\
\noindent {\bf Repeat:}
\begin{itemize}
\item Set $i = \argmin_j (\norm{b-js}_2)$
\item Set $b = b - is$
\item If vertical part of $b$ has length $\le s/2$ then swap $(s,b)$.\\
Else stop and output $min(\norm{b}_2, \norm{s}_2)$.
\end{itemize}
\begin{thebibliography}{alpha}
\bibitem{ajtai95} Miklos Ajtai.
\newblock The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions
\newblock {\em STOC}, 1998.
\bibitem{micciancio01} Daniele Micciancio.
\newblock The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant.
\newblock {\em SIAM Journal of Computing}, 2001
\bibitem{LLL82} Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L.
\newblock Factoring Polynomials with Rational Coefﬁcients
\newblock {\em Mathematische Annalen}, 1982
\end{thebibliography}
\end{document}