Multiplication as parallel as possible View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1992

AUTHORS

P. Lippitsch , K. C. Posch , R. Posch

ABSTRACT

Public key encryption/decryption with modulus arithmetic is used in a variety of cryptographic applications. A tough computational problem arises due to the very long integer arithmetic needed. Usually serial-parallel multiplication is employed, which slows down speed to the order of k=log 2(n), where n is the modulus. This paper describes a possible implementation of a method using parallel multiplication schemes at the order of log(k) in combination with incomplete modulus reduction. As many partial products as possible are implemented in parallel (As Parallel As Possible, APAP). This leads to a mixture of linear and logarithmic time complexity. This paper describes a hardware solution for the APAP-multiplier with optimized dynamic adder cells without storage elements. Additional available silicon area can be traded against speedup in a smooth way. The underlying method is described and proved in [Posch90]. Using 664 bit long operands, a 40mm2 chip manufactured in 1.2 micron CMOS technology can reach an RSA encryption/decryption rate of 240 kbits/second. More... »

PAGES

350-358

Book

TITLE

Parallel Computation

ISBN

978-3-540-55437-0
978-3-540-47073-1

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-55437-8_91

DOI

http://dx.doi.org/10.1007/3-540-55437-8_91

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "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": "Graz University of Technology", 
          "id": "https://www.grid.ac/institutes/grid.410413.3", 
          "name": [
            "Department of Applied Information Processing and Communications Technology, Graz University of Technology, Klosterwiesgasse 32/I, A-8010\u00a0Graz, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lippitsch", 
        "givenName": "P.", 
        "id": "sg:person.016310031024.53", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016310031024.53"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Graz University of Technology", 
          "id": "https://www.grid.ac/institutes/grid.410413.3", 
          "name": [
            "Department of Applied Information Processing and Communications Technology, Graz University of Technology, Klosterwiesgasse 32/I, A-8010\u00a0Graz, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Posch", 
        "givenName": "K. C.", 
        "id": "sg:person.013270133353.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013270133353.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Graz University of Technology", 
          "id": "https://www.grid.ac/institutes/grid.410413.3", 
          "name": [
            "Department of Applied Information Processing and Communications Technology, Graz University of Technology, Klosterwiesgasse 32/I, A-8010\u00a0Graz, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Posch", 
        "givenName": "R.", 
        "id": "sg:person.011236005071.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011236005071.18"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0165-6074(90)90004-s", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009964316"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0165-6074(90)90004-s", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009964316"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/359340.359342", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013337011"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/pgec.1964.263830", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061435213"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tc.1985.1676634", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061533246"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1992", 
    "datePublishedReg": "1992-01-01", 
    "description": "Public key encryption/decryption with modulus arithmetic is used in a variety of cryptographic applications. A tough computational problem arises due to the very long integer arithmetic needed. Usually serial-parallel multiplication is employed, which slows down speed to the order of k=log 2(n), where n is the modulus. This paper describes a possible implementation of a method using parallel multiplication schemes at the order of log(k) in combination with incomplete modulus reduction. As many partial products as possible are implemented in parallel (As Parallel As Possible, APAP). This leads to a mixture of linear and logarithmic time complexity. This paper describes a hardware solution for the APAP-multiplier with optimized dynamic adder cells without storage elements. Additional available silicon area can be traded against speedup in a smooth way. The underlying method is described and proved in [Posch90]. Using 664 bit long operands, a 40mm2 chip manufactured in 1.2 micron CMOS technology can reach an RSA encryption/decryption rate of 240 kbits/second.", 
    "editor": [
      {
        "familyName": "Zima", 
        "givenName": "Hans P.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-55437-8_91", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-55437-0", 
        "978-3-540-47073-1"
      ], 
      "name": "Parallel Computation", 
      "type": "Book"
    }, 
    "name": "Multiplication as parallel as possible", 
    "pagination": "350-358", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-55437-8_91"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f32ee4650782ef59e7a78a53ff217ec8bb0284cb2f378e7a3479eb6ebdb8b7a9"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051049843"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-55437-8_91", 
      "https://app.dimensions.ai/details/publication/pub.1051049843"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T12: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_8660_00000595.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-55437-8_91"
  }
]
 

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/3-540-55437-8_91'

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/3-540-55437-8_91'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-55437-8_91'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-55437-8_91'


 

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

91 TRIPLES      23 PREDICATES      31 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-55437-8_91 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nd3ad69b4a8a54fe8a4a567c689ca1dcf
4 schema:citation https://doi.org/10.1016/0165-6074(90)90004-s
5 https://doi.org/10.1109/pgec.1964.263830
6 https://doi.org/10.1109/tc.1985.1676634
7 https://doi.org/10.1145/359340.359342
8 schema:datePublished 1992
9 schema:datePublishedReg 1992-01-01
10 schema:description Public key encryption/decryption with modulus arithmetic is used in a variety of cryptographic applications. A tough computational problem arises due to the very long integer arithmetic needed. Usually serial-parallel multiplication is employed, which slows down speed to the order of k=log 2(n), where n is the modulus. This paper describes a possible implementation of a method using parallel multiplication schemes at the order of log(k) in combination with incomplete modulus reduction. As many partial products as possible are implemented in parallel (As Parallel As Possible, APAP). This leads to a mixture of linear and logarithmic time complexity. This paper describes a hardware solution for the APAP-multiplier with optimized dynamic adder cells without storage elements. Additional available silicon area can be traded against speedup in a smooth way. The underlying method is described and proved in [Posch90]. Using 664 bit long operands, a 40mm2 chip manufactured in 1.2 micron CMOS technology can reach an RSA encryption/decryption rate of 240 kbits/second.
11 schema:editor Nc403c74f3cd74c3a81226ef722ab0c83
12 schema:genre chapter
13 schema:inLanguage en
14 schema:isAccessibleForFree false
15 schema:isPartOf N69beaf02cb6842fd9b6a57c22899e985
16 schema:name Multiplication as parallel as possible
17 schema:pagination 350-358
18 schema:productId N45bf7584040f47f1ac3d046223ef95cc
19 N5b3a216394d24b1db2c302ea6559caee
20 Nf61590e685f449cda0123c754f091c6e
21 schema:publisher N164e858d7871421aad719faa528e5319
22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051049843
23 https://doi.org/10.1007/3-540-55437-8_91
24 schema:sdDatePublished 2019-04-15T12:12
25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
26 schema:sdPublisher Nab2ebcb841a94962ab813b5a05d2054e
27 schema:url http://link.springer.com/10.1007/3-540-55437-8_91
28 sgo:license sg:explorer/license/
29 sgo:sdDataset chapters
30 rdf:type schema:Chapter
31 N164e858d7871421aad719faa528e5319 schema:location Berlin, Heidelberg
32 schema:name Springer Berlin Heidelberg
33 rdf:type schema:Organisation
34 N45bf7584040f47f1ac3d046223ef95cc schema:name readcube_id
35 schema:value f32ee4650782ef59e7a78a53ff217ec8bb0284cb2f378e7a3479eb6ebdb8b7a9
36 rdf:type schema:PropertyValue
37 N5b3a216394d24b1db2c302ea6559caee schema:name dimensions_id
38 schema:value pub.1051049843
39 rdf:type schema:PropertyValue
40 N69beaf02cb6842fd9b6a57c22899e985 schema:isbn 978-3-540-47073-1
41 978-3-540-55437-0
42 schema:name Parallel Computation
43 rdf:type schema:Book
44 N797e6a4a68ea4405bbbf779de0d99308 rdf:first sg:person.013270133353.59
45 rdf:rest N7e52173ebe3549c9bbfca72a19980f30
46 N7e52173ebe3549c9bbfca72a19980f30 rdf:first sg:person.011236005071.18
47 rdf:rest rdf:nil
48 N809af7c0db904eb4a38efdce96fd1409 schema:familyName Zima
49 schema:givenName Hans P.
50 rdf:type schema:Person
51 Nab2ebcb841a94962ab813b5a05d2054e schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 Nc403c74f3cd74c3a81226ef722ab0c83 rdf:first N809af7c0db904eb4a38efdce96fd1409
54 rdf:rest rdf:nil
55 Nd3ad69b4a8a54fe8a4a567c689ca1dcf rdf:first sg:person.016310031024.53
56 rdf:rest N797e6a4a68ea4405bbbf779de0d99308
57 Nf61590e685f449cda0123c754f091c6e schema:name doi
58 schema:value 10.1007/3-540-55437-8_91
59 rdf:type schema:PropertyValue
60 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
61 schema:name Information and Computing Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
64 schema:name Data Format
65 rdf:type schema:DefinedTerm
66 sg:person.011236005071.18 schema:affiliation https://www.grid.ac/institutes/grid.410413.3
67 schema:familyName Posch
68 schema:givenName R.
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011236005071.18
70 rdf:type schema:Person
71 sg:person.013270133353.59 schema:affiliation https://www.grid.ac/institutes/grid.410413.3
72 schema:familyName Posch
73 schema:givenName K. C.
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013270133353.59
75 rdf:type schema:Person
76 sg:person.016310031024.53 schema:affiliation https://www.grid.ac/institutes/grid.410413.3
77 schema:familyName Lippitsch
78 schema:givenName P.
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016310031024.53
80 rdf:type schema:Person
81 https://doi.org/10.1016/0165-6074(90)90004-s schema:sameAs https://app.dimensions.ai/details/publication/pub.1009964316
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1109/pgec.1964.263830 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061435213
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1109/tc.1985.1676634 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533246
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1145/359340.359342 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013337011
88 rdf:type schema:CreativeWork
89 https://www.grid.ac/institutes/grid.410413.3 schema:alternateName Graz University of Technology
90 schema:name Department of Applied Information Processing and Communications Technology, Graz University of Technology, Klosterwiesgasse 32/I, A-8010 Graz, Austria
91 rdf:type schema:Organization
 




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


...