Re: Polynomial quotient and reminder

[Simon King]

Hi Andrea,

On 2013-04-17, Andrea Lazzarotto <andrea.l...@gmail.com> wrote:
> Hi, I am trying to work with polynomials in Finite Fields. We have to implement the Extended Euclidean Algorithm for using it with Reed Solomon Codes.
> ...
> Now my problem is that I would like to divide a by b and get bot the quotient and the reminder. All the documentation I have found online says that I have to write:
>
><pre>a.quo_rem(b)</pre>
>
> But sage says that the method doesn't exist. Can you suggest me what I am missing?

The problem is that in fact you are *not* considering two polynomials:
sage: type(a)
sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint
sage: type(b)
sage.symbolic.expression.Expression

Note that by saying
S(x) = ...
you define S as a symbolic function on a symbolic variable x, and if you
re-define x later, then the variable of S will still be symbolic, and
not belong to a polynomial ring.

Hence, b is just a symbolic expression that happens to look like a
polynomial.

I guess what you'd need to define is:
sage: m = 4
sage: k = 7
sage: n = 2^m-1
sage: f.<alpha> = FiniteField(2^m)
sage: P.<x> = f[]
# r should be defined as a polynomial, not as a symbolic function:
sage: r =
1+alpha*x+alpha^2*x^2+x^3+x^4+x^5+x^6+x^7+x^8+alpha^3*x^9+x^10+x^11+x^12+x^13+x^14;
r
x^14 + x^13 + x^12 + x^11 + x^10 + alpha^3*x^9 + x^8 + x^7 + x^6 + x^5
+ x^4 + x^3 + alpha^2*x^2 + alpha*x + 1
sage: Si = [r(alpha^i) for i in [1..8]]
# S should be defined by summing up the list elements, not as
# a symbolic function
sage: S = add([Si[i]*x^(7-i) for i in [0..7]]); S
alpha^2*x^7 + (alpha^2 + alpha + 1)*x^6 + (alpha^3 + alpha^2)*x^5 +
x^4 + (alpha^3 + alpha + 1)*x^3 + alpha^2*x^2 + x + alpha^3 + alpha +
1
sage: type(S)
sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX
sage: P2.<x> = Integers(q)[]
sage: a = x^(2*t)

But now we have a problem: b = S(x) would not work, because you work
here with the field GF(16,'alpha') on the one hand, but with the ring
Integers(16) (which contains zero devisors) on the other hand.
Multiplication between elements of the two domains is simply not
possible in a mathematically sober way.

Is working in such a strange ring with zero divisors really what you want?

If you instead define
sage: b = S
sage: x = P.gen()
sage: a = x^(2*t)

then you get

sage: a.quo_rem(b)
((alpha^3 + alpha^2 + 1)*x + alpha^3 + alpha^2,
x^6 + alpha*x^5 + (alpha^3 + alpha)*x^4 + (alpha^3 + alpha^2)*x^3 +
alpha^3*x^2 + (alpha^3 + alpha)*x + alpha^3 + alpha^2 + 1)
sage: type(a)
sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX
sage: type(b)
sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX

Is this perhaps what you wanted to do?

Best regards,
Simon

[Andrea Lazzarotto]

Hi,

The problem is that in fact you are *not* considering two polynomials:

  [...]

Note that by saying
  S(x) = ...
you define S as a symbolic function on a symbolic variable x, and if you
re-define x later, then the variable of S will still be symbolic, and
not belong to a polynomial ring.

Ok, my bad. I am still fairly new to Sage (even if I tried to submit a super small patch) and I don't completely understand what's the difference here, but I hope I will find the time to study this stuff about the types at the end of the semester.

 

Is working in such a strange ring with zero divisors really what you want? 

If you instead define

[...]

Is this perhaps what you wanted to do?

I suppose it is. At least, now my Euclidean algorithm seems to work quite correctly.

Unfortunately I am an undergraduate student in Computer Science (not even math) so there are some concepts which are still obscure to me. :P For example, what is the meaning of these two lines?

P.<x> = f[]

x = P.gen()

But the most important thing, thank you very much for helping me in solving the issue! I think you saved me a lot of time!

Best regards.

[Simon King]

Hi Andrea,

On 2013-04-17, Andrea Lazzarotto <andrea.l...@gmail.com> wrote:

