Hi Panos The snippet you gave certainly does not work since it will compute the gcd of 1 and something else, which is - of course - 1.
What you need is to compute the *half gcd* of R and g, i.e. run the Extended Euclidean algorithm about half-way and then stop. The Bezout relation from that iteration will give you what you want: u_i * R + v_i * g = r_i i.e. r_i == u_i * R mod g For Patterson's algorithm, the restriction you need, if I recall correctly, is something like deg r_i > deg u_i. Use this as stopping-criteria for your half-gcd and you should be good. A half-gcd as described above is already included in Sage for the Gao-decoding algorithm of Reed-Solomon codes. It's implemented in sage/coding/grs.py and called partial_xgcd. If you're implementation becomes nice, Goppa codes is really something we need in Sage. Consider opening a ticket and feel free to cc me on it. Good luck, Best, Johan On Monday, February 13, 2017 at 1:41:49 AM UTC+1, Panos Phronimos wrote: > > Hello, > > I am trying to implement Patterson's Algorithm for decoding Goppa codes. > > I am stuck in the part that I have to find two polynomials a(x) and b(x) > so that a(x)=b(x)R(x)mod(g(x)) > where g(x) is the goppa poly and deg(a(x)) must be <= t/2. > I know that i have to use extended Euclidean Algorithm and i have decoded > several random examples but > i can't find a general solution for any given equation. > > P.S. A paper i advised proposed the following code: > (d,u,v) = xgcd(PR(1),PR(R.list())); #Where PR is a polynomial ring over an > extension of GF(2) > a = g*u; b = g*v; > But I don't think is working correctly in the way i implemented it! > > > Thanks in advance! > > > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
