Re: root of polynomial over galois field


"Klueless" <klueless@xxxxxxxxxxxxxxxx> wrote in message
news:fFezh.12276$2m6.7830@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
"Jeremy Watts" <jwatts1970@xxxxxxxxxxx> wrote in message
news:db_yh.2935$mn2.1484@xxxxxxxxxxxxxxxxxxxxxxx
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.

Hello again,

Just another question, am I right in thinking that when dividing two
polynomials over a Galois field that this is not always possible? Sorry
this may seem quite a basic question but its been a while since I did any
abstract algebra and I've forgotten nearly all of it.

What I have done is to take a standard Euclidean Division routine and
convert it to run in modular arithmetic, and use that as a means of dividing
two polynomial over GF(q). But I have discovered instances where the
routine fails, and have read in Geddes,Czapor & Labahn that polynomial
division over a finite field is not always possible, but it doesnt go in to
too much detail and also I cant seem to find anything on google about this.

None of this is surprising considering that a multiplicative inverse does
not always exist for any element in a Galois field (that is true isnt
it..?? )

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

So if this is true then am I correct in also thinking that the modular GCD
of these polynomials could not be defined either as using the Euclidean
algorithm to find it is dependent on the division of polynomials? Or is it
simply set to '1' as a default in this instance?

This all being true then how are the GCD and division calculations in
Algorithm 8.3 able to be relied upon for the case where 'q' is not prime?
Am I misunderstanding something fundamental here about abstract algebra?






.

Relevant Pages

  • Re: JSH: Resolution now possible
    ... >with the factorization ... >variable of that polynomials. ... >and do you STILL want to now argue about whether or not 7 divides off ... Even though, as required, the CONSTANT TERMS ...
    (sci.math)
  • Re: JSH: The "Published" paper he dosent what you to know about.
    ... ADVANCED POLYNOMIAL FACTORIZATION ... Determining the distribution of factors within irrational algebraic integers ... that are themselves polynomials. ... Mathematicians have decided to hold on to flawed ideas that I easily ...
    (sci.math)
  • Re: JSH: The "Published" paper he dosent what you to know about.
    ... ADVANCED POLYNOMIAL FACTORIZATION ... Determining the distribution of factors within irrational algebraic integers ... that are themselves polynomials. ... Mathematicians have decided to hold on to flawed ideas that I easily ...
    (sci.math)
  • Re: JSH: Trivially easy math
    ... > compelled to pick ONE WAY to show the factorization, ... > thinking that functions can force constants, ... > The real story here is not difficulty in understanding the mathematics. ... S= set of all possible polynomials of x with coefficients in S ...
    (sci.math)
  • Re: Overinterpertations of Galois Theory Exposed
    ... ADVANCED POLYNOMIAL FACTORIZATION ... While you know that the algebraic integer factors are themselves factors ... that are themselves polynomials. ... Who is this A. W. Beckwith ...
    (sci.math)