nach oben

Designs, Codes and Cryptography

Erschienen in:

13.10.2023

Towards a Gröbner-free approach to coding

verfasst von: Michela Ceria, Teo Mora

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1/2024

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Recently, new studies on the decoding of cyclic codes have been developed. They place themselves under the umbrella of Cooper Philosophy and they consist in using (sparse) locator polynomials, which, once evaluated at the syndromes, return the error locations. In particular, it has been recently shown that it is not necessary to use Gröbner bases to compute such kind of polynomials, and that some sparse versions can be found (at least for error correction capability at most 2), using interpolation on the syndrome variety. In this paper, we study the combinatorial structure of the syndrome variety of a cyclic code and some of its variants, for error correction capability 2, by means of standard monomials. Such monomials can be found without computing a Gröbner basis of the syndrome ideal, neither performing any step of Buchberger reduction, that is, in a degröbnerized way.

Vorheriger Artikel Quantum time/memory/data tradeoff attacks

Nächster Artikel Uniqueness of an association scheme related to the Witt design on 11 points

The recent mood, not depending on the network technology of the Sixties, and thus not needing the key equation, prefers considering the plain error locator polynomial \(\prod _{j=1}^{\mu } (x-\alpha ^{\ell _j})\).

Monomials’ representation given by the Bar Code has several applications. See for example [11, 13, 14].

The interested reader can find them at https://sites.google.com/view/michela-ceria-home-page/links.

Alonso M.E., Marinari M.G., Mora T.: The big mother of all dualities 2: Macaulay bases. Appl. Algebra Eng. Commun. Comput. 17(6), 409–451 (2006).MathSciNetCrossRef

Augot D., Bardet M., Faugere J.-C.: Efficient decoding of (binary) cyclic codes above the correction capacity of the code using Grobner bases. In: IEEE International Symposium on Information Theory-ISIT’2003, p. 362 (2003). IEEE Computer Society.

Augot D., Bardet M., Faugere J.-C.: On formulas for decoding binary cyclic codes. In: 2007 IEEE International Symposium on Information Theory, pp. 2646–2650 (2007). IEEE.

Berlekamp E.R.: Algebraic Coding Theory. McGraw-Hill, New York (1968).

Caboara M., Mora T.: The Chen-Reed-Helleseth-Truong decoding algorithm and the Gianni-Kalkbrenner Gröbner shape theorem. Appl. Algebra Eng. Commun. Comput. 13(3), 209–232 (2002). https://doi.org/10.1007/s002000200097.CrossRef

Caruso F., Orsini E., Sala M., Tinnirello C.: On the shape of the general error locator polynomial for cyclic codes. IEEE Trans. Inf. Theory 63(6), 3641–3657 (2017). https://doi.org/10.1109/TIT.2017.2692213.MathSciNetCrossRef

Ceria M.: Combinatorics of ideals of points: a cerlienco-mureddu-like approach for an iterative lex game. arXiv preprint arXiv:1805.09165 (2018).

Ceria M.: Half error locator polynomials for efficient decoding of binary cyclic codes. in preparation.

Ceria M.: A proof of the“axis of evil theorem’’ for distinct points. Rend. Semin. Mat. Univ. Politec. Torino 72(3–4), 213–233 (2014).MathSciNet

10.

Ceria M.: Bar code for monomial ideals. J. Symb. Comput. 91, 30–56 (2019). https://doi.org/10.1016/j.jsc.2018.06.012.MathSciNetCrossRef

11.

Ceria M.: Bar code vs Janet tree. Atti Accad. Peloritana Pericolanti Cl. Sci. Fis. Mat. Natur 97(2), 6–12 (2019). https://doi.org/10.1478/AAPP.972A6.MathSciNetCrossRef

12.

Ceria M.: Bar code: a visual representation for finite sets of terms and its applications. Math. Comput. Sci. 14(2), 497–513 (2020). https://doi.org/10.1007/s11786-019-00425-4.MathSciNetCrossRef

13.

Ceria M.: Bar code and Janet-like division. Atti Accad. Peloritana Pericolanti Cl. Sci. Fis. Mat. Natur 100(1), 2–10 (2022). https://doi.org/10.1478/AAPP.1001A2.MathSciNetCrossRef

