TU Darmstadt / ULB / TUbiblio

MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals

Mohamed, Mohamed Saied Emam ; Cabarcas, Daniel ; Ding, Jintai ; Buchmann, Johannes ; Bulygin, Stanislav
Hrsg.: Lee, Donghoon ; Hong, Seokhie (2010)
MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals.
Seoul, Korea
doi: 10.1007/978-3-642-14423-3_7
Konferenzveröffentlichung, Bibliographie

Kurzbeschreibung (Abstract)

This paper introduces a new efficient algorithm, called MXL3, for computing Gröbner bases of zero-dimensional ideals. The MXL3 is based on XL algorithm, mutant strategy, and a new sufficient condition for a set of polynomials to be a Gröbner basis. We present experimental results comparing the behavior of MXL3 to F4 on HFE and random generated instances of the MQ problem. In both cases the first implementation of the MXL3 algorithm succeeds faster and uses less memory than Magma’s implementation of F4.

Typ des Eintrags: Konferenzveröffentlichung
Erschienen: 2010
Herausgeber: Lee, Donghoon ; Hong, Seokhie
Autor(en): Mohamed, Mohamed Saied Emam ; Cabarcas, Daniel ; Ding, Jintai ; Buchmann, Johannes ; Bulygin, Stanislav
Art des Eintrags: Bibliographie
Titel: MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals
Sprache: Englisch
Publikationsjahr: Dezember 2010
Verlag: Springer
(Heft-)Nummer: 5984
Buchtitel: Proceedings of the 12th International Conference on Information Security and Cryptography - ICISC 2009
Band einer Reihe: Lecture Notes in Computer
Veranstaltungsort: Seoul, Korea
DOI: 10.1007/978-3-642-14423-3_7
Kurzbeschreibung (Abstract):

This paper introduces a new efficient algorithm, called MXL3, for computing Gröbner bases of zero-dimensional ideals. The MXL3 is based on XL algorithm, mutant strategy, and a new sufficient condition for a set of polynomials to be a Gröbner basis. We present experimental results comparing the behavior of MXL3 to F4 on HFE and random generated instances of the MQ problem. In both cases the first implementation of the MXL3 algorithm succeeds faster and uses less memory than Magma’s implementation of F4.

Freie Schlagworte: Secure Data; Multivariate polynomial systems, Groebner basis, XL algorithm, Mutant, MutantXL algorithm
ID-Nummer: TUD-CS-2009-0214
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
LOEWE > LOEWE-Zentren
20 Fachbereich Informatik
LOEWE
Hinterlegungsdatum: 04 Aug 2016 15:08
Letzte Änderung: 17 Mai 2018 13:02
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen