MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Mohamed Saied Emam Mohamed , Wael Said Abd Elmageed Mohamed , Jintai Ding , Johannes Buchmann

ABSTRACT

MutantXL is an algorithm for solving systems of polynomial equations that was proposed at SCC 2008. This paper proposes two substantial improvements to this algorithm over GF(2) that result in significantly reduced memory usage. We present experimental results comparing MXL2 to the XL algorithm, the MutantXL algorithm and Magma’s implementation of F4. For this comparison we have chosen small, randomly generated instances of the MQ problem and quadratic systems derived from HFE instances. In both cases, the largest matrices produced by MXL2 are substantially smaller than the ones produced by MutantXL and XL. Moreover, for a significant number of cases we even see a reduction of the size of the largest matrix when we compare MXL2 against Magma’s F4 implementation. More... »

PAGES

203-215

References to SciGraph publications

Book

TITLE

Post-Quantum Cryptography

ISBN

978-3-540-88402-6
978-3-540-88403-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-88403-3_14

DOI

http://dx.doi.org/10.1007/978-3-540-88403-3_14

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical 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": {
          "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": "Wael Said Abd Elmageed", 
        "id": "sg:person.013634073236.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013634073236.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Cincinnati", 
          "id": "https://www.grid.ac/institutes/grid.24827.3b", 
          "name": [
            "Department of Mathematical Sciences, University of Cincinnati, OH 45220, Cincinnati, USA"
          ], 
          "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"
      }
    ], 
    "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": "https://doi.org/10.1080/00927879908826559", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008867318"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-24632-9_22", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028117877", 
          "https://doi.org/10.1007/978-3-540-24632-9_22"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45961-8_39", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035601256", 
          "https://doi.org/10.1007/3-540-45961-8_39"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49649-1_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038271412", 
          "https://doi.org/10.1007/3-540-49649-1_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49649-1_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038271412", 
          "https://doi.org/10.1007/3-540-49649-1_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-68339-9_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051894160", 
          "https://doi.org/10.1007/3-540-68339-9_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-68339-9_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051894160", 
          "https://doi.org/10.1007/3-540-68339-9_4"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2008", 
    "datePublishedReg": "2008-01-01", 
    "description": "MutantXL is an algorithm for solving systems of polynomial equations that was proposed at SCC 2008. This paper proposes two substantial improvements to this algorithm over GF(2) that result in significantly reduced memory usage. We present experimental results comparing MXL2 to the XL algorithm, the MutantXL algorithm and Magma\u2019s implementation of F4. For this comparison we have chosen small, randomly generated instances of the MQ problem and quadratic systems derived from HFE instances. In both cases, the largest matrices produced by MXL2 are substantially smaller than the ones produced by MutantXL and XL. Moreover, for a significant number of cases we even see a reduction of the size of the largest matrix when we compare MXL2 against Magma\u2019s F4 implementation.", 
    "editor": [
      {
        "familyName": "Buchmann", 
        "givenName": "Johannes", 
        "type": "Person"
      }, 
      {
        "familyName": "Ding", 
        "givenName": "Jintai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-88403-3_14", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-88402-6", 
        "978-3-540-88403-3"
      ], 
      "name": "Post-Quantum Cryptography", 
      "type": "Book"
    }, 
    "name": "MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy", 
    "pagination": "203-215", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-88403-3_14"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "02c9e6fde289aa84375e24f5211970256bd76bd846c543bb1ec558f583a3101b"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000585614"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-88403-3_14", 
      "https://app.dimensions.ai/details/publication/pub.1000585614"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T06:11", 
    "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/0000000350_0000000350/records_77581_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-88403-3_14"
  }
]
 

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-540-88403-3_14'

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-540-88403-3_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-88403-3_14'

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-540-88403-3_14'


 

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

