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

Mohamed Saied Emam Mohamed; Daniel Cabarcas; Jintai Ding; Johannes Buchmann; Stanislav Bulygin

doi:10.1007/978-3-642-14423-3_7

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

Mohamed Saied Emam Mohamed, Daniel Cabarcas, Jintai Ding, Johannes Buchmann, Stanislav Bulygin

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

32 Citations (Scopus)

Abstract

This paper introduces a new efficient algorithm, called MXL₃, for computing Gröbner bases of zero-dimensional ideals. The MXL₃ 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 MXL₃ to F₄ on HFE and random generated instances of the MQ problem. In both cases the first implementation of the MXL₃ algorithm succeeds faster and uses less memory than Magma's implementation of F₄.

Original language	English
Title of host publication	Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers
Pages	87-100
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-642-14423-3_7
Publication status	Published - 2010
Externally published	Yes
Event	12th International Conference on Information Security and Cryptology, ICISC 2009 - Seoul, Korea, Republic of Duration: 2 Dec 2009 → 4 Dec 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5984 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Conference on Information Security and Cryptology, ICISC 2009
Country/Territory	Korea, Republic of
City	Seoul
Period	2/12/09 → 4/12/09

Keywords

Gröbner basis
Multivariate polynomial systems
Mutant
MutantXL algorithm
XL algorithm

Access to Document

10.1007/978-3-642-14423-3_7

Cite this

Mohamed, M. S. E., Cabarcas, D., Ding, J., Buchmann, J., & Bulygin, S. (2010). MXL₃: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals. In Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers (pp. 87-100). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5984 LNCS). https://doi.org/10.1007/978-3-642-14423-3_7

Mohamed, Mohamed Saied Emam ; Cabarcas, Daniel ; Ding, Jintai et al. / MXL₃ : An efficient algorithm for computing Gröbner bases of zero-dimensional ideals. Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. 2010. pp. 87-100 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0b557850225d44019e8e33914f66d390,

title = "MXL3: An efficient algorithm for computing Gr{\"o}bner bases of zero-dimensional ideals",

abstract = "This paper introduces a new efficient algorithm, called MXL3, for computing Gr{\"o}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{\"o}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.",

keywords = "Gr{\"o}bner basis, Multivariate polynomial systems, Mutant, MutantXL algorithm, XL algorithm",

author = "Mohamed, {Mohamed Saied Emam} and Daniel Cabarcas and Jintai Ding and Johannes Buchmann and Stanislav Bulygin",

year = "2010",

doi = "10.1007/978-3-642-14423-3_7",

language = "English",

isbn = "3642144225",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "87--100",

booktitle = "Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers",

note = "12th International Conference on Information Security and Cryptology, ICISC 2009 ; Conference date: 02-12-2009 Through 04-12-2009",

}

Mohamed, MSE, Cabarcas, D, Ding, J, Buchmann, J & Bulygin, S 2010, MXL₃: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals. in Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5984 LNCS, pp. 87-100, 12th International Conference on Information Security and Cryptology, ICISC 2009, Seoul, Korea, Republic of, 2/12/09. https://doi.org/10.1007/978-3-642-14423-3_7

MXL₃: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals. / Mohamed, Mohamed Saied Emam; Cabarcas, Daniel; Ding, Jintai et al.
Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. 2010. p. 87-100 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5984 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - MXL3

T2 - 12th International Conference on Information Security and Cryptology, ICISC 2009

AU - Mohamed, Mohamed Saied Emam

AU - Cabarcas, Daniel

AU - Ding, Jintai

AU - Buchmann, Johannes

AU - Bulygin, Stanislav

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - Gröbner basis

KW - Multivariate polynomial systems

KW - Mutant

KW - MutantXL algorithm

KW - XL algorithm

UR - http://www.scopus.com/inward/record.url?scp=77954565760&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14423-3_7

DO - 10.1007/978-3-642-14423-3_7

M3 - Conference Proceeding

AN - SCOPUS:77954565760

SN - 3642144225

SN - 9783642144226

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 87

EP - 100

BT - Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers

Y2 - 2 December 2009 through 4 December 2009

ER -

Mohamed MSE, Cabarcas D, Ding J, Buchmann J, Bulygin S. MXL₃: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals. In Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. 2010. p. 87-100. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-14423-3_7