Re: root of polynomial over galois field


"Klueless" <klueless@xxxxxxxxxxxxxxxx> wrote in message
news:Xiqzh.16028$2m6.14791@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
"Jeremy Watts" <jwatts1970@xxxxxxxxxxx> wrote in message
news:DZnzh.5609$fa.5475@xxxxxxxxxxxxxxxxxxxxxxx
For instance taking the polynomials P1 = x^6 and P2 = 2x^3 + 2 and
dividing P1 by P2 over GF(4 = 2^2), then this clearly cant be done as
no
multiplicative inverse of the leading coefficient of P2 (that being 2)
exists in GF(4).

First, GF(p^k) is not the same as Z_{p^k}. GF(p^k) is a field
whereas Z_{p^k} is a commutative ring that is not a field. GF(p^k) and
Z_{p^k}
both have characteristic p. Your P2 = 0 in GF(4) because 2=0 in GF(4).

Ahh yes of course, but what I dont get about Galois Fields and GF(4) in
particular is though GF(4) contains 4 elements it uses only the symbols '0'
and '1'. Looking at wiki's page on this
http://en.wikipedia.org/wiki/Galois_field and towards the bottom of the page
there is an addition and multiplication table for GF(4). What are the 'A'
and 'B' symbols though?? Cant see anything there that explains their use...

For any field F, including GF(p^k), the univariate polynomial
division algorithm
on F[X], X = transcendental variable over F, always succeeds at finding
solutions
q(X) and r(X) to

a(X) = q(X)*b(X) + r(X) , degree(r(X),X) <
degree(b(X),X)

given b(X)<>0. There is no issue with the the nonzero leading coefficient
of b(X)
in field F having a multiplicative inverse. It does, because F is a
field. The
univariate gcd always exists in F[X].
Additionally, multivariate gcd always exists in F[X1,...,Xn] for
purely transcendental
extensions of a field F for algebra reasons that F[X1,...,X{n-1}] can be
completed to
its quotient field, but I don't want to step too deeply into that.
What you may "have read in Geddes,Czapor & Labahn that polynomial
division over a finite field is not always possible" refers, I believe,
to the failure
of some lifting algorithms (Hensel or CRT) employed by some multivariate
gcd algorithms for the non-univariate case. The downfall of these lifting
algorithms
is that they may run out of "lucky" field elements to choose from when the
field is too
small for the problem at hand. However, as I stated in the preceding
paragraph, the
multivariate gcd does exist. What is required is a different or modified
algorithm.
One approach is too enlarge the field F via an algebraic extension, then
work
over the larger field. This does result in more complexity and slower
field operations,
so an algorithm shouldn't try this without first attempting finding a
solution using F.







.

Relevant Pages

  • Re: python speed
    ... > DecInt's division algorithm is completely general also. ... > never claim that Python code is faster than assembler. ...
    (comp.lang.python)
  • Re: Knuths division and multiplication algorithms
    ... > newsgroups. ... >> I need Knuth's division algorithm 4.3.1 and multiplication algorithm ...
    (alt.comp.lang.learn.c-cpp)
  • Knuths division and multiplication algorithms
    ... I need Knuth's division algorithm 4.3.1 and multiplication algorithm 4.3.3 from Volume 2. ... alex DOT vinokur AT gmail DOT com ...
    (sci.math)
  • Knuths division and multiplication algorithms
    ... I need Knuth's division algorithm 4.3.1 and multiplication algorithm 4.3.3 from Volume 2. ... alex DOT vinokur AT gmail DOT com ...
    (comp.programming)
  • Re: root of polynomial over galois field
    ... multiplicative inverse of the leading coefficient of P2 ... There is no issue with the the nonzero leading coefficient of b ... Additionally, multivariate gcd always exists in Ffor purely transcendental ... What is required is a different or modified algorithm. ...
    (sci.math.symbolic)