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

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 Ndd3960e6606a440db5eabb3e3bc9d6b9
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 Nd12ae79130844fd1821acc9f5726b2a2
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree false
21 schema:isPartOf N76a67c4fc65f4652aeffcbb36108aabe
22 schema:name MXL3: An Efficient Algorithm for Computing Gröbner Bases of Zero-Dimensional Ideals
23 schema:pagination 87-100
24 schema:productId N3069c9e596ae4f4c919fbc6a488bc5c3
25 N6c1e41eaf3f444718863513270f8b824
26 Nf7ff099847884897ad8f1c36d61bc142
27 schema:publisher Nfbd2408c1427415cb4dfbdce8bbaa7ff
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 N2a3716a931744612a178668ccb9ed6b9
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 N005a23bc807948b3ae9a2484324ddbcc rdf:first sg:person.010425774147.54
38 rdf:rest rdf:nil
39 N0b04848a9d0e4a7db0ae810b100e9a42 rdf:first sg:person.015423657271.68
40 rdf:rest Na8f05dbb6df64d0a8ee87c997700a860
41 N1396364180f5421e83d1247641cb04f6 schema:familyName Lee
42 schema:givenName Donghoon
43 rdf:type schema:Person
44 N2a3716a931744612a178668ccb9ed6b9 schema:name Springer Nature - SN SciGraph project
45 rdf:type schema:Organization
46 N3069c9e596ae4f4c919fbc6a488bc5c3 schema:name doi
47 schema:value 10.1007/978-3-642-14423-3_7
48 rdf:type schema:PropertyValue
49 N332a3293f40f49e2bebc428ff27c1b17 rdf:first Nd5576d26498f471c9b974f975c349040
50 rdf:rest rdf:nil
51 N6170f3d94f39409ba30e9c9dae0dcafa schema:name Department of Mathematical Sciences, University of Cincinnati, South China University of Technology
52 rdf:type schema:Organization
53 N6c1e41eaf3f444718863513270f8b824 schema:name readcube_id
54 schema:value c7aed5f5c520ec8645be3c3052c0e78852a73e3cd780a46204a2c9e9f4a97c05
55 rdf:type schema:PropertyValue
56 N6eea660cb2ec43da829e24b46e9435d6 schema:name Center for Advanced Security Research Darmstadt (CASED)
57 rdf:type schema:Organization
58 N76a67c4fc65f4652aeffcbb36108aabe schema:isbn 978-3-642-14422-6
59 978-3-642-14423-3
60 schema:name Information, Security and Cryptology – ICISC 2009
61 rdf:type schema:Book
62 Na8f05dbb6df64d0a8ee87c997700a860 rdf:first sg:person.010723403013.04
63 rdf:rest Nb8743c0853b441d38a42a638e8d56235
64 Nb8743c0853b441d38a42a638e8d56235 rdf:first sg:person.016400723075.52
65 rdf:rest N005a23bc807948b3ae9a2484324ddbcc
66 Nd12ae79130844fd1821acc9f5726b2a2 rdf:first N1396364180f5421e83d1247641cb04f6
67 rdf:rest N332a3293f40f49e2bebc428ff27c1b17
68 Nd4bf3408a4044d788d42120f8e5bb24e schema:name Department of Mathematical Sciences, University of Cincinnati, South China University of Technology
69 rdf:type schema:Organization
70 Nd5576d26498f471c9b974f975c349040 schema:familyName Hong
71 schema:givenName Seokhie
72 rdf:type schema:Person
73 Ndd3960e6606a440db5eabb3e3bc9d6b9 rdf:first sg:person.010070273144.20
74 rdf:rest N0b04848a9d0e4a7db0ae810b100e9a42
75 Nf7ff099847884897ad8f1c36d61bc142 schema:name dimensions_id
76 schema:value pub.1041918753
77 rdf:type schema:PropertyValue
78 Nfbd2408c1427415cb4dfbdce8bbaa7ff schema:location Berlin, Heidelberg
79 schema:name Springer Berlin Heidelberg
80 rdf:type schema:Organisation
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 N6eea660cb2ec43da829e24b46e9435d6
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 N6170f3d94f39409ba30e9c9dae0dcafa
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 Nd4bf3408a4044d788d42120f8e5bb24e
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)


...