Patterson Decoder for binary Goppa codes

[gh-giucesare]

Decoder for binary Goppa codes whose defining polynomials are square free which uses Patterson decoding algorithm in order to correct errors in words. The Patterson decoder makes use of the terminated extended Euclidean algorithm. For further details see

14. Patterson: The algebraic decoding of Goppa codes, IEEE Transactions on Information Theory 21.2 (1975), pp. 203-207.

Johan S. H. Rosenkilde gave us a feedback on the first draft of this decoder and also suggested us possible reviewers. So, we would like to thank him.

[gh-giucesare]

Patterson Decoder

[dimpase]

Could you post a branch, rather than an attachment?

[gh-giucesare]

after many attempts maybe I did it correctly now... sorry, this is my first ticket.

---

New commits:

​e62cd8a

Decoder for binary Goppa codes whose defining polynomials are square free which uses Patterson decoding algorithm in order to correct errors in words.

[caruso]

The method _partial_xgcd_gen is called only once; is it really useful to have a special method for this? (Something that makes more sense according to me is to have a general shared function for this task which could be defined for example in the class handling univariate polynomials; but, more simply, you can just put your code directly in the caller method _decode_to_code_and_message.)

Another general remark is that the documentation is not always correctly formatted. See ​https://doc.sagemath.org/html/en/developer/coding_basics.html#the-docstring-of-a-function-content for details. In addition you should probably add TESTS sections (in the documentation) for checking that errors are handled correctly.

[gh-giucesare]

Ok, we will make these changes then. Thank you.

[mkoeppe]

Setting a new milestone for this ticket based on a cursory review.

[mkoeppe]

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.