MXL3: An Efficient Algorithm for Computing Gröbner Bases of Zero-Dimensional Ideals View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

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

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. More... »

PAGES

87-100

References to SciGraph publications

Book

TITLE

Information, Security and Cryptology – ICISC 2009

ISBN

978-3-642-14422-6
978-3-642-14423-3

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-14423-3_7

DOI

http://dx.doi.org/10.1007/978-3-642-14423-3_7

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1041918753


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0307", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Theoretical and Computational Chemistry", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/03", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Chemical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Technical University of Darmstadt", 
          "id": "https://www.grid.ac/institutes/grid.6546.1", 
          "name": [
            "TU Darmstadt, FB Informatik, Hochschulstrasse 10, 64289, Darmstadt, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mohamed", 
        "givenName": "Mohamed Saied Emam", 
        "id": "sg:person.010070273144.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010070273144.20"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Mathematical Sciences, University of Cincinnati, South China University of Technology"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cabarcas", 
        "givenName": "Daniel", 
        "id": "sg:person.015423657271.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015423657271.68"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Mathematical Sciences, University of Cincinnati, South China University of Technology"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ding", 
        "givenName": "Jintai", 
        "id": "sg:person.010723403013.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technical University of Darmstadt", 
          "id": "https://www.grid.ac/institutes/grid.6546.1", 
          "name": [
            "TU Darmstadt, FB Informatik, Hochschulstrasse 10, 64289, Darmstadt, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Buchmann", 
        "givenName": "Johannes", 
        "id": "sg:person.016400723075.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016400723075.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Center for Advanced Security Research Darmstadt (CASED)"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bulygin", 
        "givenName": "Stanislav", 
        "id": "sg:person.010425774147.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010425774147.54"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-45539-6_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000285811", 
          "https://doi.org/10.1007/3-540-45539-6_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-88403-3_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000585614", 
          "https://doi.org/10.1007/978-3-540-88403-3_14"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-88403-3_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000585614", 
          "https://doi.org/10.1007/978-3-540-88403-3_14"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/780506.780516", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007436250"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1015138233", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-0913-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015138233", 
          "https://doi.org/10.1007/978-1-4612-0913-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-0913-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015138233", 
          "https://doi.org/10.1007/978-1-4612-0913-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-10433-6_26", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030842749", 
          "https://doi.org/10.1007/978-3-642-10433-6_26"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-4049(99)00005-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040947089"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jsc.2008.02.017", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044270177"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-45146-4_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049476263", 
          "https://doi.org/10.1007/978-3-540-45146-4_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-45146-4_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049476263", 
          "https://doi.org/10.1007/978-3-540-45146-4_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/ietfec/e89-a.1.11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059669891"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "This paper introduces a new efficient algorithm, called MXL3, for computing Gr\u00f6bner 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\u00f6bner 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\u2019s implementation of F4.", 
    "editor": [
      {
        "familyName": "Lee", 
        "givenName": "Donghoon", 
        "type": "Person"
      }, 
      {
        "familyName": "Hong", 
        "givenName": "Seokhie", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-14423-3_7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-14422-6", 
        "978-3-642-14423-3"
      ], 
      "name": "Information, Security and Cryptology \u2013 ICISC 2009", 
      "type": "Book"
    }, 
    "name": "MXL3: An Efficient Algorithm for Computing Gr\u00f6bner Bases of Zero-Dimensional Ideals", 
    "pagination": "87-100", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041918753"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-14423-3_7"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "c7aed5f5c520ec8645be3c3052c0e78852a73e3cd780a46204a2c9e9f4a97c05"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-14423-3_7", 
      "https://app.dimensions.ai/details/publication/pub.1041918753"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:02", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000359_0000000359/records_29203_00000002.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-14423-3_7"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14423-3_7'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14423-3_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14423-3_7'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14423-3_7'


 

This table displays all metadata directly associated to this object as RDF triples.

138 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-14423-3_7 schema:about anzsrc-for:03
2 anzsrc-for:0307
3 schema:author N766ef2138b9a47d78a4c8bd110dcdbb9
4 schema:citation sg:pub.10.1007/3-540-45539-6_27
5 sg:pub.10.1007/978-1-4612-0913-3
6 sg:pub.10.1007/978-3-540-45146-4_3
7 sg:pub.10.1007/978-3-540-88403-3_14
8 sg:pub.10.1007/978-3-642-10433-6_26
9 https://app.dimensions.ai/details/publication/pub.1015138233
10 https://doi.org/10.1016/j.jsc.2008.02.017
11 https://doi.org/10.1016/s0022-4049(99)00005-5
12 https://doi.org/10.1093/ietfec/e89-a.1.11
13 https://doi.org/10.1145/780506.780516
14 schema:datePublished 2010
15 schema:datePublishedReg 2010-01-01
16 schema:description 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.
17 schema:editor Nf95d225e005f419da2fd8186bca0a3bb
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree false
21 schema:isPartOf N67d4f181774d41e7b56f4a3a605d6da4
22 schema:name MXL3: An Efficient Algorithm for Computing Gröbner Bases of Zero-Dimensional Ideals
23 schema:pagination 87-100
24 schema:productId N5455e07cdaf2450994d0ae5eaf9d4675
25 N7a50b13660174799996c6ff91f0872f9
26 Ne524ed6661724a41957f94611a411ed1
27 schema:publisher Nb1dc0ac7fef84e0380a1d52c3209bd46
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041918753
29 https://doi.org/10.1007/978-3-642-14423-3_7
30 schema:sdDatePublished 2019-04-16T08:02
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher N22895b4b715b4afcaa383eb513bfc3aa
33 schema:url https://link.springer.com/10.1007%2F978-3-642-14423-3_7
34 sgo:license sg:explorer/license/
35 sgo:sdDataset chapters
36 rdf:type schema:Chapter
37 N0f001ba566b448779a5192b947a934a4 schema:name Department of Mathematical Sciences, University of Cincinnati, South China University of Technology
38 rdf:type schema:Organization
39 N22895b4b715b4afcaa383eb513bfc3aa schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N371278e64f5a48dbb643038588d8a5ea schema:familyName Hong
42 schema:givenName Seokhie
43 rdf:type schema:Person
44 N46c0b7f2131d450ab411529ad9289e0e rdf:first sg:person.015423657271.68
45 rdf:rest Nf8fa34ce6d5f4eebbb3ed290e7cadccb
46 N5455e07cdaf2450994d0ae5eaf9d4675 schema:name doi
47 schema:value 10.1007/978-3-642-14423-3_7
48 rdf:type schema:PropertyValue
49 N67d4f181774d41e7b56f4a3a605d6da4 schema:isbn 978-3-642-14422-6
50 978-3-642-14423-3
51 schema:name Information, Security and Cryptology – ICISC 2009
52 rdf:type schema:Book
53 N737b5e955abe411f8f2dd2c03616f3e5 rdf:first sg:person.016400723075.52
54 rdf:rest Nbc9ea7f8d640479c87da7a4723ebe929
55 N766ef2138b9a47d78a4c8bd110dcdbb9 rdf:first sg:person.010070273144.20
56 rdf:rest N46c0b7f2131d450ab411529ad9289e0e
57 N7a50b13660174799996c6ff91f0872f9 schema:name dimensions_id
58 schema:value pub.1041918753
59 rdf:type schema:PropertyValue
60 N88659b7b5d2b47a08579441c13771f6b schema:name Center for Advanced Security Research Darmstadt (CASED)
61 rdf:type schema:Organization
62 Nb1dc0ac7fef84e0380a1d52c3209bd46 schema:location Berlin, Heidelberg
63 schema:name Springer Berlin Heidelberg
64 rdf:type schema:Organisation
65 Nbc9ea7f8d640479c87da7a4723ebe929 rdf:first sg:person.010425774147.54
66 rdf:rest rdf:nil
67 Nc3f378f571874b988257e77acd0257bd schema:familyName Lee
68 schema:givenName Donghoon
69 rdf:type schema:Person
70 Ne524ed6661724a41957f94611a411ed1 schema:name readcube_id
71 schema:value c7aed5f5c520ec8645be3c3052c0e78852a73e3cd780a46204a2c9e9f4a97c05
72 rdf:type schema:PropertyValue
73 Nf59c58b8775946dcbb5b5a2321f65ae7 rdf:first N371278e64f5a48dbb643038588d8a5ea
74 rdf:rest rdf:nil
75 Nf8fa34ce6d5f4eebbb3ed290e7cadccb rdf:first sg:person.010723403013.04
76 rdf:rest N737b5e955abe411f8f2dd2c03616f3e5
77 Nf95d225e005f419da2fd8186bca0a3bb rdf:first Nc3f378f571874b988257e77acd0257bd
78 rdf:rest Nf59c58b8775946dcbb5b5a2321f65ae7
79 Nfe10248f170242a6aee99f4f20534231 schema:name Department of Mathematical Sciences, University of Cincinnati, South China University of Technology
80 rdf:type schema:Organization
81 anzsrc-for:03 schema:inDefinedTermSet anzsrc-for:
82 schema:name Chemical Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0307 schema:inDefinedTermSet anzsrc-for:
85 schema:name Theoretical and Computational Chemistry
86 rdf:type schema:DefinedTerm
87 sg:person.010070273144.20 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
88 schema:familyName Mohamed
89 schema:givenName Mohamed Saied Emam
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010070273144.20
91 rdf:type schema:Person
92 sg:person.010425774147.54 schema:affiliation N88659b7b5d2b47a08579441c13771f6b
93 schema:familyName Bulygin
94 schema:givenName Stanislav
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010425774147.54
96 rdf:type schema:Person
97 sg:person.010723403013.04 schema:affiliation N0f001ba566b448779a5192b947a934a4
98 schema:familyName Ding
99 schema:givenName Jintai
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04
101 rdf:type schema:Person
102 sg:person.015423657271.68 schema:affiliation Nfe10248f170242a6aee99f4f20534231
103 schema:familyName Cabarcas
104 schema:givenName Daniel
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015423657271.68
106 rdf:type schema:Person
107 sg:person.016400723075.52 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
108 schema:familyName Buchmann
109 schema:givenName Johannes
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016400723075.52
111 rdf:type schema:Person
112 sg:pub.10.1007/3-540-45539-6_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000285811
113 https://doi.org/10.1007/3-540-45539-6_27
114 rdf:type schema:CreativeWork
115 sg:pub.10.1007/978-1-4612-0913-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015138233
116 https://doi.org/10.1007/978-1-4612-0913-3
117 rdf:type schema:CreativeWork
118 sg:pub.10.1007/978-3-540-45146-4_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049476263
119 https://doi.org/10.1007/978-3-540-45146-4_3
120 rdf:type schema:CreativeWork
121 sg:pub.10.1007/978-3-540-88403-3_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000585614
122 https://doi.org/10.1007/978-3-540-88403-3_14
123 rdf:type schema:CreativeWork
124 sg:pub.10.1007/978-3-642-10433-6_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030842749
125 https://doi.org/10.1007/978-3-642-10433-6_26
126 rdf:type schema:CreativeWork
127 https://app.dimensions.ai/details/publication/pub.1015138233 schema:CreativeWork
128 https://doi.org/10.1016/j.jsc.2008.02.017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044270177
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1016/s0022-4049(99)00005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040947089
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1093/ietfec/e89-a.1.11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059669891
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1145/780506.780516 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007436250
135 rdf:type schema:CreativeWork
136 https://www.grid.ac/institutes/grid.6546.1 schema:alternateName Technical University of Darmstadt
137 schema:name TU Darmstadt, FB Informatik, Hochschulstrasse 10, 64289, Darmstadt, Germany
138 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...