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.

Thank you very much for that very detailed answer. Yes indeed there was a
typo on my behalf and it should have read c(x) =/= 1 and not what I had
put. But yes very helpful answer thanks a lot.

JW






.