I am following Algorithm 8.3 on p.345 of the book 'Algorithms for Computer
Algebra' by Geddes,Czapor & Labahn ('Finite Field Square-Free
Factorization'), ...
My question is, what to do if c(x)1/p is unable to be found? ie. that c'(x) =/= 0
Is c(x)^1/p always guaranteed to be able to be found??

"Jeremy Watts" <jwatts1970@hotmail.com> wrote in message
news:db_yh.2935$mn2.1484@newsfe7-win.ntli.net...
I am following Algorithm 8.3 on p.345 of the book 'Algorithms for
Computer
Algebra' by Geddes,Czapor & Labahn ('Finite Field Square-Free
Factorization'), ...
My question is, what to do if c(x)1/p is unable to be found? ie. that
c'(x) =/= 0
Is c(x)^1/p always guaranteed to be able to be found??

In my copy of the book, Line 14 reads "if c(x) =/= 1 then {" which
is just
slightly different than what you copied into your post. However, the main
item is that whenever the algorithm reaches Line 15, "c(x) <--
c(x)^(1/p)", the
c(x) will indeed always be a perfect pth power of a polynomial in
GF(q)[x],
and therefore the method of the preceding "section which explains how to
go
about finding the pth root ..." applies. Always!
Examples 8.4-8.5 may not be sufficient explanation. To help you
out,
I will step you through some iterations of the inner while loop of the
algorithm,
pointing out some facts that could lead to loop invariants and a
correctness
proof, if they were developed fully enough. At the outset,

a = product(f_k^k, k)
b = a' = sum(k*f_k'/f_k, k)*a <= Terms with p|k
vanish here.
c = gcd(a,b) = product(f_k^(k-1), p does not divide k) *
product(f_k^k, p divides k)
w = a/c = product(f_k, p does not divide k)

Here we've written "a" in the form of a squarefree factorization, the f_k
being
pairwise relatively prime. The "b" has the interesting property regarding
"p|k".
This results in "c" resembling "a", but the exponents of the f_k are
reduced by 1
iff p does not divide k. I refer you to Examples 8.4-8.5 for the concrete
examples.
In the first iteration of the while loop,

y = gcd(w,c) = product(f_k, p does not divide k and k>1)
z = f_1 <= !!!!!!
w = product(f_k, p does not divide k and k>1)
= Update to w
c = product(f_k^(k-2), p does not divide k and k>1)*product(f_k^k, p
divides k) <= Update to c

Next iteration of the while loop, z=f_2, and the "k>1" changes to "k>2".
Next
iteration of the while loop, z=f_3, and the "k>1" changes to "k>3". Etc.
The f_k
factors of w are all picked off eventually, leaving w=1 and

c = product(f_k^k, p divides k)

Here we reach the Line 14, but now we see c = product(f_k^(k/p), p divides
k)^p !
Conclusion: whenever the algorithm reaches Line 15, "c(x) <-- c(x)^(1/p)",
the
c(x) will indeed always be a perfect pth power of a polynomial in
GF(q)[x].
The book is correct, it just needed a little more elaboration.

"Jeremy Watts" <jwatts1970@hotmail.com> wrote in message
news:db_yh.2935$mn2.1484@newsfe7-win.ntli.net...
I am following Algorithm 8.3 on p.345 of the book 'Algorithms for
Computer
Algebra' by Geddes,Czapor & Labahn ('Finite Field Square-Free
Factorization'), ...
My question is, what to do if c(x)1/p is unable to be found? ie. that
c'(x) =/= 0
Is c(x)^1/p always guaranteed to be able to be found??

In my copy of the book, Line 14 reads "if c(x) =/= 1 then {" which
is just
slightly different than what you copied into your post. However, the main
item is that whenever the algorithm reaches Line 15, "c(x) <--
c(x)^(1/p)", the
c(x) will indeed always be a perfect pth power of a polynomial in
GF(q)[x],
and therefore the method of the preceding "section which explains how to
go
about finding the pth root ..." applies. Always!
Examples 8.4-8.5 may not be sufficient explanation. To help you
out,
I will step you through some iterations of the inner while loop of the
algorithm,
pointing out some facts that could lead to loop invariants and a
correctness
proof, if they were developed fully enough. At the outset,

