Re: root of polynomial over galois field
- From: "Klueless" <klueless@xxxxxxxxxxxxxxxx>
- Date: Sat, 10 Feb 2007 20:55:19 GMT
"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).
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.
.
- Follow-Ups:
- Re: root of polynomial over galois field
- From: Jeremy Watts
- Re: root of polynomial over galois field
- References:
- root of polynomial over galois field
- From: Jeremy Watts
- Re: root of polynomial over galois field
- From: Klueless
- Re: root of polynomial over galois field
- From: Jeremy Watts
- root of polynomial over galois field
- Prev by Date: Re: root of polynomial over galois field
- Next by Date: How to do the Multiple Assignments in CAS
- Previous by thread: Re: root of polynomial over galois field
- Next by thread: Re: root of polynomial over galois field
- Index(es):
Relevant Pages
|
