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
