On 30 May 2014 12:37, Simon King <simon.k...@uni-jena.de> wrote: > 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
Simon, that is a fantastic mini-tutorial and should be kept somewhere for posterity! (assuming the the original questioner likes it too, of course). John > > > -- > 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. -- 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.
