FLINT3.7.0-dev
/

_gr_poly_mul_toom33, gr_poly_mul_toom33

Synopsis#include <flint/gr_poly.h>
int _gr_poly_mul_toom33(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, slong len2, gr_ctx_t ctx)source
int gr_poly_mul_toom33(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, gr_ctx_t ctx)source

One level of balanced Toom-3 multiplication [Too1963; Coo1966]: evaluation at 0, 1, -1, 2, \infty with Bodrato's sequence of operations and five products of a third of the length, computed by _gr_poly_mul. Requires a commutative ring with exact division by 2 and 3; not optimised for squaring. The underscore version requires positive lengths and does not allow aliasing.

References#

  • [Too1963] A. L. Toom. The complexity of a scheme of functional elements realizing the multiplication of integers. Soviet Mathematics Doklady 3 (1963), 714–716.
  • [Coo1966] S. A. Cook. On the minimum computation time of functions. PhD thesis, Harvard University, 1966.
Cite this page

The FLINT team, “_gr_poly_mul_toom33, gr_poly_mul_toom33 (gr_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_poly/_gr_poly_mul_toom33.html (generated 2026-10-20).