Back to search

University of Waterloo

Efficient Integer Representations for Cryptographic Operations

Abstract

dc:description.abstract

Every positive integer has a unique radix 2 representation which uses the digits {0,1}. However, if we allow digits other than 0 and 1, say {0,1,-1}, then a positive integer has many representations. Of these <i>redundant</i> representations, it is possible to choose one that has few nonzero digits. It is well known that using representations of integers with few nonzero digits allows certain algebraic operations to be done more quickly. This thesis is concerned with various representations of integers that are related to efficient implementations of algebraic operations in cryptographic algorithms. The topics covered here include: <ul> <li> <i>The width-w nonadjacent form (w-NAF)</i>. We prove that the <i>w</i>-NAF of an integer has a minimal number of nonzero digits; that is, no other representation of an integer, which uses the <i>w</i>-NAF digits, can have fewer nonzero digits than its <i>w</i>-NAF. </li> <li><i>A left-to-right analogue of the w-NAF</i>. We introduce a new family of radix 2 representations which use the same digits as the <i>w</i>-NAF, but have the property that they can be computed by sliding a window from left to right across the binary representation of an integer. We show these new representations have a minimal number of nonzero digits. </li> <li><i>Joint representations</i>. Solinas introduced a {0,1,-1}-radix 2 representation for pairs of integers called the joint sparse form. We consider generalizations of the joint sparse form which represent <i>r</i>&ge;2 integers and use digits other than {0,1,-1}. We show how to construct a {0,1,2,3}-joint representation that has a minimal number of nonzero columns. </li> <li><i>Nonadjacent digit sets</i>. It is well known that if <i>x</i> equals 3 or -1 then every nonnegative integer has a unique {0,1,<i>x</i>}-nonadjacent form; that is, a {0,1,<i>x</i>}-radix 2 representation with the property that, of any two consecutive digits, at most one is nonzero. We investigate what other values of <i>x</i> have this property. </li> </ul>

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2004

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Muir, James

Subjects

dc:subject × 6

Rights

dc:rights
Statement dc:rights
  • Copyright: 2004, Muir, James. All rights reserved.
Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/1099

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Muir, James. Efficient Integer Representations for Cryptographic Operations. University of Waterloo, 2004. http://hdl.handle.net/10012/1099