ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 03 Jun 2013 04:28:44 +0200Polynomial division mod nhttps://ask.sagemath.org/question/10175/polynomial-division-mod-n/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 timeSun, 02 Jun 2013 21:37:25 +0200https://ask.sagemath.org/question/10175/polynomial-division-mod-n/Answer by vdelecroix for <p>Hi everyone,</p>
<p>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?</p>
<p>Thanks for your time</p>
https://ask.sagemath.org/question/10175/polynomial-division-mod-n/?answer=14960#post-id-14960I 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.Mon, 03 Jun 2013 04:28:44 +0200https://ask.sagemath.org/question/10175/polynomial-division-mod-n/?answer=14960#post-id-14960