Re: root of polynomial over galois field

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



.

Relevant Pages

  • Re: root of polynomial over galois field
    ... Examples 8.4-8.5 may not be sufficient explanation. ... Here we've written "a" in the form of a squarefree factorization, ... Here we reach the Line 14, but now we see c = product, p divides ... typo on my behalf and it should have read c=/= 1 and not what I had ...
    (sci.math.symbolic)
  • [Factorization] Is SQUFOF efficient?
    ... I was checking out the Integer factorization page on Wikipedia: ... and tried to implement Shank's square form factorization (SQUFOF) ... while loop: ... point out the error in my algorithm; ...
    (sci.math)
  • Re: Factoring and GCD
    ... m, hence, theoretically, by going through a loop which calculates GCD ... for all all primes p_i < m, we can conceivably unveil its factorization, ... The reason I am asking is because my impression is that the GCD algorithm is ...
    (sci.math)
  • Re: Factoring and GCD
    ... m, hence, theoretically, by going through a loop which calculates GCD(m, ... for all all primes p_i < m, we can conceivably unveil its factorization, ... The reason I am asking is because my impression is that the GCD algorithm ... There are lots of primes. ...
    (sci.math)