# Re: Math question [polynomial division]

**From:** Giuliano Bertoletti (*gbe32241_at_libero.it*)

**Date:** 12/31/03

**Next message:**Mok-Kong Shen: "Re: Fast computation of parity"**Previous message:**Foo Bar: "Re: Q: Fast computation of parity"**In reply to:**Tom St Denis: "Re: Math question [polynomial division]"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Date: Wed, 31 Dec 2003 10:03:48 GMT

On Tue, 30 Dec 2003 06:18:07 GMT, "Tom St Denis" <tomstdenis@iahu.ca>

wrote:

*>
*

*>At the end of the algorithm I've multiplied P by G to form the quotient.
*

*>Does this mean that the quotient is G times too big?
*

*>
*

Yes, but typically when you work with polynomials you don't care of

such a scaling factor which under a mathematical point of view is only

a minor nuissance. For example roots remain the same.

It's like an equation of a line or a plane. It doesn't change anything

if you multiply all vars by a constant factor != 0.

*>
*

*>---- also ---
*

*>
*

*>So far I've implemented quite a few of the basics [division for char!=0 case
*

*>only] but I'm stuck on some issues. Everything seems to work well except
*

*>for gcd and invmod. First, when computing the gcd I use the characteristic
*

*>of the destination polynomial [just easier that way]. The trouble though is
*

*>that for any g(x) in GF(p^k)[x] there are at least p GCDs since any h(x) = k
*

*>where 1 <= k < p will "divide" g(x) and produce a zero remainder.
*

The non uniquiness of the GCD derives from the same problem.

The idea is that while in Z, d=GCD(a,b) is defined as the greatest

integer which divides both a and b (this indirectly solves the problem

of choosing between +ABS(d) and -ABS(d) which apparently are both

reasonable) , in the polys domain an order is not defined and

therefore you have to elect a candidate yourself.

This is particulary evident when you work over Q (rational numbers).

So, to make a long story short, the norm is typically used to define a

GCD, which in other words means you should take the GCD with the unit

coefficient as leading one (when possible).

*>
*

*>In all cases my gcd produces results which even divide the inputs. The
*

*>question though is, is it meaningful? How do I handle the trivial cases?
*

*>Do I just merge them all into one case? I'd say the operation should be
*

*>meaninful since it's part of the definition of irreducible.
*

You have to pay attention about in which domain you're operating in.

For a finite field for example all candidates are equally good, but

since you've a unit available, normalize respect to that.

If you're working on a integral domain like Z, then use

pseudo-division. Take care however that when you switch from Z to Z[x]

you lose the order relation, so while you can normalize over Z[x], you

cannot over Z.

*>However, when I try polynomials which are irreducible such as
*

*>
*

*>x^2 + 4
*

*>
*

*>against say
*

*>
*

*>x + 1
*

*>
*

*>I get a GCD of 5 where I should expect 1 (since x^2 + 4 is irreducible over
*

*>GF(17)[x] the poly x+1 cannot divide it).
*

No, first it's 5 that should divide both x^2+4 and x+1.

Second, you are operating over a finite field and therefore the result

is correct (even if the algorithm probably selected one of the

candidates randomly) because 5 has an inverse modulo 17 and thefore

you can divide both polys (over a field, division is always defined

provided that divisor is not the null element).

The point is that you won't gain back the order relation simply

because in this case deg(5) = 0 and you landed in the ground field.

All these problem however are solved if you take the norm of the

result. In this case you multiply by inv(5) and get the unit.

Regards,

Giuliano Bertoletti.

**Next message:**Mok-Kong Shen: "Re: Fast computation of parity"**Previous message:**Foo Bar: "Re: Q: Fast computation of parity"**In reply to:**Tom St Denis: "Re: Math question [polynomial division]"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]