117 TRIPLES      23 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-88403-3_14 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N342cf90faedf49b3b7e10462d2580626
4 schema:citation sg:pub.10.1007/3-540-45539-6_27
5 sg:pub.10.1007/3-540-45961-8_39
6 sg:pub.10.1007/3-540-49649-1_4
7 sg:pub.10.1007/3-540-68339-9_4
8 sg:pub.10.1007/978-3-540-24632-9_22
9 https://doi.org/10.1080/00927879908826559
10 schema:datePublished 2008
11 schema:datePublishedReg 2008-01-01
12 schema:description MutantXL is an algorithm for solving systems of polynomial equations that was proposed at SCC 2008. This paper proposes two substantial improvements to this algorithm over GF(2) that result in significantly reduced memory usage. We present experimental results comparing MXL2 to the XL algorithm, the MutantXL algorithm and Magma’s implementation of F4. For this comparison we have chosen small, randomly generated instances of the MQ problem and quadratic systems derived from HFE instances. In both cases, the largest matrices produced by MXL2 are substantially smaller than the ones produced by MutantXL and XL. Moreover, for a significant number of cases we even see a reduction of the size of the largest matrix when we compare MXL2 against Magma’s F4 implementation.
13 schema:editor Ne2ee9f4da881475189d8cc101d3b0ed6
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree true
17 schema:isPartOf N90863174f628490dbff8e2b6e72e6cb1
18 schema:name MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy
19 schema:pagination 203-215
20 schema:productId N24ba24205d81414eb03c9fbf899105ec
21 N2abd76278770410595fecd1a8e284bfd
22 N6e9b4981d61e4ca5a10f9debc5db88c2
23 schema:publisher N5aea8bea99374592b315b8c353164663
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000585614
25 https://doi.org/10.1007/978-3-540-88403-3_14
26 schema:sdDatePublished 2019-04-16T06:11
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N8cff5729a95d42208ed1ab58eb1f60ae
29 schema:url https://link.springer.com/10.1007%2F978-3-540-88403-3_14
30 sgo:license sg:explorer/license/
31 sgo:sdDataset chapters
32 rdf:type schema:Chapter
33 N0df546cdb71b4d9cabff025d5abc1c60 schema:familyName Buchmann
34 schema:givenName Johannes
35 rdf:type schema:Person
36 N178c5db290c8476abe41c0d515870e7d rdf:first sg:person.013634073236.45
37 rdf:rest N2543fd038df24ac0bc2b8ec31ed79be9
38 N24ba24205d81414eb03c9fbf899105ec schema:name doi
39 schema:value 10.1007/978-3-540-88403-3_14
40 rdf:type schema:PropertyValue
41 N2543fd038df24ac0bc2b8ec31ed79be9 rdf:first sg:person.010723403013.04
42 rdf:rest N7f8bc2be7e44403ca44224d060353713
43 N2abd76278770410595fecd1a8e284bfd schema:name dimensions_id
44 schema:value pub.1000585614
45 rdf:type schema:PropertyValue
46 N342cf90faedf49b3b7e10462d2580626 rdf:first sg:person.010070273144.20
47 rdf:rest N178c5db290c8476abe41c0d515870e7d
48 N5aea8bea99374592b315b8c353164663 schema:location Berlin, Heidelberg
49 schema:name Springer Berlin Heidelberg
50 rdf:type schema:Organisation
51 N6e9b4981d61e4ca5a10f9debc5db88c2 schema:name readcube_id
52 schema:value 02c9e6fde289aa84375e24f5211970256bd76bd846c543bb1ec558f583a3101b
53 rdf:type schema:PropertyValue
54 N7f8bc2be7e44403ca44224d060353713 rdf:first sg:person.016400723075.52
55 rdf:rest rdf:nil
56 N8cff5729a95d42208ed1ab58eb1f60ae schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 N8f2771eb37e24058af7d32ad176b7588 rdf:first Nd3fd86b408b14a848ba9980ed9465f51
59 rdf:rest rdf:nil
60 N90863174f628490dbff8e2b6e72e6cb1 schema:isbn 978-3-540-88402-6
61 978-3-540-88403-3
62 schema:name Post-Quantum Cryptography
63 rdf:type schema:Book
64 Nd3fd86b408b14a848ba9980ed9465f51 schema:familyName Ding
65 schema:givenName Jintai
66 rdf:type schema:Person
67 Ne2ee9f4da881475189d8cc101d3b0ed6 rdf:first N0df546cdb71b4d9cabff025d5abc1c60
68 rdf:rest N8f2771eb37e24058af7d32ad176b7588
69 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
70 schema:name Mathematical Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
73 schema:name Pure Mathematics
74 rdf:type schema:DefinedTerm
75 sg:person.010070273144.20 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
76 schema:familyName Mohamed
77 schema:givenName Mohamed Saied Emam
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010070273144.20
79 rdf:type schema:Person
80 sg:person.010723403013.04 schema:affiliation https://www.grid.ac/institutes/grid.24827.3b
81 schema:familyName Ding
82 schema:givenName Jintai
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04
84 rdf:type schema:Person
85 sg:person.013634073236.45 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
86 schema:familyName Mohamed
87 schema:givenName Wael Said Abd Elmageed
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013634073236.45
89 rdf:type schema:Person
90 sg:person.016400723075.52 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
91 schema:familyName Buchmann
92 schema:givenName Johannes
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016400723075.52
94 rdf:type schema:Person
95 sg:pub.10.1007/3-540-45539-6_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000285811
96 https://doi.org/10.1007/3-540-45539-6_27
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/3-540-45961-8_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035601256
99 https://doi.org/10.1007/3-540-45961-8_39
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/3-540-49649-1_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038271412
102 https://doi.org/10.1007/3-540-49649-1_4
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/3-540-68339-9_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051894160
105 https://doi.org/10.1007/3-540-68339-9_4
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/978-3-540-24632-9_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028117877
108 https://doi.org/10.1007/978-3-540-24632-9_22
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1080/00927879908826559 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008867318
111 rdf:type schema:CreativeWork
112 https://www.grid.ac/institutes/grid.24827.3b schema:alternateName University of Cincinnati
113 schema:name Department of Mathematical Sciences, University of Cincinnati, OH 45220, Cincinnati, USA
114 rdf:type schema:Organization
115 https://www.grid.ac/institutes/grid.6546.1 schema:alternateName Technical University of Darmstadt
116 schema:name TU Darmstadt, FB Informatik, Hochschulstrasse 10, 64289, Darmstadt, Germany
117 rdf:type schema:Organization
 




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


...