Re: Math question [polynomial division]
From: Giuliano Bertoletti (gbe32241_at_libero.it)
Date: Wed, 31 Dec 2003 10:03:48 GMT
On Tue, 30 Dec 2003 06:18:07 GMT, "Tom St Denis" <email@example.com>
>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
>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.