# How to find compution time require for gcd of two polynomial over prime field This post is a wiki. Anyone with karma >750 is welcome to improve it.

gcd(polynomial1,polynomial2) what are the operation involved in computation of above operation in SAGE math

edit retag close merge delete

Sort by » oldest newest most voted

To give a quick answer to the question in title, you can use the magic function %time or %timeit:

sage: R.<x> = GF(17)[]
sage: p = R.random_element(50)
sage: q = R.random_element(50)
sage: %timeit gcd(p,q)
100000 loops, best of 3: 12.2 µs per loop


The actual computation in my case (univariate polynomial over prime finite field) is done by Flint. I explain below how to get this information.

First, you can use gcd?? which shows you the source code. You'll find

try:
return a.gcd(b, **kwargs)


which tells you that the actual computation is p.gcd(q). Then using p.gcd??, you'll see that this method, written in the file $SAGE/src/sage/rings/polynomial/polynomial_template.pxi, use the function celement_gcd. If you open this file polynomial_template.pxi, the docstring tells us that this celement_gcd is implemented in some linkage file. Since in my case, the polynomial has type sage: type(p) <type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>  one can open the file $SAGE/src/sage/rings/polynomial/polynomial_zmod_flint.pyx where the linkage file is included:

include "sage/libs/flint/nmod_poly_linkage.pxi"


The linkage file is thus \$SAGE/src/sage/libs/flint/nmod_poly_linkage.pxi. In this file one sees that celement_gcd uses nmod_poly_gcd from Flint library. So at the end, this computation is performed by Flint.

more