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$ Jun 17, 2017 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$ Jun 17, 2017 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$ Jun 17, 2017 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, 2017 at 12:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.