zbMATH — the first resource for mathematics

Fast operations on linearized polynomials and their applications in coding theory. (English) Zbl 1398.12015
Summary: This paper considers fast algorithms for operations on linearized polynomials. We propose a new multiplication algorithm for skew polynomials (a generalization of linearized polynomials) which has sub-quadratic complexity in the polynomial degree \(s\), independent of the underlying field extension degree \(m\). We show that our multiplication algorithm is faster than all known ones when \(s \leq m\). Using a result by X. Caruso and J. Le Borgne [J. Symb. Comput. 79, Part 2, 411–443 (2017; Zbl 1373.16046)], this immediately implies a sub-quadratic division algorithm for linearized polynomials for arbitrary polynomial degree \(s\). Also, we propose algorithms with sub-quadratic complexity for the \(q\)-transform, multi-point evaluation, computing minimal subspace polynomials, and interpolation, whose implementations were at least quadratic before. Using the new fast algorithm for the \(q\)-transform, we show how matrix multiplication over a finite field can be implemented by multiplying linearized polynomials of degrees at most \(s = m\) if an elliptic normal basis of extension degree \(m\) exists, providing a lower bound on the cost of the latter problem. Finally, it is shown how the new fast operations on linearized polynomials lead to the first error and erasure decoding algorithm for Gabidulin codes with sub-quadratic complexity.

