\documentclass{article}
\usepackage{amsmath}
\DeclareMathOperator{\len}{len}
\DeclareMathOperator{\mult}{mul^{T}}

\begin{document}

\title{Sch\"onhage-Strassen multipication for GMP-ECM}
\author{A. Kruppa}
\maketitle

\section{Transposed multiplication}
\subsection{Transposed Karatsuba}
Interpret the input vectors $A$ and $B$ of length $\len(A)$ and $\len(B)$, 
respectively, as polynomials $A(x) = \sum_{i=0}^{\len(A)-1} a_i x^i$ and
$B(x) = \sum_{i=0}^{\len(B)-1} b_i x^i$ of degree $\len(A)-1$ and $\len(B)-1$, 
respectively. Assume $4\mid \len(B)$ and let $h = \len(B)/4$. 
Set 
\begin{displaymath}
B_k = \sum_{i=0}^{h-1} b_{i+kh} x^i, \textrm{for } k = 0, 1, 2, 3, 
\end{displaymath}
that is, cut $B$ into four equal-size pieces. 
Assume $\len(A) = 2h$ or $\len(A) = 2h+1$ and set
\begin{eqnarray*}
A_0 & = & \sum_{i=0}^{h-1} a_{i} x^i, \\
A_1 & = & \sum_{i=0}^{\len(A)-h-1} a_{i+h} x^i.
\end{eqnarray*}
with $a_{2h} = 0$ if $\len(A) = 2h$.

Let $R = \mult(A, B)$ where $R$ is a polynomial of degree $\deg(R)$, i.e.
%
\begin{displaymath}
R(x) = \sum_{i=0}^{\deg(R)} r_i x^i,
\end{displaymath}
%
\begin{displaymath}
r_i = \sum_{j=0}^{\len(A)-1} a_j b_{j+i}, \textrm{for } 0\leq i \leq \deg(R).
\end{displaymath}

\pagebreak{}

Set $T(X) = \mult(A_0 + A_1, B_1 + B_2 x^h)$
so that
\begin{eqnarray*}
t_i & = & \sum_{j=0}^{h-1} (a_j + a_{j+h}) b_{j+i+h} + a_{2h} b_{i+2h} \\
    & = & \sum_{j=0}^{h-1} (a_j b_{j+i+h} + a_{j+h} b_{j+i+h}) + a_{2h} b_{i+2h} \\
& & \textrm{for } 0\leq i < h.
\end{eqnarray*}

Set $U(x) = \mult(A_0, (B_0 - B_1) + (B_1 - B_2) x^h)$
so that
\begin{eqnarray*}
u_i & = & \sum_{j=0}^{h-1} a_j (b_{j+i} - b_{j+i+h}) \\
    & = & \sum_{j=0}^{h-1} (a_j b_{j+i} - a_j b_{j+i+h}) \\
& & \textrm{for } 0\leq i < h.
\end{eqnarray*}

Set $V(x) = \mult(A_1, (B_2 - B_1) + (B_3 - B_2) x^h)$ 
so that
\begin{eqnarray*}
v_i & = & \sum_{j=0}^{h-1} a_{j+h} (b_{j+i+2h} - b_{j+i+h}) + a_{2h}(b_{i+3h} - b_{i+2h})\\
    & = & \sum_{j=0}^{h-1} (a_{j+h} b_{j+i+2h} - a_{j+h} b_{j+i+h}) + a_{2h} b_{i+3h} - a_{2h} b_{i+2h}\\
& & \textrm{for } 0\leq i < h.
\end{eqnarray*}

Let $R(x) = T(x) + U(x)$ so that
\begin{eqnarray*}
r_i & = & \sum_{j=0}^{h-1} (a_j b_{j+i+h} + a_{j+h} b_{j+i+h} + a_j b_{j+i} - a_j b_{j+i+h}) + a_{2h} b_{i+2h} \\
    & = & \sum_{j=0}^{h-1} (a_{j+h} b_{j+i+h} + a_j b_{j+i}) + a_{2h} b_{i+2h} \\
    & = & \sum_{j=0}^{2h-1} a_j b_{j+i} + a_{2h} b_{i+2h} \\
    & = & \sum_{j=0}^{\len(A)-1} a_j b_{j+i}
\end{eqnarray*}

Let $S(x) = T(x) + V(x)$ so that
\begin{eqnarray*}
s_i & = & \sum_{j=0}^{h-1} (a_j b_{j+i+h} + a_{j+h} b_{j+i+h} + a_{j+h} b_{j+i+2h} - a_{j+h} b_{j+i+h}) \\
    &   &+ a_{2h} b_{i+2h} + a_{2h} b_{i+3h} - a_{2h} b_{i+2h}\\
    & = & \sum_{j=0}^{h-1} (a_j b_{j+i+h} + a_{j+h} b_{j+i+2h}) + a_{2h} b_{i+3h} \\
    & = & \sum_{j=0}^{2h-1} a_j b_{j+i+h} + a_{2h} b_{i+3h} \\
    & = & \sum_{j=0}^{\len(A)-1} a_j b_{j+i+h}.
\end{eqnarray*}

Now set $r_{i+h} = s_i$ for $0 \leq i < h$. This way, 
$r_i = \sum_{j=0}^{len(A)-1} a_j b_{j+i}$ for $0 \leq i < 2h$, as desired.
\end{document}