Energy-Efficient Software Implementation of Long Integer Modular Arithmetic View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Johann Großschädl , Roberto M. Avanzi , Erkay Savaş , Stefan Tillich

ABSTRACT

This paper investigates performance and energy characteristics of software algorithms for long integer arithmetic. We analyze and compare the number of RISC-like processor instructions (e.g. single-precision multiplication, addition, load, and store instructions) required for the execution of different algorithms such as Schoolbook multiplication, Karatsuba and Comba multiplication, as well as Montgomery reduction. Our analysis shows that a combination of Karatsuba-Comba multiplication and Montgomery reduction (the so-called KCM method) allows to achieve better performance than other algorithms for modular multiplication. Furthermore, we present a simple model to compare the energy-efficiency of arithmetic algorithms. This model considers the clock cycles and average current consumption of the base instructions to estimate the overall amount of energy consumed during the execution of an algorithm. Our experiments, conducted on a StrongARM SA-1100 processor, indicate that a 1024-bit KCM multiplication consumes about 22% less energy than other modular multiplication techniques. More... »

PAGES

75-90

Book

TITLE

Cryptographic Hardware and Embedded Systems – CHES 2005

ISBN

978-3-540-28474-1
978-3-540-31940-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11545262_6

DOI

http://dx.doi.org/10.1007/11545262_6

