Ask Your Question

Polynomial division mod n

asked 2013-06-02 14:37:25 -0600

cp_sage gravatar image

updated 2013-06-02 15:25:51 -0600

Hi everyone,

Let's suppose that we are working with polynomials modulo n a composite number, for which we know the factorization (n=p*q). If we know that f(x) can be divided by e.g. g(x), what is the most efficient way to calculate f(x)/g(x) in Z_n with Sage?

Thanks for your time

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2013-06-02 21:28:44 -0600

vdelecroix gravatar image

I do not know if this is the best answer but it works

sage: K = Zmod(543)    # the ring Z/nZ
sage: R.<x> = PolynomialRing(K,'x')
sage: f = 3*x^5 + 2*x + 1
sage: g = 2*x + 1
sage: f.quo_rem(g)
(273*x^4 + 135*x^3 + 204*x^2 + 441*x + 52, 492)

The method quo_rem returns the 2-tuple made of the quotient and the remainder of the division.

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: 2013-06-02 14:37:25 -0600

Seen: 1,307 times

Last updated: Jun 02 '13