Montgomery Multiplication on the Cell View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Joppe W. Bos , Marcelo E. Kaihara

ABSTRACT

A technique to speed up Montgomery multiplication targeted at the Synergistic Processor Elements (SPE) of the Cell Broadband Engine is proposed. The technique consists of splitting a number into four consecutive parts. These parts are placed one by one in each of the four element positions of a vector, representing columns in a 4-SIMD organization. This representation enables arithmetic to be performed in a 4-SIMD fashion. An implementation of the Montgomery multiplication using this technique is up to 2.47 times faster compared to an unrolled implementation of Montgomery multiplication, which is part of the IBM multi-precision math library, for odd moduli of length 160 to 2048 bits. The presented technique can also be applied to speed up Montgomery multiplication on other SIMD-architectures. More... »

PAGES

477-485

References to SciGraph publications

  • 2009. Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate in ADVANCES IN CRYPTOLOGY - CRYPTO 2009
  • 2001-07-13. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems in ADVANCES IN CRYPTOLOGY — CRYPTO ’96
  • 2009. Fast Elliptic-Curve Cryptography on the Cell Broadband Engine in PROGRESS IN CRYPTOLOGY – AFRICACRYPT 2009
  • 1986. Use of Elliptic Curves in Cryptography in ADVANCES IN CRYPTOLOGY — CRYPTO ’85 PROCEEDINGS
  • Book

    TITLE

    Parallel Processing and Applied Mathematics

    ISBN

    978-3-642-14389-2
    978-3-642-14390-8

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-14390-8_50

    DOI

    http://dx.doi.org/10.1007/978-3-642-14390-8_50

    DIMENSIONS

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


    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/1005", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Communications Technologies", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/10", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Technology", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne", 
              "id": "https://www.grid.ac/institutes/grid.5333.6", 
              "name": [
                "Laboratory for Cryptologic Algorithms, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL), CH-1015, Lausanne, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bos", 
            "givenName": "Joppe W.", 
            "id": "sg:person.011356726653.68", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011356726653.68"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne", 
              "id": "https://www.grid.ac/institutes/grid.5333.6", 
              "name": [
                "Laboratory for Cryptologic Algorithms, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL), CH-1015, Lausanne, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kaihara", 
            "givenName": "Marcelo E.", 
            "id": "sg:person.015710024243.12", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015710024243.12"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-02384-2_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004091122", 
              "https://doi.org/10.1007/978-3-642-02384-2_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/359340.359342", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013337011"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-39799-x_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022380878", 
              "https://doi.org/10.1007/3-540-39799-x_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0025-5718-1987-0866109-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022745146"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03356-8_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037125946", 
              "https://doi.org/10.1007/978-3-642-03356-8_4"
            ], 
            "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-68697-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047972271", 
              "https://doi.org/10.1007/3-540-68697-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-68697-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047972271", 
              "https://doi.org/10.1007/3-540-68697-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1049/el:19991230", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1056788977"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/hpca.2005.26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094158096"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010", 
        "datePublishedReg": "2010-01-01", 
        "description": "A technique to speed up Montgomery multiplication targeted at the Synergistic Processor Elements (SPE) of the Cell Broadband Engine is proposed. The technique consists of splitting a number into four consecutive parts. These parts are placed one by one in each of the four element positions of a vector, representing columns in a 4-SIMD organization. This representation enables arithmetic to be performed in a 4-SIMD fashion. An implementation of the Montgomery multiplication using this technique is up to 2.47 times faster compared to an unrolled implementation of Montgomery multiplication, which is part of the IBM multi-precision math library, for odd moduli of length 160 to 2048 bits. The presented technique can also be applied to speed up Montgomery multiplication on other SIMD-architectures.", 
        "editor": [
          {
            "familyName": "Wyrzykowski", 
            "givenName": "Roman", 
            "type": "Person"
          }, 
          {
            "familyName": "Dongarra", 
            "givenName": "Jack", 
            "type": "Person"
          }, 
          {
            "familyName": "Karczewski", 
            "givenName": "Konrad", 
            "type": "Person"
          }, 
          {
            "familyName": "Wasniewski", 
            "givenName": "Jerzy", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-14390-8_50", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-642-14389-2", 
            "978-3-642-14390-8"
          ], 
          "name": "Parallel Processing and Applied Mathematics", 
          "type": "Book"
        }, 
        "name": "Montgomery Multiplication on the Cell", 
        "pagination": "477-485", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1041484288"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-14390-8_50"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "c59ea69fd46a5d28c4844e45891764f654b5a8ca87b5d2adaba2ec740c6a3a61"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-14390-8_50", 
          "https://app.dimensions.ai/details/publication/pub.1041484288"
        ], 
        "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_29200_00000002.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-14390-8_50"
      }
    ]
     

    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-14390-8_50'

    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-14390-8_50'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14390-8_50'

    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-14390-8_50'


     

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

    118 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-14390-8_50 schema:about anzsrc-for:10
    2 anzsrc-for:1005
    3 schema:author N43add9f882da4acc81dafe375d21fb7d
    4 schema:citation sg:pub.10.1007/3-540-39799-x_31
    5 sg:pub.10.1007/3-540-68697-5_9
    6 sg:pub.10.1007/978-3-642-02384-2_23
    7 sg:pub.10.1007/978-3-642-03356-8_4
    8 https://doi.org/10.1049/el:19991230
    9 https://doi.org/10.1090/s0025-5718-1985-0777282-x
    10 https://doi.org/10.1090/s0025-5718-1987-0866109-5
    11 https://doi.org/10.1109/hpca.2005.26
    12 https://doi.org/10.1145/359340.359342
    13 schema:datePublished 2010
    14 schema:datePublishedReg 2010-01-01
    15 schema:description A technique to speed up Montgomery multiplication targeted at the Synergistic Processor Elements (SPE) of the Cell Broadband Engine is proposed. The technique consists of splitting a number into four consecutive parts. These parts are placed one by one in each of the four element positions of a vector, representing columns in a 4-SIMD organization. This representation enables arithmetic to be performed in a 4-SIMD fashion. An implementation of the Montgomery multiplication using this technique is up to 2.47 times faster compared to an unrolled implementation of Montgomery multiplication, which is part of the IBM multi-precision math library, for odd moduli of length 160 to 2048 bits. The presented technique can also be applied to speed up Montgomery multiplication on other SIMD-architectures.
    16 schema:editor N31fe98c36bd84445b8b95e600c39f580
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf N0736f549105344e398f476d274f4e8f8
    21 schema:name Montgomery Multiplication on the Cell
    22 schema:pagination 477-485
    23 schema:productId N243f4bd554d543faa0239ced57cea6cc
    24 Nbf4d722b71b948d1be1229cb72e92e3d
    25 Nd7f99655dfc841f196d43e396085eadf
    26 schema:publisher N39813d1d61834911a578dce74a6cec26
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041484288
    28 https://doi.org/10.1007/978-3-642-14390-8_50
    29 schema:sdDatePublished 2019-04-16T08:02
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N7c471257ea22416b93c4a1df14a5b8a8
    32 schema:url https://link.springer.com/10.1007%2F978-3-642-14390-8_50
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N0736f549105344e398f476d274f4e8f8 schema:isbn 978-3-642-14389-2
    37 978-3-642-14390-8
    38 schema:name Parallel Processing and Applied Mathematics
    39 rdf:type schema:Book
    40 N23a004cc01824e7bab386d28cf3ac0f0 rdf:first N4abf860a5c8d4c5faa6116f60ad5a1de
    41 rdf:rest Nf6f269f0772349129cc96cd49112e5c1
    42 N243f4bd554d543faa0239ced57cea6cc schema:name doi
    43 schema:value 10.1007/978-3-642-14390-8_50
    44 rdf:type schema:PropertyValue
    45 N31fe98c36bd84445b8b95e600c39f580 rdf:first Nd4967f2d251c4d6587c422d764d3912e
    46 rdf:rest N9f8bae8613c04396ad37d2e4049f93db
    47 N39813d1d61834911a578dce74a6cec26 schema:location Berlin, Heidelberg
    48 schema:name Springer Berlin Heidelberg
    49 rdf:type schema:Organisation
    50 N43add9f882da4acc81dafe375d21fb7d rdf:first sg:person.011356726653.68
    51 rdf:rest N86aa6c64f1514452ad2e097a49c596f8
    52 N4abf860a5c8d4c5faa6116f60ad5a1de schema:familyName Karczewski
    53 schema:givenName Konrad
    54 rdf:type schema:Person
    55 N4eaf91eae5d54f0aaa9fb4c3850a2309 schema:familyName Dongarra
    56 schema:givenName Jack
    57 rdf:type schema:Person
    58 N7c471257ea22416b93c4a1df14a5b8a8 schema:name Springer Nature - SN SciGraph project
    59 rdf:type schema:Organization
    60 N807c1479dcea4779bef849e335ee81af schema:familyName Wasniewski
    61 schema:givenName Jerzy
    62 rdf:type schema:Person
    63 N86aa6c64f1514452ad2e097a49c596f8 rdf:first sg:person.015710024243.12
    64 rdf:rest rdf:nil
    65 N9f8bae8613c04396ad37d2e4049f93db rdf:first N4eaf91eae5d54f0aaa9fb4c3850a2309
    66 rdf:rest N23a004cc01824e7bab386d28cf3ac0f0
    67 Nbf4d722b71b948d1be1229cb72e92e3d schema:name dimensions_id
    68 schema:value pub.1041484288
    69 rdf:type schema:PropertyValue
    70 Nd4967f2d251c4d6587c422d764d3912e schema:familyName Wyrzykowski
    71 schema:givenName Roman
    72 rdf:type schema:Person
    73 Nd7f99655dfc841f196d43e396085eadf schema:name readcube_id
    74 schema:value c59ea69fd46a5d28c4844e45891764f654b5a8ca87b5d2adaba2ec740c6a3a61
    75 rdf:type schema:PropertyValue
    76 Nf6f269f0772349129cc96cd49112e5c1 rdf:first N807c1479dcea4779bef849e335ee81af
    77 rdf:rest rdf:nil
    78 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Technology
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Communications Technologies
    83 rdf:type schema:DefinedTerm
    84 sg:person.011356726653.68 schema:affiliation https://www.grid.ac/institutes/grid.5333.6
    85 schema:familyName Bos
    86 schema:givenName Joppe W.
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011356726653.68
    88 rdf:type schema:Person
    89 sg:person.015710024243.12 schema:affiliation https://www.grid.ac/institutes/grid.5333.6
    90 schema:familyName Kaihara
    91 schema:givenName Marcelo E.
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015710024243.12
    93 rdf:type schema:Person
    94 sg:pub.10.1007/3-540-39799-x_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022380878
    95 https://doi.org/10.1007/3-540-39799-x_31
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/3-540-68697-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047972271
    98 https://doi.org/10.1007/3-540-68697-5_9
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/978-3-642-02384-2_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004091122
    101 https://doi.org/10.1007/978-3-642-02384-2_23
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/978-3-642-03356-8_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037125946
    104 https://doi.org/10.1007/978-3-642-03356-8_4
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1049/el:19991230 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056788977
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1090/s0025-5718-1985-0777282-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1041482767
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1090/s0025-5718-1987-0866109-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022745146
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1109/hpca.2005.26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094158096
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1145/359340.359342 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013337011
    115 rdf:type schema:CreativeWork
    116 https://www.grid.ac/institutes/grid.5333.6 schema:alternateName École Polytechnique Fédérale de Lausanne
    117 schema:name Laboratory for Cryptologic Algorithms, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015, Lausanne, Switzerland
    118 rdf:type schema:Organization
     




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


    ...