Hi,(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Square-free factorization of univariate polynomials over Galois Fields

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

Loading...

Similar Threads - Square free factorization | Date |
---|---|

I Can we construct a Lie algebra from the squares of SU(1,1) | Feb 24, 2018 |

Least Square basic problem | Jan 20, 2018 |

I Free Groups | Oct 19, 2017 |

B ##AB = I \implies BA = I##, for square matricies ##A,B## | Jun 9, 2017 |

I Trying to understand least squares estimates | Feb 25, 2017 |

**Physics Forums - The Fusion of Science and Community**