TU Darmstadt / ULB / TUbiblio

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

Mohamed, Mohamed Saied Emam and Cabarcas, Daniel and Ding, Jintai and Buchmann, Johannes and Bulygin, Stanislav
Lee, Donghoon and Hong, Seokhie (eds.) (2010):
MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals.
In: Proceedings of the 12th International Conference on Information Security and Cryptography - ICISC 2009, Springer, Seoul, Korea, Lecture Notes in Computer, ISBN 978-3-642-14422-6,
DOI: 10.1007/978-3-642-14423-3_7,
[Conference or Workshop Item]

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.

Item Type: Conference or Workshop Item
Erschienen: 2010
Editors: Lee, Donghoon and Hong, Seokhie
Creators: Mohamed, Mohamed Saied Emam and Cabarcas, Daniel and Ding, Jintai and Buchmann, Johannes and Bulygin, Stanislav
Title: MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals
Language: ["languages_typename_1" not defined]
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.

Title of Book: Proceedings of the 12th International Conference on Information Security and Cryptography - ICISC 2009
Volume: Lecture Notes in Computer
Number: 5984
Publisher: Springer
ISBN: 978-3-642-14422-6
Uncontrolled Keywords: Secure Data; Multivariate polynomial systems, Groebner basis, XL algorithm, Mutant, MutantXL algorithm
Divisions: 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
LOEWE > LOEWE-Zentren
20 Department of Computer Science
LOEWE
Event Location: Seoul, Korea
Date Deposited: 04 Aug 2016 15:08
DOI: 10.1007/978-3-642-14423-3_7
Identification Number: TUD-CS-2009-0214
Export:
Suche nach Titel in: TUfind oder in Google

Optionen (nur für Redakteure)

View Item View Item