Vestnik of Samara University. Natural Science SeriesVestnik of Samara University. Natural Science Series2541-75252712-8954Samara National Research University1012910.18287/2541-7525-2021-27-2-7-15Research ArticleON DECODING ALGORITHMS FOR GENERALIZED REED — SOLOMON CODES WITH ERRORS AND ERASURES. IIRatseevS. M.<p>Doctor of Physical and Mathematical Sciences, associate professor, Department of Information Security and Control Theory</p>ratseevsm@mail.ruhttps://orcid.org/0000-0003-4995-9418CherevatenkoO. I.<p>Candidate of Physical and Mathematical Sciences, associate professor, Department of Higher Mathematics</p>choi2008@mail.ruhttps://orcid.org/0000-0003-3931-9425Ulyanovsk State UniversityUlyanovsk State University of Education310520212727152803202228032022Copyright © 2021, Ratseev S.M., Cherevatenko O.I.2021<p>The article is a continuation of the authors’ work «On decoding algorithms for generalized Reed — Solomon codes with errors and erasures». In this work, another modification of the Gao algorithm and the Berlekamp — Massey algorithm is given. The first of these algorithms is a syndrome-free decoding algorithm, the second is a syndrome decoding algorithm. The relevance of these algorithms is that they are applicable for decoding Goppa codes, which are the basis of some promising post-quantum cryptosystems.</p>помехоустойчивые кодыкоды Рида — Соломонакоды Гоппыдекодирование кодаerror-correcting codesReed — Solomon codesGoppa codescode decoding[Gao S. A new algorithm for decoding Reed—Solomon codes. In: Bhargava V.K., Poor H.V., Tarokh V., Yoon S. (Eds.) Communications, Information and Network Security. The Springer International Series in Engineering and Computer Science (Communications and Information Theory). Boston, MA.: Springer, 2003, vol. 712, pp. 55–68. DOI: http://doi.org/10.1007/978-1-4757-3789-9_5.][Massey J.L. Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory, 1969, vol. IT. 15, no. 1, pp. 122–127. Available at: https://crypto.stanford.edu/ mironov/cs359/massey.pdf.][Ratseev S.M., Cherevatenko O.I. On decoding algorithms for generalized Reed-Solomon codes with errors and erasures. Vestnik Samarskogo universiteta. Estestvennonauchnaia seriia = Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 3, pp. 17–29. DOI: http://doi.org/10.18287/2541-7525-2020-26-3-17-29. (In Russ.)][Fedorenko S.V. A simple algorithm for decoding algebraic codes. Information and Control Systems, 2008, no. 3 (34), pp. 23–27. Available at: https://elibrary.ru/item.asp?id=10607208. (In Russ.)][Goppa V.D. A New Class of Linear Correcting Codes. Probl. Peredachi Inf. [Problems of Information Transmission], 1970, vol. 6, issue 3, pp. 207–212. Available at: http://mi.mathnet.ru/ppi1748; http://xn–80af7aea.xn–p1ai/Publications/linear_correcting_codes.pdf. (In Russ.)][Ratseev S.M. Elements of higher algebra and coding theory. St. Petersburg: Lan’, 2022, 656 p. Available at: https://reader.lanbook.com/book/187575?demoKey=9c43d0c829634cd713016a7fb3743823#1 (In Russ.)][Ratseev S.M. On decoding algorithms for Goppa codes. Chelyabinskiy Fizilko-Matematicheskiy Zhurnal = Chelyabinsk Physical and Mathematical Journal, 2020, vol. 5, no. 3, pp. 327–341. DOI: http://doi.org/10.47475/2500-0101-2020-15307. (In Russ.)][Patterson N.J. The algebraic decoding of Goppa codes. IEEE Transactions on Information Theory, 1975, vol. 21, issue 2, pp. 203–207. DOI: http://doi.org/10.1109/TIT.1975.1055350][Bernstein D., Chou T., Lange T., Maurich I., Misoczki R., Niederhagen R., Persichetti E., Peters C., Schwabe P., Sendrier N., Szefer J., Wang W. Classic McEliece: conservative code-based cryptography. Project documentation. Available at: https://classic.mceliece.org/nist/mceliece-20190331.pdf (accessed 22.12.2020).][Ratseev S.M. Mathematical methods of information security: textbook. Saint Petersburg: Lan’, 2022, 544 p. Available at: https://e.lanbook.com/book/193323. (In Russ.)]