14.

Ceria M.: Applications of bar code to involutive divisions and a “greedy’’ algorithm for complete sets. Math. Comput. Sci. 16(4), 30–17 (2022). https://doi.org/10.1007/s11786-022-00548-1.MathSciNetCrossRef

15.

Ceria M., Mora T., Sala M.: Zech tableaux as tools for sparse decoding. Rend. Semin. Mat. Univ. Politec. Torino 78(1), 43–56 (2020).MathSciNet

16.

Ceria M., Mora T., Sala M.: HELP: a sparse error locator polynomial for BCH codes. Appl. Algebra Eng. Commun. Comput. 31(3–4), 215–233 (2020). https://doi.org/10.1007/s00200-020-00427-x.MathSciNetCrossRef

17.

Ceria M., Lundqvist S., Mora T.: Degröbnerization: a political manifesto. Appl. Algebra Eng. Commun. Comput. 33(6), 675–723 (2022). https://doi.org/10.1007/s00200-022-00586-z.CrossRef

18.

Cerlienco L., Mureddu M.: From algebraic sets to monomial linear bases by means of combinatorial algorithms. vol. 139, pp. 73–87 (1995). https://doi.org/10.1016/0012-365X(94)00126-4 . Formal power series and algebraic combinatorics (Montreal, PQ, 1992).

19.

Cerlienco L., Mureddu M.: Algoritmi combinatori per l’interpolazione polinomiale in dimensione \(\ge 2\). Sém. Lothar. Comb. 24, 37 (1990).

20.

Cerlienco L., Mureddu M.: Multivariate interpolation and standard bases for Macaulay modules. J. Algebra 251(2), 686–726 (2002). https://doi.org/10.1006/jabr.2001.9061.MathSciNetCrossRef

21.

Chen X., Reed I.S., Helleseth T., Truong T.K.: Algebraic decoding of cyclic codes: a polynomial ideal point of view. In: Finite Fields: Theory, Applications, and Algorithms (Las Vegas, NV, 1993). Contemp. Math., vol. 168, pp. 15–22. Amer. Math. Soc., Providence (1994). https://doi.org/10.1090/conm/168/01685.

22.

Chen X., Reed I.S., Helleseth T., Truong T.K.: Use of Gröbner bases to decode binary cyclic codes up to the true minimum distance. IEEE Trans. Inf. Theory 40(5), 1654–1661 (1994). https://doi.org/10.1109/18.333885.CrossRef

23.

Chen X., Reed I.S., Helleseth T., Truong T.K.: General principles for the algebraic decoding of cyclic codes. IEEE Trans. Inf. Theory 40(5), 1661–1663 (1994). https://doi.org/10.1109/18.333886.MathSciNetCrossRef

24.

Cooper A.B.: Direct solution of BCH decoding equations. Commun. Control Signal Process. 281–286 (1990).

25.

Cooper A.B.: Finding BCH error locator polynomials in one step. Electron. Lett. 22(27), 2090–2091 (1991).CrossRef

26.

Coppersmith D., Winograd S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251–280 (1990).MathSciNetCrossRef

27.

Felszeghy B., Ráth B., Rónyai L.: The lex game and some applications. J. Symb. Comput. 41(6), 663–681 (2006). https://doi.org/10.1016/j.jsc.2005.11.003.MathSciNetCrossRef

28.

Gianni P.: Properties of Gröbner bases under specializations. In: EUROCAL ’87 (Leipzig, 1987). Lecture Notes in Comput. Sci., vol. 378, pp. 293–297. Springer, Berlin (1989). https://doi.org/10.1007/3-540-51517-8_128.

29.

Hoeven J., Larrieu R.: Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals. Appl. Algebra Eng. Commun. Comput. 30(6), 509–539 (2019). https://doi.org/10.1007/s00200-019-00389-9.CrossRef

30.

Huffman W.C., Pless V.: Fundamentals of Error-Correcting Codes, p. 646. Cambridge University Press, Cambridge (2003) https://doi.org/10.1017/CBO9780511807077.CrossRef

31.

