Efficient Multiplication Using Type 2 Optimal Normal Bases View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2007

AUTHORS

Joachim von zur Gathen , Amin Shokrollahi , Jamshid Shokrollahi

ABSTRACT

In this paper we propose a new structure for multiplication using optimal normal bases of type 2. The multiplier uses an efficient linear transformation to convert the normal basis representations of elements of \(\mathbb{F}_{q^{n}}\) to suitable polynomials of degree at most n over \(\mathbb{F}_{q}\). These polynomials are multiplied using any method which is suitable for the implementation platform, then the product is converted back to the normal basis using the inverse of the above transformation. The efficiency of the transformation arises from a special factorization of its matrix into sparse matrices. This factorization — which resembles the FFT factorization of the DFT matrix — allows to compute the transformation and its inverse using O(n logn) operations in \(\mathbb{F}_{q}\), rather than O(n 2) operations needed for a general change of basis. Using this technique we can reduce the asymptotic cost of multiplication in optimal normal bases of type 2 from reported by Gao et al. (2000) to M(n) + O(n logn) operations in \(\mathbb{F}_{q}\), where M(n) is the number of \(\mathbb{F}_{q}\)-operations to multiply two polynomials of degree n − 1 over \(\mathbb{F}_{q}\). We show that this cost is also smaller than other proposed multipliers for n > 160, values which are used in elliptic curve cryptography. More... »

PAGES

55-68

