# Multiplication for balanced or unbalanced univariate binary polynomials.

## Toom-Cook 3-way for characteristic 2 polynomials

Implements the proven optimal^{[*]} evaluation
and interpolation sequences.
Toom-3 is very efficient and requires only two small divisions and some
small shifts. Recursive usage of the balanced 3x3 formula gives an
asymptotic complexity of
**O(***d*^{log35})
multiplications. Two different formulas are given, for the balanced
3x3, and the unbalanced 4x2 cases.

The Toom 3 formulas for other rings are described on the integer squaring and multiplication page.

Only *evaluation* phase differ, *interpolation* and *recomposition* are exactly the same.

**Licence:**
GNU GPL.

**Download:**
bt-3way-gf2x.gp, bt-3way-4x2-gf2x.gp.

**Reference:**
[*]*Towards Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0* by Marco Bodrato

## Toom-Cook 4-way for characteristic 2 polynomials

Implements the proven optimal^{[*]} evaluation
and interpolation sequences.
Toom-4 is efficient for large operands, and requires only four small divisions. Recursive usage of the balanced 4x4 formula gives an
asymptotic complexity of
**O(***d*^{log47})
multiplications. Only the the balanced
4x4 is given.

Toom 4 formulas for other rings are described on the integer squaring and multiplication page.

**Licence:**
GNU GPL.

**Download:**
bt-4way-gf2x.gp.

**Reference:**
[*]*Towards Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0* by Marco Bodrato

## Experimental software for GF(2)[x]

Some test implementations can be downloaded. Written by me and carefully debugged by Paul Zimmerman!

**Licence:**
GNU GPL.

**Download:**
ToomInGF2x-source-code.tbz.

**References:** [*],
necessary code: Zimmermann's irred-ntl code..

# Bivariate and Multivariate

## Waiting for publication.

Algorithm for {bi,multi}variate Toom-Cook multiplication for binary
polynomials are fully analysed on the paper[*].
Algorithms will be published some days after the conference, on this page.

You can ask for a preview copy of the paper, write to the author: Marco Bodrato
<>.

Refer to: *Towards Optimal Toom-Cook Multiplication for
Univariate and Multivariate Polynomials in Characteristic 2 and
0*, by Marco Bodrato, in C.Carlet and B.Sunar,
editors, *WAIFI'07 proceedings*, volume 4547 of *LNCS*, pages
116-133. Springer, Madrid, España, June 21-22, 2007.

For basic operations on elements of the fields **GF(2**^{n})[x], you can use the Bellezza's Binary Finite Fields Library.
# Go back

Go back to list of papers.

Go back to convolution algorithms on integers.

Marco Bodrato -
23 febbraio 2008