Montgomery Multiplication in GF(2k) View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1998-04

AUTHORS

Cetin K. Koc, Tolga Acar

ABSTRACT

We show that the multiplication operation c=a · b · r-1 in the field GF(2k can be implemented significantly faster in software than the standard multiplication, where r is a special fixed element of the field. This operation is the finite field analogue of the Montgomery multiplication for modular multiplication of integers. We give the bit-level and word-level algorithms for computing the product, perform a thorough performance analysis, and compare the algorithm to the standard multiplication algorithm in GF(2k. The Montgomery multiplication can be used to obtain fast software implementations of the discrete exponentiation operation, and is particularly suitable for cryptographic applications where k is large. More... »

PAGES

57-69

References to SciGraph publications

  • 2001-05-18. Public-Key Cryptosystems with Very Small Key Lengths in ADVANCES IN CRYPTOLOGY — EUROCRYPT’ 92
  • 2001-05-18. A Cryptographic Library for the Motorola DSP56000 in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’90
  • 2005-06-26. A fast software implementation for arithmetic operations in GF(2n) in ADVANCES IN CRYPTOLOGY — ASIACRYPT '96
  • 1991-01. An implementation for a fast public-key cryptosystem in JOURNAL OF CRYPTOLOGY
  • 2001-07-13. Fast Key Exchange with Elliptic Curve Systems in ADVANCES IN CRYPTOLOGY — CRYPT0’ 95
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1008208521515

    DOI

    http://dx.doi.org/10.1023/a:1008208521515

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Oregon State University", 
              "id": "https://www.grid.ac/institutes/grid.4391.f", 
              "name": [
                "Electrical and Computer Engineering, Oregon State University, Corvallis, 97331, Oregon"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Koc", 
            "givenName": "Cetin K.", 
            "id": "sg:person.011276776763.01", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011276776763.01"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Oregon State University", 
              "id": "https://www.grid.ac/institutes/grid.4391.f", 
              "name": [
                "Electrical and Computer Engineering, Oregon State University, Corvallis, 97331, Oregon"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Acar", 
            "givenName": "Tolga", 
            "id": "sg:person.010520540023.13", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010520540023.13"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf00196789", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020123700", 
              "https://doi.org/10.1007/bf00196789"
            ], 
            "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/bfb0034836", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026882213", 
              "https://doi.org/10.1007/bfb0034836"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-47555-9_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030622134", 
              "https://doi.org/10.1007/3-540-47555-9_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-47555-9_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030622134", 
              "https://doi.org/10.1007/3-540-47555-9_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46877-3_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031645149", 
              "https://doi.org/10.1007/3-540-46877-3_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46877-3_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031645149", 
              "https://doi.org/10.1007/3-540-46877-3_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0025-5718-1985-0777282-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041482767"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44750-4_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048478958", 
              "https://doi.org/10.1007/3-540-44750-4_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44750-4_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048478958", 
              "https://doi.org/10.1007/3-540-44750-4_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/49.223883", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061176862"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.1976.1055638", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061647862"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1998-04", 
        "datePublishedReg": "1998-04-01", 
        "description": "We show that the multiplication operation c=a \u00b7 b \u00b7 r-1 in the field GF(2k can be implemented significantly faster in software than the standard multiplication, where r is a special fixed element of the field. This operation is the finite field analogue of the Montgomery multiplication for modular multiplication of integers. We give the bit-level and word-level algorithms for computing the product, perform a thorough performance analysis, and compare the algorithm to the standard multiplication algorithm in GF(2k. The Montgomery multiplication can be used to obtain fast software implementations of the discrete exponentiation operation, and is particularly suitable for cryptographic applications where k is large.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1023/a:1008208521515", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136552", 
            "issn": [
              "0925-1022", 
              "1573-7586"
            ], 
            "name": "Designs, Codes and Cryptography", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "14"
          }
        ], 
        "name": "Montgomery Multiplication in GF(2k)", 
        "pagination": "57-69", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "0d72dd99f2b70702e6a3c6ba30aa8791f9596e1d20cd3f27a88ff7896d9d8385"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1008208521515"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1002824065"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1008208521515", 
          "https://app.dimensions.ai/details/publication/pub.1002824065"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T21:33", 
        "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_8687_00000498.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1023/A:1008208521515"
      }
    ]
     

    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.1023/a:1008208521515'

    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.1023/a:1008208521515'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1008208521515'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1008208521515'


     

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

    100 TRIPLES      21 PREDICATES      36 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1008208521515 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N813b1e990e6a4bc1a63c7d94e7e60a0b
    4 schema:citation sg:pub.10.1007/3-540-44750-4_4
    5 sg:pub.10.1007/3-540-46877-3_21
    6 sg:pub.10.1007/3-540-47555-9_14
    7 sg:pub.10.1007/bf00196789
    8 sg:pub.10.1007/bfb0034836
    9 https://doi.org/10.1016/0166-218x(88)90090-x
    10 https://doi.org/10.1090/s0025-5718-1985-0777282-x
    11 https://doi.org/10.1109/49.223883
    12 https://doi.org/10.1109/tit.1976.1055638
    13 schema:datePublished 1998-04
    14 schema:datePublishedReg 1998-04-01
    15 schema:description We show that the multiplication operation c=a · b · r-1 in the field GF(2k can be implemented significantly faster in software than the standard multiplication, where r is a special fixed element of the field. This operation is the finite field analogue of the Montgomery multiplication for modular multiplication of integers. We give the bit-level and word-level algorithms for computing the product, perform a thorough performance analysis, and compare the algorithm to the standard multiplication algorithm in GF(2k. The Montgomery multiplication can be used to obtain fast software implementations of the discrete exponentiation operation, and is particularly suitable for cryptographic applications where k is large.
    16 schema:genre research_article
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf N27d05475be2c41eab6f838c0f0911573
    20 Nf67fc7f2402d48e18a5b6ea089565812
    21 sg:journal.1136552
    22 schema:name Montgomery Multiplication in GF(2k)
    23 schema:pagination 57-69
    24 schema:productId N4a68614c53334f9c8bbea3cbdd9df70d
    25 N6eaa3978c9d3437485185b7ba58ae47d
    26 Nbb25cedb6df946079eb78223f1ed4142
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002824065
    28 https://doi.org/10.1023/a:1008208521515
    29 schema:sdDatePublished 2019-04-10T21:33
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher Nb5cfcf1c3b2249d5ba3b6bdb8a2801ae
    32 schema:url http://link.springer.com/10.1023/A:1008208521515
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset articles
    35 rdf:type schema:ScholarlyArticle
    36 N179d28d1ce2e440cb2d29a25dc7b89d2 rdf:first sg:person.010520540023.13
    37 rdf:rest rdf:nil
    38 N27d05475be2c41eab6f838c0f0911573 schema:issueNumber 1
    39 rdf:type schema:PublicationIssue
    40 N4a68614c53334f9c8bbea3cbdd9df70d schema:name readcube_id
    41 schema:value 0d72dd99f2b70702e6a3c6ba30aa8791f9596e1d20cd3f27a88ff7896d9d8385
    42 rdf:type schema:PropertyValue
    43 N6eaa3978c9d3437485185b7ba58ae47d schema:name doi
    44 schema:value 10.1023/a:1008208521515
    45 rdf:type schema:PropertyValue
    46 N813b1e990e6a4bc1a63c7d94e7e60a0b rdf:first sg:person.011276776763.01
    47 rdf:rest N179d28d1ce2e440cb2d29a25dc7b89d2
    48 Nb5cfcf1c3b2249d5ba3b6bdb8a2801ae schema:name Springer Nature - SN SciGraph project
    49 rdf:type schema:Organization
    50 Nbb25cedb6df946079eb78223f1ed4142 schema:name dimensions_id
    51 schema:value pub.1002824065
    52 rdf:type schema:PropertyValue
    53 Nf67fc7f2402d48e18a5b6ea089565812 schema:volumeNumber 14
    54 rdf:type schema:PublicationVolume
    55 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    56 schema:name Information and Computing Sciences
    57 rdf:type schema:DefinedTerm
    58 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    59 schema:name Computation Theory and Mathematics
    60 rdf:type schema:DefinedTerm
    61 sg:journal.1136552 schema:issn 0925-1022
    62 1573-7586
    63 schema:name Designs, Codes and Cryptography
    64 rdf:type schema:Periodical
    65 sg:person.010520540023.13 schema:affiliation https://www.grid.ac/institutes/grid.4391.f
    66 schema:familyName Acar
    67 schema:givenName Tolga
    68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010520540023.13
    69 rdf:type schema:Person
    70 sg:person.011276776763.01 schema:affiliation https://www.grid.ac/institutes/grid.4391.f
    71 schema:familyName Koc
    72 schema:givenName Cetin K.
    73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011276776763.01
    74 rdf:type schema:Person
    75 sg:pub.10.1007/3-540-44750-4_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048478958
    76 https://doi.org/10.1007/3-540-44750-4_4
    77 rdf:type schema:CreativeWork
    78 sg:pub.10.1007/3-540-46877-3_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031645149
    79 https://doi.org/10.1007/3-540-46877-3_21
    80 rdf:type schema:CreativeWork
    81 sg:pub.10.1007/3-540-47555-9_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030622134
    82 https://doi.org/10.1007/3-540-47555-9_14
    83 rdf:type schema:CreativeWork
    84 sg:pub.10.1007/bf00196789 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020123700
    85 https://doi.org/10.1007/bf00196789
    86 rdf:type schema:CreativeWork
    87 sg:pub.10.1007/bfb0034836 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026882213
    88 https://doi.org/10.1007/bfb0034836
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1016/0166-218x(88)90090-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1025417667
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1090/s0025-5718-1985-0777282-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1041482767
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1109/49.223883 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061176862
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1109/tit.1976.1055638 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061647862
    97 rdf:type schema:CreativeWork
    98 https://www.grid.ac/institutes/grid.4391.f schema:alternateName Oregon State University
    99 schema:name Electrical and Computer Engineering, Oregon State University, Corvallis, 97331, Oregon
    100 rdf:type schema:Organization
     




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


    ...