root of polynomial over galois field

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'), and the algorithm states that :-

"Algorithm 8.3 Finite Field Squre-Free Factorization.

procedure SquareFreeFF(a(x),q)

# Given a monic polynomial a(x) contained in GF(q)[x], with GF(q) a
# Galois field of order q = p^m, we calculate the square-free
factorization of
# a(x).

i <--- 1; Output <--- 1; b(x) <--- a'(x)
if b(x) =/= 0 then {
c(x) <---- GCD(a(x), b(x))
w(x) <---- a(x)/c(x)
while w(x) =/= 1 do {
y(x) <---- GCD(w(x),c(x)); z(x) <---- w(x)/y(x)
Output <---- Output . z(x)^i; i <---- i + 1
w(x) <---- y(x); c(x) <---- c(x)/y(x) }
if c(x) =/= c(x)^1/p
c(x) <--- c(x)^1/p
Output <---- Output . ( SquareFreeFF(c(x)) )^p}}
else {
a(x) <---- a(x)^1/p
Output <---- ( SquareFreeFF(a(x)) )^p}
return(Output)

end"

My question concerns Lines 14-15... ie. the bit that says :-
"if c(x) =/= c(x)^1/p
c(x) <--- c(x)^1/p"

These lines obviously call for finding the 'pth root 'of the polynomial c(x)
over a Galois Field.

Now preceeding this algorithm there is a section which explains how to go
about finding the pth root of a polynomial over a Galois field, but there is
a condition that to find the pth root of a polynomial a(x) then a'(x) = 0.

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


Thanks
Jereny Watts


.

Relevant Pages

  • Re: Elementary group theory: Proof of Fermat-Maas primality-test (was: correcting Dik ...)
    ... the Fermat-Maas algorithm to prove it's really prime, ... the known factorization of p-1 that you got when you directly ... Back to the RSA page: ... So somebody buys 80 high-speed computers, ...
    (sci.math)
  • Re: Spectral Matrix Factorization via Wilson Method
    ... inner-outer factorization of a spectral density matrix, S, (where ... Factorization of Matricial Spectral Densities, ... algorithm does not quite converge on the correct solution. ...
    (comp.dsp)
  • Simple answer, surrogate factoring
    ... where M is the target to be factored, j is some non-zero natural ... Az is related to the factorization of T and M. ... So the full algorithm, which splits up A and x requires that you solve ... And then for at least one case, it must be true that the denominator ...
    (sci.math)
  • Simple answer, surrogate factoring
    ... where M is the target to be factored, j is some non-zero natural ... Az is related to the factorization of T and M. ... So the full algorithm, which splits up A and x requires that you solve ... And then for at least one case, it must be true that the denominator ...
    (sci.crypt)
  • Re: Surrogate factoring demonstrated
    ... > Will Twentyman wrote: ... >>or success wise? ... > Initial Factorization: ... be a sharp increase in factoring efficiency depending on what algorithm ...
    (sci.crypt)
Quantcast