a = product(f_k^k, k)
b = a' = sum(k*f_k'/f_k, k)*a <= Terms with p|k
vanish here.
c = gcd(a,b) = product(f_k^(k-1), p does not divide k) *
product(f_k^k, p divides k)
w = a/c = product(f_k, p does not divide k)

Here we've written "a" in the form of a squarefree factorization, the f_k
being
pairwise relatively prime. The "b" has the interesting property regarding
"p|k".
This results in "c" resembling "a", but the exponents of the f_k are
reduced by 1
iff p does not divide k. I refer you to Examples 8.4-8.5 for the concrete
examples.
In the first iteration of the while loop,

y = gcd(w,c) = product(f_k, p does not divide k and k>1)
z = f_1 <= !!!!!!
w = product(f_k, p does not divide k and k>1)
= Update to w
c = product(f_k^(k-2), p does not divide k and k>1)*product(f_k^k, p
divides k) <= Update to c

Next iteration of the while loop, z=f_2, and the "k>1" changes to "k>2".
Next
iteration of the while loop, z=f_3, and the "k>1" changes to "k>3". Etc.
The f_k
factors of w are all picked off eventually, leaving w=1 and

c = product(f_k^k, p divides k)

Here we reach the Line 14, but now we see c = product(f_k^(k/p), p divides
k)^p !
Conclusion: whenever the algorithm reaches Line 15, "c(x) <-- c(x)^(1/p)",
the
c(x) will indeed always be a perfect pth power of a polynomial in
GF(q)[x].
The book is correct, it just needed a little more elaboration.

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).

"Jeremy Watts" <jwatts1970@hotmail.com> wrote in message
news:DZnzh.5609$fa.5475@newsfe1-win.ntli.net...
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.

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??

"Jeremy Watts" <jwatts1970@hotmail.com> wrote in message
news:vQzzh.16755$Da4.80@newsfe6-gui.ntli.net...
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??

"One must be able at any time to replace points, lines and planes
with tables, chairs and beer mugs."
-- Mathematician David Hilbert

Other than stipulating that "0", "1", "A", "B" are distinct unequal
symbols in the
language, all that is required to know about "0", "1", "A", "B" is that
they satisfy
those addition and multiplication tables for GF(4). In other words, you
have the
whole of GF(4) before you and there is nothing else that it is being kept
hidden
from you. Now, you can use it and play with it. E.g. you could write a
small computer
program that knows how to evaluate any arithmetical expression in GF(4)
down
to one of the four symbols. You could prove theorems about it. E.g. from
the
tables, verify that the alleged GF(4) does indeed satisfy all the field
axioms, so
is a finite field with 4 elements. E.g. We see right away from the
multiplication table
that every nonzero element has a unique inverse.

However, going more deeply into the matters, by I suggest reading up more
on
finite fields, you will find out that GF(p^k) is essentially unique as a
finite field with
p^k elements. Any other with p^k elements is isomorphic to it.
GF(p)=Z_p,
though GF(p^k) not the same as Z_{p^k} for k>1. GF(p^k) is an algebraic
extension of GF(p)=Z_p. Hence, GF(p^k)=Z_p[A], for some A which is
algebraic
over Z_p. That means A is a root of a minimal polynomial in Z_p[X] lifted
to GF(p)[X]
-- here X is transcendental over Z_p.

If you look at the GF(4) in the URL you cite, you can verify that A^2+A+1.
So
you can think of A as the root of X^2+X+1 and GF(4)=GF(2)[A]. The B is
the
other root of X^2+X+1. Since B=A+1, if you agree to write A+1 whereever
you
now see B, there is actually no longer a need for symbol B, and the four
elements
of GF(4) are now seen to be 0, 1, A, A+1 . In general, elements of
GF(p^k)=Z_p[A],
can be represented by polynomials in A with coefficients from Z_p. The
addition
and multiplication operations in GF(p^k)=Z_p[A] may be carried out as
polynomial
addition and multiplication, reduced by the minimal polynomial for A.

jeez... thanks again for that very indepth answer I think for
simplicity's sake I'll limit the routine to GF(q) where 'q' is prime... but
I do understand now what I am misunderstanding