Portal de Periódicos da CAPES

A method for solving key equation for decoding goppa codes

1975; Academic Press; Volume: 27; Issue: 1 Linguagem: Inglês

10.1016/s0019-9958(75)90090-x

1878-2981

Y. Sugiyama, Masao Kasahara, Shigeichi Hirasawa, Toshihiko Namekawa,

Cellular Automata and Applications

In this paper we show that the key equation for decoding Goppa codes can be solved using Euclid's algorithm. The division for computing the greatest common divisor of the Goppa polynomial g ( z ) of degree 2 t and the syndrome polynomial is stopped when the degree of the remainder polynomial is less than or equal to t − 1. The error locator polynomial is proved the multiplier polynomial for the syndrome polynomial multiplied by an appropriate scalar factor. The error evaluator polynomial is proved the remainder polynomial multiplied by an appropriate scalar factor. We will show that the Euclid's algorithm can be modified to eliminate multiplicative inversion, and we will evaluate the complexity of the inversionless algorithm by the number of memories and the number of multiplications of elements in GF ( q m ). The complexity of the method for solving the key equation for decoding Goppa codes is a few times as much as that of the Berlekamp—Massey algorithm for BCH codes modified by Burton. However the method is straightforward and can be applied for solving the key equation for any Goppa polynomial.