Abstract:
In this thesis, we study the Karatsuba-Ofman Algorithm (KOA), which is a
recursive multi-precision multiplication method, and improve it for certain special
applications. This thesis is in two parts.
In the first part, we derive an efficient algorithm from the KOA to multiply the
operands having a precision of 2[superscript m] computer words for some integer m. This new
algorithm is less complex and three times less recursive than the KOA. However, the
order of the complexity is the same as the KOA.
In the second part of the thesis, we introduce a novel method to perform fast
multiplication in GF(2[superscript m]), using the KOA. This method is intended for software
implementations and has two phases. In the first phase, we treat the field elements
in GF(2[superscript m]) as polynomials over GF(2) and multiply them by a technique based on
the KOA, which we call the LKOA (lean KOA). In the second phase, we reduce the
product with an irreducible trinomial or pentanomial.
The LKOA is similar to the KOA. However, it stops the recursions early and
switches to some nonrecursive algorithms which can efficiently multiply small polynomials
over GF(2). We derive these nonrecursive algorithms from the KOA, by
removing its recursions. Additionally, we optimize them, exploiting the arithmetic
of the polynomials over GF(2). As a result, we obtain a decrease in complexity, as
well as a reduction in the recursion overhead.
