Ask Your Question

How to find compution time require for gcd of two polynomial over prime field

asked 2017-03-03 00:05:15 -0500

this post is marked as community wiki

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 flag offensive close merge delete

1 answer

Sort by » oldest newest most voted

answered 2017-03-03 02:18:54 -0500

B r u n o gravatar image

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

    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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2017-03-03 00:05:15 -0500

Seen: 184 times

Last updated: Mar 03