12Y05 Computational aspects of field theory and polynomials (MSC2010)
94B35 Decoding
Full Text: DOI arXiv
[1] Aho, A. V.; Hopcroft, J. E., The design and analysis of computer algorithms, (1974), Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA · Zbl 0326.68005
[2] Bini, D.; Pan, V., Polynomial and matrix computations: fundamental algorithms, (2012), Springer Science & Business Media
[3] Blahut, R. E., Fast algorithms for digital signal processing, (1985), Addison-Wesley · Zbl 0579.94001
[4] Bohaczuk Venturelli, R.; Silva, D., An evaluation of erasure decoding algorithms for gabidulin codes, (Int. Telecommunications Symposium, ITS, (Aug. 2014)), 1-5
[5] Boucher, D.; Ulmer, F., Linear codes using skew polynomials with automorphisms and derivations, Des. Codes Cryptogr., 70, 3, 405-431, (2014) · Zbl 1302.94065
[6] Brent, R. P.; Gustavson, F. G.; Yun, D. Y., Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms, 1, 3, 259-295, (1980) · Zbl 0475.65018
[7] Brent, R. P.; Kung, H. T., Fast algorithms for manipulating formal power series, J. ACM, 25, 4, 581-595, (Oct. 1978)
[8] Caruso, X.; Borgne, J. L., Fast multiplication for skew polynomials, (2017), arXiv preprint
[9] Caruso, X.; Le Borgne, J., A new faster algorithm for factoring skew polynomials over finite fields, J. Symb. Comput., 79, 411-443, (2017) · Zbl 1373.16046
[10] Cohen, S. D.; Hachenberger, D., The dynamics of linearized polynomials, Proc. Edinb. Math. Soc., 43, 01, 113-128, (2000) · Zbl 0955.12002
[11] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. Symb. Comput., 9, 3, 251-280, (1990) · Zbl 0702.65046
[12] Couveignes, J.-M.; Lercier, R., Elliptic periods for finite fields, Finite Fields Appl., 15, 1, 1-22, (2009) · Zbl 1216.11106
[13] Delsarte, P., Bilinear forms over a finite field with applications to coding theory, J. Comb. Theory, Ser. A, 25, 3, 226-241, (1978) · Zbl 0397.94012
[14] Evans, R. J.; Greene, J.; Niederreiter, H., Linearized polynomials and permutation polynomials of finite fields, Mich. Math. J., 39, 3, 405-413, (1992) · Zbl 0777.11052
[15] Gabidulin, E. M., Theory of codes with maximum rank distance, Probl. Inf. Transm., 21, 1, 3-16, (1985) · Zbl 0585.94013
[16] Gabidulin, E. M.; Paramonov, A.; Tretjakov, O., Ideals over a non-commutative ring and their application in cryptology, (Advances in Cryptology—EUROCRYPT’91, (1991), Springer), 482-489 · Zbl 0766.94009
[17] Gao, S., Normal bases over finite fields, (1993), University of Waterloo Waterloo, Canada, Ph.D. thesis
[18] Gao, S., A new algorithm for decoding Reed-Solomon codes, (Communications, Information and Network Security, vol. 712, (2003)), 55-68 · Zbl 1330.94063
[19] Gathen, J.; Gerhard, J., Modern computer algebra, (1999), Cambridge University Press · Zbl 0936.11069
[20] Gustavson, F.; Yun, D., Fast algorithms for rational Hermite approximation and solution of Toeplitz systems, IEEE Trans. Circuits Syst., 26, 9, 750-755, (September 1979)
[21] Huang, X.; Pan, V. Y., Fast rectangular matrix multiplication and applications, J. Complex., 14, 2, 257-299, (1998) · Zbl 0919.65030
[22] Ke, S.; Zeng, B.; Han, W.; Pan, V. Y., Fast rectangular matrix multiplication and some applications, Sci. China Ser. A, 51, 3, 389-406, (2008) · Zbl 1151.68428
[23] Li, W.; Sidorenko, V.; Silva, D., On transform-domain error and erasure correction by gabidulin codes, Des. Codes Cryptogr., 73, 2, 571-586, (2014) · Zbl 1335.94097
[24] Lidl, R.; Niederreiter, H., Finite fields: encyclopedia of mathematics and its applications, Comput. Math. Appl., 33, 7, 136, (1997)
[25] Menezes, A. J.; Blake, I. F.; Gao, X.; Mullin, R. C.; Vanstone, S. A.; Yaghoobian, T., Applications of finite fields, (1993), Springer · Zbl 0779.11059
[26] Ore, O., On a special class of polynomials, Trans. Am. Math. Soc., 35, 3, 559-584, (1933) · JFM 59.0163.02
[27] Ore, O., Theory of non-commutative polynomials, Ann. Math., 34, 3, 480-508, (1933) · JFM 59.0925.01
[28] Paterson, M. S.; Stockmeyer, L. J., On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM J. Comput., 2, 1, 60-66, (1973) · Zbl 0262.65033
[29] Puchinger, S.; Wachter-Zeh, A., Sub-quadratic decoding of gabidulin codes, (IEEE Int. Symp. Inf. Theory, ISIT, (Jul. 2016))
[30] Roth, R. M., Maximum-rank array codes and their application to crisscross error correction, IEEE Trans. Inf. Theory, 37, 2, 328-336, (1991) · Zbl 0721.94012
[31] Silberstein, N.; Rawat, A. S.; Vishwanath, S., Error resilience in distributed storage via rank-metric codes, (Allerton Conf. Communication, Control, Computing, Allerton, (Oct. 2012)), 1150-1157
[32] Silva, D.; Kschischang, F. R., Rank-metric codes for priority encoding transmission with network coding, (Canadian Workshop on Information Theory, (2007), IEEE), 81-84
[33] Silva, D.; Kschischang, F. R., Fast encoding and decoding of gabidulin codes, (IEEE Int. Symp. Inf. Theory, ISIT, (Jun. 2009)), 2858-2862
[34] Silva, D.; Kschischang, F. R.; Koetter, R., A rank-metric approach to error control in random network coding, IEEE Trans. Inf. Theory, 54, 9, 3951-3967, (2008) · Zbl 1318.94119
[35] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 4, 354-356, (1969) · Zbl 0185.40101
[36] Sudan, M., Decoding of Reed-Solomon codes beyond the error-correction bound, J. Complex., 13, 1, 180-193, (Mar. 1997)
[37] Sugiyama, Y.; Kasahara, M.; Hirasawa, S.; Namekawa, T., A method for solving key equation for decoding Goppa codes, Inf. Control, 27, 1, 87-99, (1975) · Zbl 0293.94007
[38] Wachter-Zeh, A., Decoding of block and convolutional codes in rank metric, (2013), Ulm University and University of Rennes, Ph.D. thesis
[39] Wachter-Zeh, A.; Afanassiev, V.; Sidorenko, V., Fast decoding of gabidulin codes, Des. Codes Cryptogr., 66, 1, 57-73, (2013) · Zbl 1259.94082
[40] Welch, L.R., Berlekamp, E.R., 1986. Error correction for algebraic block codes.
[41] Wu, B.; Liu, Z., Linearized polynomials over finite fields revisited, Finite Fields Appl., 22, 79-100, (2013) · Zbl 1345.11084
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.