References to SciGraph publications

  • 1992-12. Optimal normal bases in DESIGNS, CODES AND CRYPTOGRAPHY
  • 2006. Efficient FPGA-Based Karatsuba Multipliers for Polynomials over in SELECTED AREAS IN CRYPTOGRAPHY
  • 2005-09. Polynomial and Normal Bases for Finite Fields in JOURNAL OF CRYPTOLOGY
  • 2002-02-08. Efficient Finite Field Basis Conversion Involving dual bases in CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS
  • Book

    TITLE

    Arithmetic of Finite Fields

    ISBN

    978-3-540-73073-6
    978-3-540-73074-3

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-73074-3_6

    DOI

    http://dx.doi.org/10.1007/978-3-540-73074-3_6

    DIMENSIONS

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


    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": "Bonn Aachen International Center for Information Technology", 
              "id": "https://www.grid.ac/institutes/grid.469360.e", 
              "name": [
                "B-IT, Dahlmannstr. 2, Universit\u00e4t Bonn, 53113 Bonn, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "von zur Gathen", 
            "givenName": "Joachim", 
            "id": "sg:person.013654024753.29", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013654024753.29"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne", 
              "id": "https://www.grid.ac/institutes/grid.5333.6", 
              "name": [
                "ALGO, Station 14, Batiment BC, EPFL, 1015 Lausanne, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Shokrollahi", 
            "givenName": "Amin", 
            "id": "sg:person.012145056067.52", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012145056067.52"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Bonn Aachen International Center for Information Technology", 
              "id": "https://www.grid.ac/institutes/grid.469360.e", 
              "name": [
                "B-IT, Dahlmannstr. 2, Universit\u00e4t Bonn, 53113 Bonn, Germany, current address: System Security Group, Ruhr-Universit\u00e4t Bochum, D-44780 Bochum, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Shokrollahi", 
            "givenName": "Jamshid", 
            "id": "sg:person.015660075425.37", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015660075425.37"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1006/jsco.1999.0309", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020473052"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(88)90090-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025417667"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00125200", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028104815", 
              "https://doi.org/10.1007/bf00125200"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00125200", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028104815", 
              "https://doi.org/10.1007/bf00125200"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00145-004-0221-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029078491", 
              "https://doi.org/10.1007/s00145-004-0221-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48059-5_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029888792", 
              "https://doi.org/10.1007/3-540-48059-5_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48059-5_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029888792", 
              "https://doi.org/10.1007/3-540-48059-5_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11693383_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046111389", 
              "https://doi.org/10.1007/11693383_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11693383_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046111389", 
              "https://doi.org/10.1007/11693383_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/12.902754", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061089312"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.2002.1004590", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061533688"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.2005.120", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061534071"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.2005.120", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061534071"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007", 
        "datePublishedReg": "2007-01-01", 
        "description": "In this paper we propose a new structure for multiplication using optimal normal bases of type 2. The multiplier uses an efficient linear transformation to convert the normal basis representations of elements of \\(\\mathbb{F}_{q^{n}}\\) to suitable polynomials of degree at most n over \\(\\mathbb{F}_{q}\\). These polynomials are multiplied using any method which is suitable for the implementation platform, then the product is converted back to the normal basis using the inverse of the above transformation. The efficiency of the transformation arises from a special factorization of its matrix into sparse matrices. This factorization \u2014 which resembles the FFT factorization of the DFT matrix \u2014 allows to compute the transformation and its inverse using O(n logn) operations in \\(\\mathbb{F}_{q}\\), rather than O(n 2) operations needed for a general change of basis. Using this technique we can reduce the asymptotic cost of multiplication in optimal normal bases of type 2 from reported by Gao et al.\u00a0(2000) to M(n)\u2009+\u2009O(n logn) operations in \\(\\mathbb{F}_{q}\\), where M(n) is the number of \\(\\mathbb{F}_{q}\\)-operations to multiply two polynomials of degree n\u2009\u2212\u20091 over \\(\\mathbb{F}_{q}\\). We show that this cost is also smaller than other proposed multipliers for n\u2009>\u2009160, values which are used in elliptic curve cryptography.", 
        "editor": [
          {
            "familyName": "Carlet", 
            "givenName": "Claude", 
            "type": "Person"
          }, 
          {
            "familyName": "Sunar", 
            "givenName": "Berk", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-73074-3_6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-73073-6", 
            "978-3-540-73074-3"
          ], 
          "name": "Arithmetic of Finite Fields", 
          "type": "Book"
        }, 
        "name": "Efficient Multiplication Using Type 2 Optimal Normal Bases", 
        "pagination": "55-68", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-73074-3_6"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "a08584caeeffba35dbe031b3db37e11ccd25d33674632e88681b1e5927e6a9cd"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1033696916"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-73074-3_6", 
          "https://app.dimensions.ai/details/publication/pub.1033696916"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T18:12", 
        "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/0000000001_0000000264/records_8681_00000264.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-540-73074-3_6"
      }
    ]
     

    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-73074-3_6'

    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-73074-3_6'

    Turtle is a human-readable linked data format.

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

    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-73074-3_6'


     

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

    119 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-73074-3_6 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N2637fe927ad84c32bc6476bdcb798f1d
    4 schema:citation sg:pub.10.1007/11693383_25
    5 sg:pub.10.1007/3-540-48059-5_13
    6 sg:pub.10.1007/bf00125200
    7 sg:pub.10.1007/s00145-004-0221-0
    8 https://doi.org/10.1006/jsco.1999.0309
    9 https://doi.org/10.1016/0166-218x(88)90090-x
    10 https://doi.org/10.1109/12.902754
    11 https://doi.org/10.1109/tc.2002.1004590
    12 https://doi.org/10.1109/tc.2005.120
    13 schema:datePublished 2007
    14 schema:datePublishedReg 2007-01-01
    15 schema:description In this paper we propose a new structure for multiplication using optimal normal bases of type 2. The multiplier uses an efficient linear transformation to convert the normal basis representations of elements of \(\mathbb{F}_{q^{n}}\) to suitable polynomials of degree at most n over \(\mathbb{F}_{q}\). These polynomials are multiplied using any method which is suitable for the implementation platform, then the product is converted back to the normal basis using the inverse of the above transformation. The efficiency of the transformation arises from a special factorization of its matrix into sparse matrices. This factorization — which resembles the FFT factorization of the DFT matrix — allows to compute the transformation and its inverse using O(n logn) operations in \(\mathbb{F}_{q}\), rather than O(n 2) operations needed for a general change of basis. Using this technique we can reduce the asymptotic cost of multiplication in optimal normal bases of type 2 from reported by Gao et al. (2000) to M(n) + O(n logn) operations in \(\mathbb{F}_{q}\), where M(n) is the number of \(\mathbb{F}_{q}\)-operations to multiply two polynomials of degree n − 1 over \(\mathbb{F}_{q}\). We show that this cost is also smaller than other proposed multipliers for n > 160, values which are used in elliptic curve cryptography.
    16 schema:editor N353e35be96df411eb21cc8d122a3b55c
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf N83013b27ea184aa2a565f0752419eb71
    21 schema:name Efficient Multiplication Using Type 2 Optimal Normal Bases
    22 schema:pagination 55-68
    23 schema:productId N03e2168abe884b6f933d54d5dcfa911f
    24 N3b841ec2acdd439a99d80783692062eb
    25 N7518a3c066174b85a10863b91a62a2be
    26 schema:publisher N1a1dbc5d2910437f84613bed6535f59b
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033696916
    28 https://doi.org/10.1007/978-3-540-73074-3_6
    29 schema:sdDatePublished 2019-04-15T18:12
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N7d30eb5a61924060909aa3ea3da7532c
    32 schema:url http://link.springer.com/10.1007/978-3-540-73074-3_6
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N0190cf9de3ad45f8b5d926ccce396999 rdf:first sg:person.012145056067.52
    37 rdf:rest N23694414b6c2484ca8f0aa991b74f5b6
    38 N03e2168abe884b6f933d54d5dcfa911f schema:name dimensions_id
    39 schema:value pub.1033696916
    40 rdf:type schema:PropertyValue
    41 N1a1dbc5d2910437f84613bed6535f59b schema:location Berlin, Heidelberg
    42 schema:name Springer Berlin Heidelberg
    43 rdf:type schema:Organisation
    44 N23694414b6c2484ca8f0aa991b74f5b6 rdf:first sg:person.015660075425.37
    45 rdf:rest rdf:nil
    46 N2637fe927ad84c32bc6476bdcb798f1d rdf:first sg:person.013654024753.29
    47 rdf:rest N0190cf9de3ad45f8b5d926ccce396999
    48 N2df65cd3d0ae4654b84f3f979467a634 schema:familyName Carlet
    49 schema:givenName Claude
    50 rdf:type schema:Person
    51 N2f1586d4322c476694a5f777116fdefe rdf:first N33d54465f6d344959bf9e4a9d9784c84
    52 rdf:rest rdf:nil
    53 N33d54465f6d344959bf9e4a9d9784c84 schema:familyName Sunar
    54 schema:givenName Berk
    55 rdf:type schema:Person
    56 N353e35be96df411eb21cc8d122a3b55c rdf:first N2df65cd3d0ae4654b84f3f979467a634
    57 rdf:rest N2f1586d4322c476694a5f777116fdefe
    58 N3b841ec2acdd439a99d80783692062eb schema:name readcube_id
    59 schema:value a08584caeeffba35dbe031b3db37e11ccd25d33674632e88681b1e5927e6a9cd
    60 rdf:type schema:PropertyValue
    61 N7518a3c066174b85a10863b91a62a2be schema:name doi
    62 schema:value 10.1007/978-3-540-73074-3_6
    63 rdf:type schema:PropertyValue
    64 N7d30eb5a61924060909aa3ea3da7532c schema:name Springer Nature - SN SciGraph project
    65 rdf:type schema:Organization
    66 N83013b27ea184aa2a565f0752419eb71 schema:isbn 978-3-540-73073-6
    67 978-3-540-73074-3
    68 schema:name Arithmetic of Finite Fields
    69 rdf:type schema:Book
    70 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Mathematical Sciences
    72 rdf:type schema:DefinedTerm
    73 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Pure Mathematics
    75 rdf:type schema:DefinedTerm
    76 sg:person.012145056067.52 schema:affiliation https://www.grid.ac/institutes/grid.5333.6
    77 schema:familyName Shokrollahi
    78 schema:givenName Amin
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012145056067.52
    80 rdf:type schema:Person
    81 sg:person.013654024753.29 schema:affiliation https://www.grid.ac/institutes/grid.469360.e
    82 schema:familyName von zur Gathen
    83 schema:givenName Joachim
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013654024753.29
    85 rdf:type schema:Person
    86 sg:person.015660075425.37 schema:affiliation https://www.grid.ac/institutes/grid.469360.e
    87 schema:familyName Shokrollahi
    88 schema:givenName Jamshid
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015660075425.37
    90 rdf:type schema:Person
    91 sg:pub.10.1007/11693383_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046111389
    92 https://doi.org/10.1007/11693383_25
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/3-540-48059-5_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029888792
    95 https://doi.org/10.1007/3-540-48059-5_13
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/bf00125200 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028104815
    98 https://doi.org/10.1007/bf00125200
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/s00145-004-0221-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029078491
    101 https://doi.org/10.1007/s00145-004-0221-0
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1006/jsco.1999.0309 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020473052
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/0166-218x(88)90090-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1025417667
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1109/12.902754 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061089312
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1109/tc.2002.1004590 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533688
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1109/tc.2005.120 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061534071
    112 rdf:type schema:CreativeWork
    113 https://www.grid.ac/institutes/grid.469360.e schema:alternateName Bonn Aachen International Center for Information Technology
    114 schema:name B-IT, Dahlmannstr. 2, Universität Bonn, 53113 Bonn, Germany
    115 B-IT, Dahlmannstr. 2, Universität Bonn, 53113 Bonn, Germany, current address: System Security Group, Ruhr-Universität Bochum, D-44780 Bochum, Germany
    116 rdf:type schema:Organization
    117 https://www.grid.ac/institutes/grid.5333.6 schema:alternateName École Polytechnique Fédérale de Lausanne
    118 schema:name ALGO, Station 14, Batiment BC, EPFL, 1015 Lausanne, Switzerland
    119 rdf:type schema:Organization
     




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


    ...