A Graph Theoretic Analysis of Double Base Number Systems
Double base number systems (DBNS) provide an elegant way to represent numbers. These representations also have many interesting and useful properties, which have been exploited to find many applications in Cryptography and Signal Processing. In the curren
- PDF / 472,124 Bytes
- 15 Pages / 430 x 660 pts Page_size
- 4 Downloads / 185 Views
Abstract. Double base number systems (DBNS) provide an elegant way to represent numbers. These representations also have many interesting and useful properties, which have been exploited to find many applications in Cryptography and Signal Processing. In the current article we present a scheme to represent numbers in double (and multi-) base format by combinatorial objects like graphs and diagraphs. The combinatorial representation leads to proof of some interesting results about the double and multibase representation of integers. These proofs are based on simple combinatorial arguments. In this article we have provided a graph theoretic proof of the recurrence relation satisfied by the number of double base representations of a given integer. The result has been further generalized to more than 2 bases. Also, we have uncovered some interesting properties of the sequence representing the number of double base representation of a positive integer n. It is expected that the combinatorial representation can serve as a tool for a better understanding of the double (and multi-) base number systems. Keywords: Double base number system, DBNS-graphs, MB-graphs.
1
Introduction
For last couple of years, there have been many papers emphasizing the use of double base number system (DBNS) in cryptography ([1,2,7,9,10,11,14,17,18]). In [6] and [15], authors have discussed elliptic curve scalar multiplication using a representation of the scalar in more than one bases. Double base number system, first time proposed in [13], is a non-traditional way of representing numbers. Unlike traditional systems, which use only one radix to represent numbers, DBNS uses 2 radii to represent a number. For example, if 2 and 3 are used as the radii, an integer n is expressed as sum of terms like ±2bi 3ti , where bi , ti are integers. Recently, in [17] an elliptic curve scalar multiplication scheme has been presented which uses 3 bases to represent the scalar. The proposed algorithm performs even better than its 2 base counterparts. This indicates that the DBNS can be easily generalized to more than 2 bases, which will greatly enhance their applicability to real life situations. The current article is devoted to analyse and explore some interesting propeties of double (and multi) base number system using combinatorial and graph theoretic arguments. K. Srinathan, C. Pandu Rangan, M. Yung (Eds.): Indocrypt 2007, LNCS 4859, pp. 152–166, 2007. c Springer-Verlag Berlin Heidelberg 2007
A Graph Theoretic Analysis of Double Base Number Systems
153
Graphs are very interesting combinatorial objects widely used in discrete mathematics and computer science. In the current article we will represent a number in DBNS by means of a bipartite graph or a diagraph. We will prove some interesting results about DBNS representations using simple combinatorial arguments on these objects. Usual arithmetic operations like addition, multiplication can now be described by graph theoretic operations. This representation may be of interest to people working in various
Data Loading...
