# Square-free factorization of univariate polynomials over Galois Fields

1. Dec 13, 2013

### jezza10181

Hi,

I am looking at an algorithm in the book, 'Algorithms for Computer Algebra' by Geddes/Czapor/Labahn, and the algorithm on p. 345, 'Finite Field Square-Free Factorization', which square -free factorizes univariate polynomials over Galois Fields, of order 'q'. Where, 'q' here is a prime, or a power of a prime, so that
q = p^m, where 'p' is prime, and 'm' is a positive integer.

On page 344, there is a theorem that states that if a(x) = a0 + a1x + ... + an x^n be a polynomial of degree 'n' in GF(q)[x] satisfying a'(x) = 0. Then a(x) = b(x)^p, for some polynomial b(x), and that each coefficient of b(x), is given by :-

bi = aip ^ 1/p = aip ^ (p^m-1)

Now, I have myself produced an example, to test this theory, so I have my a(x) as :-

a(x) = 2 x^8 + 4 x^4 + 8 x^2 + 7

where here, I have chosen q = 16, p = 2, m = 4

Now, a'(x) = 0 (Hope you agree with that?)

So, if I am interpreting this theorem correctly, then I make my corresponding coefficients for
b(x), as:-

b0 = ao ^ 8 = 7 ^ 8 = 1
b1 = a2 ^ 8 = 8 ^ 8 = 0
b2 = a4 ^ 8 = 4 ^ 8 = 0
b3 = a6 ^ 8 = 0 ^ 8 = 0
b4 = a8 ^ 8 = 2 ^ 8 = 0

All the other coefficients will be zero, so there's no point going any further - so my final result for b(x) is:-
b(x) = 1

Yet this cannot possibly be correct, as b(x) ^ p does not equal a(x).

Does anyone else have this book, or know this theorem. Can you see what's going wrong here please?

Thanks
Jeremy