Re: Math question [polynomial division]

From: Giuliano Bertoletti (gbe32241_at_libero.it)
Date: 12/31/03


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.



Relevant Pages

  • Re: I was right, surrogate factoring proof
    ... >> factor 9 via gcd. ... > There's a proof that the method does not work for primes squared. ... To prove that, mess with the algorithm. ... No, I'm not estimating anything. ...
    (sci.crypt)
  • Re: Analysis ToolPak Function in VBA is sloooow
    ... the algorithm you offered is the best performer of all the solutions offered in this thread so far. ... Thus each scenario calls Totient(and therefore GCD) 1,000,000 times. ... Even after uncommenting the debug.print statements in ATP's native GCD function, timings were in the 80's. ... Dim Remainder As Long ...
    (microsoft.public.excel.programming)
  • Re: how to rotate an array
    ... You can easily find the explanation of Euclidean algorithm on the Internet. ... gcd of original a,b values. ... > loops through the number of elements in the series, ...
    (comp.lang.cpp)
  • Re: euclidean algorithm over Q[i]
    ... Z, the Gaussian integers, may be what you remember seeing. ... written a pretty simplistic algorithm in java that carries out polynomial ... GCD, just using polynomial long division and the euclidean algorithm. ... GCD's of univariate polynomials over Q? ...
    (sci.math.symbolic)