>> Note that by saying
>> S(x) = ...
>> you define S as a symbolic function on a symbolic variable x, and if you
>> re-define x later, then the variable of S will still be symbolic, and
>> not belong to a polynomial ring.
>>
>
> Ok, my bad. I am still fairly new to Sage (even if I tried to submit a
> super small patch) and I don't completely understand what's the difference
> here,

A symbolic expression is something fairly general---so general that many
methods won't make sense in this generality. A symbolic expression may
contain all "strange" stuff like sin(x^2), exp(pi), x^x, etc.

In contrast, a polynomial ring is a structure that has a fixed base ring
(finite field of order 16, in your example) and has one or several
generators (x, in your example), so that *all* elements are sums of
terms of the form "element of the base ring times product of
generators". Hence, x^x is not a polynomial (the exponent must be a
natural number), there is no sin, no pi, etc.

Polynomials are of course quite useful in some branches of mathematics.
And concerning your problem: Polynomial rings over fields are Euclidean
domains, and thus there is an algorithm to compute quotient with
remainder or gcd and so on.

From computer science point of view, the mathematical algorithms are
implemented in methods of certain (base) classes. The polynomials we want
to consider here belong to classes that provide a quo_rem method. But
general symbolic expressions belong to a different class, and a quo_rem
method would make no sense for them.

In your example, a particular situation occurs: You define a and b.
While a *is* a polynomial, b is not. Hence, the method a.quo_rem
exists, but the method realises that b is no suitable input.

> Unfortunately I am an undergraduate student in Computer Science (not even
> math) so there are some concepts which are still obscure to me. :P For
> example, what is the meaning of these two lines?
>
> P.<x> = f[]

This line is a shortcut for
P = PolynomialRing(f,'x')
x = P.gen()

It is syntactical sugar: P.<x>=f[] is not valid in Python, but it is a
convenient notation well known from the Magma computer algebra system.
Hence, the Sage developers wanted to make this notation available, by
means of a pre-processor.

> x = P.gen()

As I mentioned above, a polynomial ring knows its base ring and it
generator(s). Here, we have the base ring f, which you could check by
sage: P.base_ring() is f
True

And P.gen() returns the generator (i.e., the "variable") of this
polynomial ring. Note that this "variable" is by no means the same as a
symbolic variable of the same name:

sage: x = var('x')
sage: x
x
sage: P.gen()
x
sage: type(x)
sage.symbolic.expression.Expression
sage: type(P.gen())
sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX
sage: hasattr(x, 'quo_rem')
False
sage: hasattr(P.gen(), 'quo_rem')
True

By the way, you can get the documentation of a method by appending a
question mark (and hitting return resp. shift-return in the notebook).
Hence, P.gen?<ret>

By appending two question marks, you can get the source code (in most
cases). If you start typing the name of a method and hit the tab key,
you'll get a list of all methods starting with what you typed. Hence,
P.ge<tab> will give you P.gen, P.gens, P.gens_dict, P.gens_dict_recursive,
P.get_action, P.get_action_c, P.get_action_impl, for each of which you
could then check the documentation.

Best regards,
Simon

[Andrea Lazzarotto]

2013/4/18 Simon King <simon...@uni-jena.de>

A symbolic expression is something fairly general---so general that many
methods won't make sense in this generality. A symbolic expression may
contain all "strange" stuff like sin(x^2), exp(pi), x^x, etc.

 

From computer science point of view, the mathematical algorithms are

implemented in methods of certain (base) classes. The polynomials we want
to consider here belong to classes that provide a quo_rem method. But
general symbolic expressions belong to a different class, and a quo_rem
method would make no sense for them.

Ok, I did get what was the problem about the instances of different classes, but now I have an idea of why from a mathematical POV. ;)

 

This line is a shortcut for

  P = PolynomialRing(f,'x')
  x = P.gen()

It is syntactical sugar: P.<x>=f[] is not valid in Python, but it is a
convenient notation well known from the Magma computer algebra system.
Hence, the Sage developers wanted to make this notation available, by
means of a pre-processor.

> x = P.gen()

As I mentioned above, a polynomial ring knows its base ring and it
generator(s). Here, we have the base ring f, which you could check by
  sage: P.base_ring() is f
  True

And P.gen() returns the generator (i.e., the "variable") of this
polynomial ring. Note that this "variable" is by no means the same as a
symbolic variable of the same name:

Thank you, now my ideas are more clear!

Best regards,

--
Andrea Lazzarotto — http://andrealazzarotto.com — http://lazza.dk