Hi! On 2014-05-30, kundan kumar <kundankumar2...@gmail.com> wrote: > Does sage have an implementation of Bivariate polynomial Euclid's division > algorithm?
Yes, that's known as normal form computation in commutative algebra. > In particular, I want to divide f(x) = x^p - 1 by g(x,y) = (x-y)^2 - c. > Here, p is a large prime. The division occur in F[y] / (y^7 - 1) where F is > a finite field(Z mod p).That is while applying division I don't want to > allow the power of y to increse beyond 7. First of all, let us define a polynomial ring. Note that it is a common mistake for new users of Sage to try to define a polynomial *without* creating a polynomial ring. For example, this should not be done when you want to work with g as a polynomial: sage: g(x,y) = (x-y)^2-5 sage: type(x) <type 'sage.symbolic.expression.Expression'> The result, as you can see, is a symbolic expression. Its purpose is very much different from what we need here. So, let us properly define a multi-variate polynomial ring, and as you say the coefficients are in some finite field (let us consider p=19): sage: P.<x,y> = GF(19)[] sage: g = (x-y)^2-5 sage: g x^2 - 2*x*y + y^2 - 5 sage: type(g) <type 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular'> But you actually want to do computations modulo y^7-1. So, let us define the quotient ring. Note that we have variables x and y, so, we live in F[x,y]/(y^7-1), not in F[y]/(y^7-1). sage: Q = P.quo(y^7-1) sage: Q Quotient of Multivariate Polynomial Ring in x, y over Finite Field of size 19 by the ideal (y^7 - 1) We have defined g as an element of P---let's check: sage: g.parent() is P True Hence, we should convert it to an element of the quotient ring: sage: gQ = Q(g) sage: gQ.parent() is Q True Next, let us define f as an element of the quotient ring Q. We have two possibilities: Either we rename x and y, so that they correspont to the generators of Q, or we directly define f in terms of the generators of Q, not of x,y. I assume that the two primes you are talking about are equal, since you both denote them by p. So, stick with p=19: sage: f = Q.0^19-1 sage: f xbar^19 - 1 As you can see, when defining the quotient, the variable names have been automatically changed, to distinguish elements of P from elements of Q. Back to your question: You want to "divide" f by gQ. If you naively do the division f/gQ, you'll get an error. However, what we want is a representative for the coset f+(gQ*Q). So, let us give a name to the ideal gQ*Q: sage: I = gQ*Q sage: I Ideal (xbar^2 - 2*xbar*ybar + ybar^2 - 5) of Quotient of Multivariate Polynomial Ring in x, y over Finite Field of size 19 by the ideal (y^7 - 1) Polynomial ideals provide a method ".reduce()", that reduces a given element by the Gröbner basis of the ideal---that's exactly what we need. Thus, the last step is sage: I.reduce(f) ybar^5 + xbar - ybar - 1 Actually, if you want, you could lift the result back to the non-quotiented ring P: sage: I.reduce(f).lift() y^5 + x - y - 1 Best regards, Simon -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