Kalkbrener M.: Solving systems of algebraic equations by using Gröbner bases. In: EUROCAL ’87 (Leipzig, 1987). Lecture Notes in Comput. Sci., vol. 378, pp. 282–292. Springer, Berlin (1989). https://doi.org/10.1007/3-540-51517-8_127.

32.

Lazard D.: Ideal bases and primary decomposition: case of two variables. J. Symb. Comput. 1(3), 261–270 (1985).MathSciNetCrossRef

33.

Loustaunau P., York E.V.: On the decoding of cyclic codes using Gröbner bases. Appl. Algebra Eng. Commun. Comput. 8(6), 469–483 (1997). https://doi.org/10.1007/s002000050084.CrossRef

34.

Lundqvist S.: Vector space bases associated to vanishing ideals of points. J. Pure Appl. Algebra 214(4), 309–321 (2010). https://doi.org/10.1016/j.jpaa.2009.05.013.MathSciNetCrossRef

35.

Macaulay F.S.: Some properties of enumeration in the theory of modular systems. Proc. Lond. Math. Soc. 26(2), 531–555 (1927). https://doi.org/10.1112/plms/s2-26.1.531.MathSciNetCrossRef

36.

Marinari M.G., Möller H.M., Mora T.: Gröbner bases of ideals given by dual bases. In: Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, pp. 55–63 (1991).

37.

Marinari M.G., Mora T., Möller H.M.: Gröbner duality and multiplicities in polynomial system solving. In: Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, pp. 167–179 (1995).

38.

Marinari M.G., Mora T.: A remark on a remark by Macaulay or enhancing Lazard structural theorem. Bull. Iranian Math. Soc. 29(1), 1–4585 (2003).MathSciNet

39.

Marinari M.G., Möller H.M., Mora T.: Gröbner bases of ideals defined by functionals with an application to ideals of projective points. Appl. Algebra Eng. Commun. Comput. 4(2), 103–145 (1993). https://doi.org/10.1007/BF01386834.CrossRef

40.

Möller H.M., Buchberger B.: The construction of multivariate polynomials with preassigned zeros. In: Computer Algebra (Marseille, 1982). Lecture Notes in Comput. Sci., vol. 144, pp. 24–31. Springer, Berlin (1982).

41.

Mora T., Orsini E.: Invited talk: decoding cyclic codes: the Cooper philosophy (extended abstract). In: Mathematical Methods in Computer Science. Lecture Notes in Comput. Sci., vol. 5393, pp. 126–127. Springer, Berlin (2008). https://doi.org/10.1007/978-3-540-89994-5_10.

42.

Mora T.: Solving Polynomial Equation Systems, vol. 4. Cambridge University Press, Cambridge (I (2003), II (2005), III (2015), IV (2016)).

43.

Mora F.: De nugis Groebnerialium. II. Applying Macaulay’s trick in order to easily write a Gröbner basis. Appl. Algebra Eng. Commun. Comput. 13(6), 437–446 (2003). https://doi.org/10.1007/s00200-002-0112-2.CrossRef

44.

Mourrain B.: A new criterion for normal form algorithms. In: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Honolulu, HI, 1999). Lecture Notes in Comput. Sci., vol. 1719, pp. 430–443. Springer, Berlin (1999). https://doi.org/10.1007/3-540-46796-3_41.

45.

Orsini E., Sala M.: Correcting errors and erasures via the syndrome variety. J. Pure Appl. Algebra 200(1–2), 191–226 (2005). https://doi.org/10.1016/j.jpaa.2004.12.027.MathSciNetCrossRef

Titel: Towards a Gröbner-free approach to coding
verfasst von: Michela Ceria
Teo Mora
Publikationsdatum: 13.10.2023
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 1/2024
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-023-01302-9

Springer Professional

Towards a Gröbner-free approach to coding

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1/2024

Parameters of several families of binary duadic codes and their related codes

Generic constructions of master-key KDM secure attribute-based encryption

Quantum time/memory/data tradeoff attacks

BBB security for 5-round even-Mansour-based key-alternating Feistel ciphers

Minimal and optimal binary codes obtained using -construction over the non-unital ring I

Nonsingular hypercubes and nonintersecting hyperboloids

Premium Partner