Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

For integer polynomials, FLINT is used to do the multiplication. We look at the _mul_ method since in Sage, __mul__ is used to handle coercion and then dispatches to _mul_.

sage: R.<x> = ZZ[]
sage: x._mul_??
...
cpdef RingElement _mul_(self, RingElement right):
    r"""
    Returns self multiplied by right.

    EXAMPLES::

        sage: R.<x> = PolynomialRing(ZZ)
        sage: (x - 2)*(x^2 - 8*x + 16)
        x^3 - 10*x^2 + 32*x - 32
    """
    cdef Polynomial_integer_dense_flint x = self._new()
    sig_on()
    fmpz_poly_mul(x.__poly, self.__poly,
            (<Polynomial_integer_dense_flint>right).__poly)
    sig_off()
    return x

You can do a similar check to see that FLINT's fmpq_poly_mul is used for polynomials over the rationals.

The univariate polynomials over finite fields different based on the size of the field. For example, for small primes, FLINT is used:

sage: R.<x> = GF(next_prime(2^5))[]
sage: type(x)
<type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>

But for larger primes, NTL is used:

sage: R.<x> = GF(next_prime(2^64))[]
sage: type(x)
<type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_p'>

To find out the exact algorithm / heuristics used, you'll need to delve into those packages.