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^log₃5) 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^log₄7) 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.

Ask for a copy of the paper

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.

Binary Finite Fields Library

Go back

Go back to list of papers.

Go back to convolution algorithms on integers.