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(dlog35) 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(dlog47) 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

For basic operations on elements of the fields GF(2n)[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