DIMENSIONS

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


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": "Graz University of Technology", 
          "id": "https://www.grid.ac/institutes/grid.410413.3", 
          "name": [
            "Institute for Applied Information Processing and Communications, Graz University of Technology, Inffeldgasse 16a, A\u20138010, Graz, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gro\u00dfsch\u00e4dl", 
        "givenName": "Johann", 
        "id": "sg:person.011275441722.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011275441722.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Ruhr University Bochum", 
          "id": "https://www.grid.ac/institutes/grid.5570.7", 
          "name": [
            "Faculty of Mathematics and Horst G\u00f6rtz Institute for IT-Security, Ruhr University Bochum, Universit\u00e4tsstrasse 150, D\u201344780, Bochum, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Avanzi", 
        "givenName": "Roberto M.", 
        "id": "sg:person.010554140307.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010554140307.42"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sabanc\u0131 University", 
          "id": "https://www.grid.ac/institutes/grid.5334.1", 
          "name": [
            "Faculty of Engineering and Natural Sciences, Sabanci University, Orhanli-Tuzla, TR\u201334956, Istanbul, Turkey"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sava\u015f", 
        "givenName": "Erkay", 
        "id": "sg:person.014042133177.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014042133177.60"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Graz University of Technology", 
          "id": "https://www.grid.ac/institutes/grid.410413.3", 
          "name": [
            "Institute for Applied Information Processing and Communications, Graz University of Technology, Inffeldgasse 16a, A\u20138010, Graz, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tillich", 
        "givenName": "Stefan", 
        "id": "sg:person.013345200075.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345200075.73"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/263272.263286", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001434784"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01130407", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014510782", 
          "https://doi.org/10.1007/bf01130407"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1022241315935", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031181585", 
          "https://doi.org/10.1023/a:1022241315935"
        ], 
        "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/978-1-4615-5685-5_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043534105", 
          "https://doi.org/10.1007/978-1-4615-5685-5_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/871506.871518", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053064908"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/40.502403", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061168196"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/92.335012", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061248249"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1147/sj.294.0526", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063184115"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/percom.2005.29", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094085969"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/dac.2001.935508", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098757858"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1109410941", 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "This paper investigates performance and energy characteristics of software algorithms for long integer arithmetic. We analyze and compare the number of RISC-like processor instructions (e.g. single-precision multiplication, addition, load, and store instructions) required for the execution of different algorithms such as Schoolbook multiplication, Karatsuba and Comba multiplication, as well as Montgomery reduction. Our analysis shows that a combination of Karatsuba-Comba multiplication and Montgomery reduction (the so-called KCM method) allows to achieve better performance than other algorithms for modular multiplication. Furthermore, we present a simple model to compare the energy-efficiency of arithmetic algorithms. This model considers the clock cycles and average current consumption of the base instructions to estimate the overall amount of energy consumed during the execution of an algorithm. Our experiments, conducted on a StrongARM SA-1100 processor, indicate that a 1024-bit KCM multiplication consumes about 22% less energy than other modular multiplication techniques.", 
    "editor": [
      {
        "familyName": "Rao", 
        "givenName": "Josyula R.", 
        "type": "Person"
      }, 
      {
        "familyName": "Sunar", 
        "givenName": "Berk", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11545262_6", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-28474-1", 
        "978-3-540-31940-5"
      ], 
      "name": "Cryptographic Hardware and Embedded Systems \u2013 CHES 2005", 
      "type": "Book"
    }, 
    "name": "Energy-Efficient Software Implementation of Long Integer Modular Arithmetic", 
    "pagination": "75-90", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044926321"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11545262_6"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d5ff6d53a9c1b7dfc2c15fc3d3bc72b765918abad0531c4d18b02283094594b5"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11545262_6", 
      "https://app.dimensions.ai/details/publication/pub.1044926321"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07:30", 
    "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/0000000356_0000000356/records_57883_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11545262_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/11545262_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/11545262_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11545262_6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11545262_6'


 

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

139 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11545262_6 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N34495e4b175640a0b5da6c1e66cf16cd
4 schema:citation sg:pub.10.1007/3-540-46877-3_21
5 sg:pub.10.1007/978-1-4615-5685-5_15
6 sg:pub.10.1007/bf01130407
7 sg:pub.10.1023/a:1022241315935
8 https://app.dimensions.ai/details/publication/pub.1109410941
9 https://doi.org/10.1090/s0025-5718-1985-0777282-x
10 https://doi.org/10.1109/40.502403
11 https://doi.org/10.1109/92.335012
12 https://doi.org/10.1109/dac.2001.935508
13 https://doi.org/10.1109/percom.2005.29
14 https://doi.org/10.1145/263272.263286
15 https://doi.org/10.1145/871506.871518
16 https://doi.org/10.1147/sj.294.0526
17 schema:datePublished 2005
18 schema:datePublishedReg 2005-01-01
19 schema:description This paper investigates performance and energy characteristics of software algorithms for long integer arithmetic. We analyze and compare the number of RISC-like processor instructions (e.g. single-precision multiplication, addition, load, and store instructions) required for the execution of different algorithms such as Schoolbook multiplication, Karatsuba and Comba multiplication, as well as Montgomery reduction. Our analysis shows that a combination of Karatsuba-Comba multiplication and Montgomery reduction (the so-called KCM method) allows to achieve better performance than other algorithms for modular multiplication. Furthermore, we present a simple model to compare the energy-efficiency of arithmetic algorithms. This model considers the clock cycles and average current consumption of the base instructions to estimate the overall amount of energy consumed during the execution of an algorithm. Our experiments, conducted on a StrongARM SA-1100 processor, indicate that a 1024-bit KCM multiplication consumes about 22% less energy than other modular multiplication techniques.
20 schema:editor N6bab6653f607463aa4b7556a11f9027b
21 schema:genre chapter
22 schema:inLanguage en
23 schema:isAccessibleForFree true
24 schema:isPartOf Nafd84cb255ea4caf8e87f3d6c56c0c70
25 schema:name Energy-Efficient Software Implementation of Long Integer Modular Arithmetic
26 schema:pagination 75-90
27 schema:productId N413355818e87471f8d44dfe40cdcf1a3
28 N68e75a2107334bc7bf15edfec9a2a5d0
29 Nae81839be29d485b8cef90f8c30836b8
30 schema:publisher N7b9074154e014b43876e0a52377046df
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044926321
32 https://doi.org/10.1007/11545262_6
33 schema:sdDatePublished 2019-04-16T07:30
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher Ndea64c39f6194ad7ab6d7af677c8a79b
36 schema:url https://link.springer.com/10.1007%2F11545262_6
37 sgo:license sg:explorer/license/
38 sgo:sdDataset chapters
39 rdf:type schema:Chapter
40 N1f72e7a771024d159aa1a492d478f6bf rdf:first sg:person.010554140307.42
41 rdf:rest Ndf2d873968e948a9b48ab03c4e41ecf2
42 N34495e4b175640a0b5da6c1e66cf16cd rdf:first sg:person.011275441722.34
43 rdf:rest N1f72e7a771024d159aa1a492d478f6bf
44 N40096816393e401692a5fff862da31d6 rdf:first N4581f42a4cd0419c91766f58f6d1e4cb
45 rdf:rest rdf:nil
46 N413355818e87471f8d44dfe40cdcf1a3 schema:name readcube_id
47 schema:value d5ff6d53a9c1b7dfc2c15fc3d3bc72b765918abad0531c4d18b02283094594b5
48 rdf:type schema:PropertyValue
49 N4581f42a4cd0419c91766f58f6d1e4cb schema:familyName Sunar
50 schema:givenName Berk
51 rdf:type schema:Person
52 N617c2b186c9147fe9d921dd00fb6c612 schema:familyName Rao
53 schema:givenName Josyula R.
54 rdf:type schema:Person
55 N68e75a2107334bc7bf15edfec9a2a5d0 schema:name doi
56 schema:value 10.1007/11545262_6
57 rdf:type schema:PropertyValue
58 N69177e3afba3464abefb9d8d105c35ca rdf:first sg:person.013345200075.73
59 rdf:rest rdf:nil
60 N6bab6653f607463aa4b7556a11f9027b rdf:first N617c2b186c9147fe9d921dd00fb6c612
61 rdf:rest N40096816393e401692a5fff862da31d6
62 N7b9074154e014b43876e0a52377046df schema:location Berlin, Heidelberg
63 schema:name Springer Berlin Heidelberg
64 rdf:type schema:Organisation
65 Nae81839be29d485b8cef90f8c30836b8 schema:name dimensions_id
66 schema:value pub.1044926321
67 rdf:type schema:PropertyValue
68 Nafd84cb255ea4caf8e87f3d6c56c0c70 schema:isbn 978-3-540-28474-1
69 978-3-540-31940-5
70 schema:name Cryptographic Hardware and Embedded Systems – CHES 2005
71 rdf:type schema:Book
72 Ndea64c39f6194ad7ab6d7af677c8a79b schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 Ndf2d873968e948a9b48ab03c4e41ecf2 rdf:first sg:person.014042133177.60
75 rdf:rest N69177e3afba3464abefb9d8d105c35ca
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
80 schema:name Computation Theory and Mathematics
81 rdf:type schema:DefinedTerm
82 sg:person.010554140307.42 schema:affiliation https://www.grid.ac/institutes/grid.5570.7
83 schema:familyName Avanzi
84 schema:givenName Roberto M.
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010554140307.42
86 rdf:type schema:Person
87 sg:person.011275441722.34 schema:affiliation https://www.grid.ac/institutes/grid.410413.3
88 schema:familyName Großschädl
89 schema:givenName Johann
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011275441722.34
91 rdf:type schema:Person
92 sg:person.013345200075.73 schema:affiliation https://www.grid.ac/institutes/grid.410413.3
93 schema:familyName Tillich
94 schema:givenName Stefan
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345200075.73
96 rdf:type schema:Person
97 sg:person.014042133177.60 schema:affiliation https://www.grid.ac/institutes/grid.5334.1
98 schema:familyName Savaş
99 schema:givenName Erkay
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014042133177.60
101 rdf:type schema:Person
102 sg:pub.10.1007/3-540-46877-3_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031645149
103 https://doi.org/10.1007/3-540-46877-3_21
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/978-1-4615-5685-5_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043534105
106 https://doi.org/10.1007/978-1-4615-5685-5_15
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/bf01130407 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014510782
109 https://doi.org/10.1007/bf01130407
110 rdf:type schema:CreativeWork
111 sg:pub.10.1023/a:1022241315935 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031181585
112 https://doi.org/10.1023/a:1022241315935
113 rdf:type schema:CreativeWork
114 https://app.dimensions.ai/details/publication/pub.1109410941 schema:CreativeWork
115 https://doi.org/10.1090/s0025-5718-1985-0777282-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1041482767
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1109/40.502403 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061168196
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1109/92.335012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061248249
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1109/dac.2001.935508 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098757858
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1109/percom.2005.29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094085969
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1145/263272.263286 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001434784
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1145/871506.871518 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053064908
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1147/sj.294.0526 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063184115
130 rdf:type schema:CreativeWork
131 https://www.grid.ac/institutes/grid.410413.3 schema:alternateName Graz University of Technology
132 schema:name Institute for Applied Information Processing and Communications, Graz University of Technology, Inffeldgasse 16a, A–8010, Graz, Austria
133 rdf:type schema:Organization
134 https://www.grid.ac/institutes/grid.5334.1 schema:alternateName Sabancı University
135 schema:name Faculty of Engineering and Natural Sciences, Sabanci University, Orhanli-Tuzla, TR–34956, Istanbul, Turkey
136 rdf:type schema:Organization
137 https://www.grid.ac/institutes/grid.5570.7 schema:alternateName Ruhr University Bochum
138 schema:name Faculty of Mathematics and Horst Görtz Institute for IT-Security, Ruhr University Bochum, Universitätsstrasse 150, D–44780, Bochum, Germany
139 rdf:type schema:Organization
 




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


...