According to the articles that i read (also wikipedia [1]), they refer that the above algorithm works on finite field $GF(q)$. But I cannot find an evidence that it still works on extension field, i.e: $GF(q^n)$. It looks like from the algorithm itself that there is no problem, but I rather like an expert opinion.

[1]- https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm#CITEREFReedsSloane1985

  • $\begingroup$ Wikipedia says it works for an arbitrary field. It does not mention prime fields, if that's what you mean by $q$. $\endgroup$ – Emil Jeřábek Jun 17 '17 at 11:43
  • $\begingroup$ Yes I know and yet, I'm trying to find an explicit justification that it works on extension field. Because I depend on that fact in an article that I'm writing. $\endgroup$ – user1387682 Jun 17 '17 at 12:00
  • 4
    $\begingroup$ Apologies for sounding grumpy, but if this algorithm is essential to your article, maybe you should read original articles and understand the algorithm yourself, rather than rely on wikipedia and stackexchange. $\endgroup$ – Sasho Nikolov Jun 17 '17 at 22:45
  • 1
    $\begingroup$ I agree with @SashoNikolov, for example at a minimum you can code the algorithm for say $GF(4)$ and test it for all sequences up to some small length and confirm. $\endgroup$ – kodlu Jun 18 '17 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.