% This is not TeX, it's -*- LaTeX -*- (for emacs)
\documentclass{beamer}
% Copyright by Marco Bodrato, 2007
% Released under the Creative Common 3.0 BY-NC-SA licence, available at
% http://creativecommons.org/licenses/by-nc-sa/3.0/
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{enumerate}
\usepackage{beamerthemesplit}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}

\usepackage{graphicx}
\usepackage{arydshln}

\usetheme{Copenhagen}

%%%%%% Inizio font cirillico %%%%%%
\usepackage[OT2,OT1]{fontenc}
\newcommand\cyr{%
  \renewcommand\rmdefault{wncyr}%
  \renewcommand\sfdefault{wncyss}%
  \renewcommand\encodingdefault{OT2}%
  \normalfont
  \selectfont}
\DeclareTextFontCommand{\textcyr}{\cyr} 
%%%%%%% Fine font cirillico %%%%%%%

\setlength\dashlinedash{.4pt}
\setlength\dashlinegap{1.2pt}

% oggetti matematici
\def\NN{{{\mathbb{N}}}}
\def\ZZ{{{\mathbb Z}}}
\def\RR{{{\mathbb R}}}
\def\u{{{\mathbf 1}}}
\def\N{\mathbb{N}}
\def\setZ{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\K{\mathbb{K}}
\def\F{\mathbb{F}}
\def\T{{{\cyr Toom}}}
\def\TC{\T-Cook}

\newcommand{\per}{\ensuremath{\cdot}}
\newcommand{\zsupz}[1][p]{{\ensuremath{\ZZ_{\!/\!#1\ZZ}}}}
\newcommand{\pol}[1][p]{\mathfrak{#1}}
\newcommand{\vet}[1]{\overline{#1}}
\newcommand{\hex}[1]{\mathrm{#1}}
\newcommand{\zsunz}{\zsupz[n]}
\newcommand{\zsuppz}{\zsupz[p^2]}
\newcommand{\GF}[1][2]{{\ensuremath{\mathrm{GF}\!\left(#1\right)}}}
\newcommand{\GFx}[1][2]{{\ensuremath{\GF[#1]\!\left[x\right]}}}
\newcommand{\Zx}{{\ensuremath{\setZ\left[x\right]}}}
\newcommand{\Ogr}{\mathrm{O}}
\newcommand{\opi}{\mathrm{o}}
\newcommand{\evide}[1]{\textcolor{green!70!black}{#1}}
\newcommand{\grigio}[1]{\textcolor{white!60!black}{#1}}

\begin{document}

\title[Towards optimal \TC-3 multiplication in \GFx]{Towards optimal \TC-3 multiplication}
\subtitle{for univariate binary polynomials}
\author[Marco Bodrato \ \ \ \ \ \ (0xC1A000B0)]{Marco Bodrato}
\institute{Centro ``Vito Volterra'' -- Universit\`a di Roma ``Tor Vergata'' -- Italy}

\date[WAIFI 2007]{WAIFI 2007 - June 21$^\mathrm{th}$}

\subject{Fast multiplication for long integers and binary polynomials.}
\keywords{Polynomial multiplication,
finite fields, GF2x, Toom-Cook, Karatsuba, binary polynomials, convolution}

\frame{\titlepage}
\part{Workshop on Finite Fields}
\frame[label=indice]{\tableofcontents
\hfill\hyperlink{appendices}{\beamergotobutton{see appendices}}
}

\section{A way to Toom multiplication for binary polynomials}
\frame{
  \framesubtitle{The problem}
  \frametitle{Polynomial multiplication in \GFx}
  We start from two dense binary polynomials
  $$u,v \in\GFx$$
  and we need the product
  $$w=u\cdot v \in\GFx$$

  \begin{block}{\only<1>{Assume monomial base.\vspace{.2mm}}\only<2>{Compact dense representation, each bit store a coefficient.}}
    \only<1>{
      \noindent\(
      \begin{array}{rl}
        u=\!&\!\ \ \ \ x^{d_u}\!\ldots0\cdot x^6\!+1\cdot x^5\!+1\cdot x^4\!+0\cdot x^3\!+1\cdot x^2\!+1\cdot x\!+1\\
        v=\!&\!\ \ \ \ x^{d_v}\!\ldots1\cdot x^6\!+0\cdot x^5\!+0\cdot x^4\!+0\cdot x^3\!+1\cdot x^2\!+1\cdot x\!+0\\
        \leadsto w=\!&\!x^{d_u+d_v}\!\ldots1\cdot x^6\!+1\cdot x^5\!+1\cdot x^4\!+0\cdot x^3\!+0\cdot x^2\!+1\cdot x\!+0
      \end{array}
      \)
    }
    \only<2>{
      \noindent\(
      \begin{array}{rl}
        u=&\ \ \ \ \ \ \ \ \ \ \ \ [1\ldots0110111]\\
        v=&\ \ \ \ \ \ \ \ \ \ \ \ [1\ldots1000110]\\
        \leadsto w=&[1\ldots\ldots\ldots\ldots1110010]
      \end{array}
      \)\vspace*{.35mm}
    }
  \end{block}
}
\subsection{Multiplication algorithms and complexity}
\frame{
  \frametitle{Polynomial multiplication algorithms}
  \begin{block}{Many algorithms are known for polynomial multiplication.}
    \begin{itemize}
    \item<alert@+|1-> Na\"ive \hfill $\Ogr(d^2)$
    \item<alert@+|2-> Karatsuba {\footnotesize(\T-2)} (1962)\hfill$\Ogr(d^{\log_23})$
    \item<alert@4|4-> \TC-$k$ (1963) \hfill $\Ogr(d^{\log_k2k-1})$
    \item<alert@3|3-> Sch\"onhage-FFT (1977) \hfill $\Ogr(d\log d\log\log d)$
    \end{itemize}
  \end{block}
  
  Each one has a different complexity, and a different range where it
  is the fastest.\hfill\hyperlink{threshold}{\beamergotobutton{see thresholds}}

  \begin{overprint}
    \onslide<4->{\alert<4>{\ \\Some authors say: ``\T's strategy is impossible for \GFx''.\\I say:``It is possible and practical''

}}
  \end{overprint}
}
\subsection{Toom-Cook algorithm for polynomials, revisited}
\frame[label=Toom-algo]{
  \frametitle{Recall on \T-$k$ algorithm}
  \framesubtitle{5 phases}
  \begin{enumerate}[<+-|alert@+>]
  \item Splitting\only<2->{: choose a base, homogenise}
  \item Evaluation\only<3->{: \evide{$2\times$ matrix-vector multiplication}}
  \item Multiplication\only<4->{: $(2k-1)\times$ recursive application}
  \item Interpolation\only<5->{: \evide{{\em inverse matrix}-vector multiplication}}
  \item Recomposition\only<6->{: shift and add.}
  \end{enumerate}

  \begin{block}{Phase \only<1>{1, choose a base, homogenise}\only<2>{2, some linear algebra}\only<3>{3, recursive application}\only<4>{4, some more linear algebra}\only<5>{5, last details}\evide{\only<6>{2 and 4, are critical}}
\hfill\only<1,3>{\hyperlink{unbalanced}{\beamergotobutton{see unbalanced}}}
}
    \begin{overprint}
      \only<1>{Choose a base $Y=x^b$ suitable to represent operands with $k$ parts.
        \vspace{-3.9mm}
        \[\begin{array}{rrcrlll}
          \multicolumn{2}{l}{\GFx}&\leadsto&\multicolumn{4}{r}{\GFx\left[y,z\right]}\\
          u=&[\alert{\ldots}\evide{\ldots}\ldots]&\leadsto&[\alert{\ldots}]\cdot y^2+&[\evide{\ldots}]\cdot yz&+[\ldots]\cdot z^2&=\pol[u]\\
          v=&[\alert{\ldots}\evide{\ldots}\ldots]&\leadsto&[\alert{\ldots}]\cdot y^2+&[\evide{\ldots}]\cdot yz&+[\ldots]\cdot z^2&=\pol[v]
        \end{array}
        \]
      }
      \only<2>{Evaluate polynomials $\pol[u],\pol[v]$ in $2k-1$ different
        points $(\alpha_i,\beta_i) \in\alert{\GFx^2}$, not just in \GF!

        Obtain this multiplying a (non square) Vandermonde matrix by the vector of coefficients.
      }
      \only<3>{Compute evaluation of the product by multiplying evaluations.

        $\pol[w](\alpha_i,\beta_i) = \pol[u](\alpha_i,\beta_i)\cdot\pol[v](\alpha_i,\beta_i)$

        Degree $k-1$ $\times$ degree $k-1$ $\leadsto$ degree $2k-2$.\\
        $k$ parts  $\times$ $k$ parts  $\leadsto$ $2k-1$ parts. $\Rightarrow$ $2k-1$ multiplications.\vspace*{-.15mm}
      }
      \only<4>{Interpolate to obtain coefficient of the product polynomial.

        \ 

        Obtain this multiplying the inverse of a (square) Vandermonde matrix by the
        vector of evaluations.
      }
      \only<5>{We computed the product in $\GFx\left[y,z\right]$.

        Go back to \GFx\ with an evaluation:\\
        $u\cdot v=\pol[u](Y,1)\pol[v](Y,1)=\pol[w](Y,1)=w\in\GFx$\\
        where $Y$, is the ``base'' chosen during phase 1.
      }
      \only<6>{
        Splitting order $k$ gives number ($2k-1$) of multiplication in phase~3, and asymptotic behaviour $\Ogr(d^{\log_k2k-1})$. Rigidly.

        The choice of evaluation/interpolation points \evide{and}
        operation sequences for \evide{phases 2 and 4} gives the hidden constant.
      }
    \end{overprint} 
  \end{block}
}
\subsection{Operations and costs}
\frame{
  \frametitle{Operations we count on for linear algebra}
  \begin{block}{Basic on long operands\hfill(cost)\ \ \ \ \ \ \ \;}
    \begin{itemize}
    \item Addition(Subtraction)\hfill({\tt add}) linear
    \item Mul/div by $x^n$ (optimised with shift)\hfill({\tt shift}) linear
    \item Multiplication by a ``small'' operand\hfill({\tt Smul}) linear
    \item Exact division by a ``small'' operand\hfill({\tt Sdiv}) \hyperlink{exactdivision}{linear}
    \end{itemize}
    \grigio{\footnotesize ``small'' actually means fixed: asymptotically small. Typically fits in 1 BYTE.}
  \end{block}

  \begin{block}{Composite}
    \begin{itemize}
    \item linear combination $l_i \gets (c_j\cdot l_j + c_k\cdot l_k)/d_i$, may be $i=j$ \\ $c_j,c_k,d_i$ are ``small'' constants.
    \end{itemize}
  \end{block}
}
\section{Searching for the optimal Toom-3 in $\GFx$}
\subsection{Na\"ive evaluation}
\frame{
  \frametitle{Evaluation is Matrix-vector multiplication}
  \begin{exampleblock}{After splitting, operands are quadratic polynomials}
    \vspace{-4mm}
    $$\evide{u(y,z)\!=\!U_2y^2\!+\!U_1yz\!+\!U_0z^2}, \quad U_0,U_1,U_2 \in\GFx, \deg(U_i)<b$$
  \end{exampleblock}
  \vspace{4mm}
  \begin{block}{Evaluate at 5 points: $\footnotesize\{(0,1),\ (1,1),\ (x,1),\ (x+1,1),\ (1,0)\}$}
    \vspace{-3mm}
    $$\footnotesize
    \begin{pmatrix}
      u(0,1)\\\cdashline{1-1}
      u(1,1)\\
      u(x,1)\\
      \!\!u(x+1,1)\!\\\cdashline{1-1}
      u(1,0)
    \end{pmatrix}
    \!\!=\!\!
    \begin{pmatrix}
      1&0&0\\\cdashline{1-3}
      1&1&1\\
      1&x&x^2\\
      1&\!x+1\!&\!x^2+1\!\!\\\cdashline{1-3}
      0&0&1
    \end{pmatrix}\!\!\begin{pmatrix}
      U_0\\
      U_1\\
      U_2
    \end{pmatrix}\!\!=\!\!\begin{pmatrix}
      U_0\\\cdashline{1-1}
      U_0\alert{+}U_1\alert{+}U_2\\
      U_0\alert{+}(\textcolor{green}{x})U_1\alert{+}(\textcolor{green}{x^2})U_2\\
      \!\!U_0\alert{+}\textcolor<1>{blue}{(\textcolor<2>{green}{x}\alert<2>{+}1)}U_1\alert{+}\textcolor<1>{blue}{(\textcolor<2>{green}{x^2}\alert<2>{+}1)}U_2\!\!\\\cdashline{1-1}
      U_2\\
    \end{pmatrix}$$
  
    A na\"ive implementation cost: $\alert{\only<1>6\only<2>8 \times \tt add} + \textcolor{green}{\only<1>2\only<2>4 \times \tt shift} \only<1>{ + \textcolor{blue}{2 \times \tt Smul}}$.

    \footnotesize First and last evaluations are trivial.
  \end{block}
}
\subsection{Proposed graph search}
\frame{
  \frametitle{Search a sequence of operations on matrix lines}
  \framesubtitle{Start from the ``empty'' matrix, search a path to the goal}
  \vspace{-2mm}
  \evide{No temporaries: in-place operations.}

  \vspace{.68mm}
  \(\footnotesize
  \begin{array}{ccc}
    \left(
      \begin{array}{l:rrr}
        l_{-1}&1&0&0\\
        l_{-2}&0&1&0\\
        l_{-3}&0&0&1\\\hline
        l_{1}&0&0&0\\
        l_{2}&0&0&0\\
        l_{3}&0&0&0\\\hline
      \end{array}
    \right)
    &\overset{\ l_1 \gets l_{-1}+l_{-2}\ }{\leadsto}&
    \left(
      \begin{array}{l:rrr}
        l_{-1}&1&0&0\\
        l_{-2}&0&1&0\\
        l_{-3}&0&0&1\\\hline
        l_{1}&1&1&0\\
        l_{2}&0&0&0\\
        l_{3}&0&0&0\\\hline
      \end{array}
    \right)\\
    \overset{l_1 \gets \evide{(x)}l_{-2}+\evide{(x^2)}l_{-3}}{\downarrow}&\ddots&\vdots\\
    \left(
      \begin{array}{l:rrl}
        l_{-1}&1&0&0\\
        l_{-2}&0&1&0\\
        l_{-3}&0&0&1\\\hline
        l_{1}&0&x&x^2\!\\
        l_{2}&0&0&0\\
        l_{3}&0&0&0\\\hline
      \end{array}
    \right)
    &{\overset{}{\cdots}}&
    \left(
      \begin{array}{rrr}
        1&0&0\\
        0&1&0\\
        0&0&1\\\hline
        1&1&1\\
        1&x&x^2\\
        1&x+1&x^2+1\\\hline
      \end{array}
    \right)
    \\
  \end{array}
  \)

  \vspace{1mm}
  \evide{Order of nontrivial values doesn't matter.}
}
\frame{
  \frametitle{Paths with different costs}
  \framesubtitle{even with same number of steps}
  \vspace{-2mm}
  Here two partial paths are shown.

  \vspace{1mm}
  \(\footnotesize
  \begin{array}{ccc}
    \left(
      \begin{array}{l:rrr}
        l_{-1}&1&0&0\\
        l_{-2}&0&1&0\\
        l_{-3}&0&0&1\\\hline
        l_{1}&1&1&1\\
        l_{2}&0&0&0\\
        l_{3}&0&0&0\\\hline
      \end{array}
    \right)
    &\!\overset{\!l_2 \gets l_{-2}+\alert{(x+1)}\cdot l_{-3}\!}{\leadsto}\!&
    \left(
      \begin{array}{l:rrr}
        l_{-1}&1&0&0\\
        l_{-2}&0&1&0\\
        l_{-3}&0&0&1\\\hline
        l_{1}&1&1&1\\
        l_{2}&0&1&x+1\\
        l_{3}&0&0&0\\\hline
      \end{array}
    \right)\\
    \overset{l_2 \gets \evide{(x)}l_{-2}+\evide{(x^2)}l_{-3}}{\downarrow}&&\overset{l_2 \gets \alert{(x+1)}l_{2}+l_{1}}{\downarrow}\\
    \left(
      \begin{array}{l:rrl}
        l_{-1}&1&0&0\\
        l_{-2}&0&1&0\\
        l_{-3}&0&0&1\\\hline
        l_{1}&1&1&1\\
        l_{2}&0&x&x^2\!\\
        l_{3}&0&0&0\\\hline
      \end{array}
    \right)
    &{\overset{l_2 \gets l_2+l_{1}}{\leadsto}}&
    \left(
      \begin{array}{rrr}
        1&0&0\\
        0&1&0\\
        0&0&1\\\hline
        1&1&1\\
        1&x+1&x^2+1\\
        0&0&0\\\hline
      \end{array}
    \right)
    \\
  \end{array}
  \)

  \vspace{1mm}
  Initial and final matrices coincide, but the cost is different.

}
\subsection{The algorithm found}
\frame{
  \frametitle{Optimal evaluation sequence}
  \framesubtitle{The power of recycling}
  \begin{block}{Path on the graph\ldots}
  \(\footnotesize\!
  \left(
    \begin{array}{l:rrr}
      \!\!\!l_{-1}&1\!&\!0\!&\!0\!\\
      \!\!\!l_{-2}&0\!&\!1\!&\!0\!\\
      \!\!\!l_{-3}&0\!&\!0\!&\!1\!\\\hline
      \!\!\!l_{1} &0\!&\!0\!&\!0\!\\
      \!\!\!l_{2} &0\!&\!0\!&\!0\!\\
      \!\!\!l_{3} &0\!&\!0\!&\!0\!\\\hline
    \end{array}
  \right)\!\!
  \overset{l_1 \gets l_{-1}\alert{+}l_{-2}\alert{+}l_{-3}}{\underset{l_3 \gets \evide{(x)}l_{-2}\alert{+}\evide{(x^2)}l_{-3}}{\leadsto}}\!\!
  \left(
    \begin{array}{rrl}
      \!\!\!1\!&\!0\!&\!0\!\!\!\\
      \!\!\!0\!&\!1\!&\!0\!\!\!\\
      \!\!\!0\!&\!0\!&\!1\!\!\!\\\hline
      \!\!\!1\!&\!1\!&\!1\!\!\!\\
      \!\!\!0\!&\!0\!&\!0\!\!\!\\
      \!\!\!0\!&\!x\!&\!x^2\!\!\!\!\\\hline
    \end{array}
  \right)\!\!
  \overset{l_2 \gets l_3\alert{+}l_{-1}}{\underset{l_3 \gets l_3\alert{+}l_1}{\leadsto}}\!\!
  \left(
    \begin{array}{rrr}
      \!\!\!1&0&0\!\!\!\\
      \!\!\!0&1&0\!\!\!\\
      \!\!\!0&0&1\!\!\!\\\hline
      \!\!\!1&1&1\!\!\!\\
      \!\!\!1&x&x^2\!\!\!\\
      \!\!\!1&\!\!\!x+1&\!\!\!\!x^2+1\!\!\!\\\hline
    \end{array}
  \right)
  \)
  Total cost: $\alert{5 \times \tt add} + \evide{2 \times \tt shift}$

  Na\"ive was: $\alert{8 \times \tt add} + \evide{4 \times \tt shift}$
  \end{block}

  \begin{exampleblock}{\ldots immediately translates to temporary-less evaluation sequence}
    $L_1 = U_0 + U_1 + U_2; L_3 = (x)\cdot U_2 + (x^2)\cdot U_3;$\\
    $L_2 = L_3+ U_0; L_3 = L_3 + L_1$
  \end{exampleblock}
}
\frame{
  \begin{block}{After recursive multiplication $w(\alpha,\beta)=u(\alpha,\beta)v(\alpha,\beta)$}
  \(\footnotesize
  \begin{pmatrix}
    w(0,1)\\\cdashline{1-1}
    w(1,1)\\
    w(x,1)\\
    \!\!w(x+1,1)\!\\\cdashline{1-1}
    w(1,0)
  \end{pmatrix}
  \!\!=\!\!
  \begin{pmatrix}
    1&0&0&0&0\\\cdashline{1-5}
    1&1&1&1&1\\
    1&x&x^2&x^3&x^4\\
    1&\!x+1\!&\!x^2+1\!\!&(x+1)^3&x^4+1\\\cdashline{1-5}
    0&0&0&0&1
  \end{pmatrix}\!\!\begin{pmatrix}
    W_0\\\cdashline{1-1}
    W_1\\
    W_2\\
    W_3\\\cdashline{1-1}
    W_4
  \end{pmatrix}\)
  \end{block}

  Graph search for interpolation too [ISSAC2007].

  Cost found: $9\times{\tt add} + 1\times{\tt shift} + 1\times{\tt Smul} + 2\times{\tt Sdiv}$

  Multiplication by $x^3+1$, \alert{exact divisions by $x+1, x^2+x$}.\hfill\hyperlink{exactdivision}{\beamergotobutton{see}}


  \alert{A \T-3 in \GFx\ without divisions is not possible.}

  \begin{exampleblock}{Final recomposition, doubly length coefficients}
    $\quad\quad\ [\ldots W3\ldots][\ldots W1\ldots]\quad\quad\ \ \oplus$\\
    $[\ldots W4\ldots][\ldots W2\ldots][\ldots W0\ldots] = w$
  \end{exampleblock}
}
\section{Conclusions}
\subsection{Timings}
\frame{
  \frametitle{Thresholds for NTL-based implementations}
  \hypertarget{threshold}{}
  \begin{block}{Range where each algorithm is the fastest}
    \begin{tabular}{l|rcr|r}
      Algorithm & \multicolumn{3}{c|}{operand degree (bits)}& asymptotic\\\hline
      \textcolor{blue}{Na\"ive} & &$<$&$190$&$\Ogr(d^2)$\\
      \textcolor{blue}{Karatsuba} & 190&\ldots&360& $\Ogr(d^{\log_23})$\\
      \T-$3$ &360&\ldots&8,000& $\Ogr(d^{\log_35})$\\
      \T-$4$ &8,000&\ldots&15,000& $\Ogr(d^{\log_47})$\\
      \textcolor{blue}{Sch\"onhage-FFT} &15,000&$<$& & $\Ogr(d\log d\log\log d)$
    \end{tabular}
  \end{block}

  \ 

  Those values highly depend on implementation, architecture\ldots

  \ 

  \textcolor{blue}{Algorithms in blue where implemented by \href{http://www.loria.fr/~zimmerma/irred/}{Paul Zimmermann}}
}
\subsection{More results}
\frame{
  \frametitle{What else you can find on the paper?}
  \framesubtitle{Only about 10 pages of the paper reported in this presentation}
  \begin{block}{Details skipped during presentation}
    \begin{itemize}
    \item Heuristics for graph search.
    \item Operands with very different size \hfill\hyperlink{unbalanced}{\beamergotobutton{Unbalanced}}
    \item Bivariate (and sketches on multivariate)
    \item Results for characteristic 0 ($\Zx$ and $\setZ$, + squaring)
    \end{itemize}
  \end{block}
  \begin{exampleblock}{The title of the paper is much longer!}
    \href{http://marco.bodrato.it/papers/Bodrato2007-OptimalToomCookMultiplicationForBinaryFieldAndIntegers.pdf}{Towards Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0\hfill\beamergotobutton{Download}}
  \end{exampleblock}
}

\subsection{Thanks}
\frame{
  \frametitle{That's all !}
\begin{center}
  Thank you very much for your kind attention

  \vspace{12mm}
  \alert{\Large Questions?}

  \vspace{22mm}
  \footnotesize \grigio{Presentation will be available on the web:
    \href{http://bodrato.it/papers/\#WAIFI2007}{http://bodrato.it/papers/\#WAIFI2007},\\
    released under a \href{http://creativecommons.org/licenses/by-nc-sa/3.0/}{CreativeCommons BY-NC-SA licence. \includegraphics[width=1cm]{cc.png}}\\
\
\\
    \href{http://marco.bodrato.it/papers/Bodrato2007-OptimalToomCookMultiplicationForBinaryFieldAndIntegers.pdf}{Full paper too is available on web.}}
\end{center}
}

\appendix
\part{Appendices}
\frame[label=appendices]{\tableofcontents
\hfill\hyperlink{indice}{\beamerreturnbutton{back to index}}
}

\section{More on computations}
\subsection{Exact division}
\frame[label=exactdivision]{
  \frametitle{Exact division}
  \framesubtitle{detailed only for $D=x^n+1\in\GFx$}

  We start from an element $\GFx\ni a = qD$, whose degree is
  $\deg(a)=d+n$. We want the quotient $q$. Compute with
  $2^kn\leqslant d$.

  $$q\equiv a\cdot(1+x^n)\cdot(1+x^{2n})\cdots(1+x^{2^kn}) \pmod{x^{d+1}}$$
  
  Division can be performed limb by limb starting from less
  significant one, obtaining linear complexity.
  \begin{block}{Division limb by limb obtain linear complexity}
    for $i=0\ldots d/w$\\
    $\quad a_i \gets a_i\cdot D^{-1} \pmod{x^w}$\\
    $\quad a_{i+1} \gets a_{i+1} - \frac{a_i\cdot D}{x^w} = a_{i+1} - a_i>>(w-n)$
  \end{block}

  \footnotesize \grigio{Thanks to \href{http://jjj.de/}{J\"org Arndt} for suggesting a clean description}

}
\subsection{Unbalanced multiplication}
\frame[label=unbalanced]{
  \frametitle{Splitting for unbalanced operands}
  \begin{block}{\T-2.5}
    Degree $2$ $\times$ degree $1$ $\leadsto$ degree $3$.\\
    $3$ parts  $\times$ $2$ parts  $\leadsto$ $4$ parts.
    \vspace{-4mm}
    \[\begin{array}{rrcrlll}
      \multicolumn{2}{l}{\GFx}&\leadsto&\multicolumn{4}{r}{\GFx\left[y,z\right]}\\
      u=&[\alert{\ldots}\evide{\ldots}\ldots]&\leadsto&[\alert{\ldots}]\cdot y^2+&[\evide{\ldots}]\cdot yz&+[\ldots]\cdot z^2&=\pol[u]\\
      v=&[\evide{\ldots}\ldots] &\leadsto& &[\evide{\ldots}]\cdot y &+[\ldots]\cdot z&=\pol[v]
    \end{array}
    \]
  \end{block}
  \begin{block}{Unbalanced \T-3
      \hfill\hyperlink{Toom-algo<3>}{\beamerreturnbutton{back to balanced}}
    }
    Degree $3$ $\times$ degree $1$ $\leadsto$ degree $4$.\\
    $4$ parts  $\times$ $2$ parts  $\leadsto$ $5$ parts.
    \vspace{-4mm}
    \[\begin{array}{rcrll}
      \multicolumn{1}{l}{\GFx}&\!\leadsto\!&\multicolumn{3}{r}{\GFx\left[y,z\right]}\\
      {[\textcolor{blue}{\ldots}\alert{\ldots}\evide{\ldots}\ldots]}&\!\leadsto\!&[\textcolor{blue}{\ldots}]\cdot y^3+[\alert{\ldots}]\cdot y^2z+&[\evide{\ldots}]\cdot yz^2&+[\ldots]\cdot z^3\\
      {[\evide{\ldots}\ldots]}&\!\leadsto\!&&[\evide{\ldots}]\cdot y&+[\ldots]\cdot z
    \end{array}
    \]
    \end{block}
  }
\subsection{Choice of points}
\frame[label=points]{
  \frametitle{How to choose evaluation/interpolation points}

  Points chosen for the results gives small degree increase and small
  cost for ES/IS. Different choices are possible.

  \ 

  An anonymous referee and Richard Brent suggested the use of $x^w$,
  $x^w+1$ for $w$-bits CPU. ES and IS basically remain the same.

  \ 

  When working on $\GFx[2^n]$ we are working on $\GFx_{/p}\left[X\right]$,
  so we have to choose the use of $x,x+1$ or $X,X+1$, test for any
  particular implementation.

}
\end {document}
