A Study on Near Canonic Representation of Double Base Number System and Multi-Base Number System

Abstract

Several algorithms have been proposed since the Elliptic Curve Cryptosystem was introduced in the field of cryptography to minimize the computational complexity and Double Base Number System (DBNS) was one of them. In this thesis, an algorithm has been discussed which may optimise the greedy algorithm and hence optimising the near canonic representation of an integer in Double Base Number System, which is important to perform basic arithmetic operations. Another algorithm has been discussed in the thesis on near canonic representation of an integer with three co-prime bases and four co-prime bases. A comparative study has been done as well between the newly proposed algorithm and the optimized greedy algorithm. A few experiments were performed to compare among Double base Chain, Triple Base Chain and Quintuple Base Chain and to compare between Joint Double Base Chain and Joint Triple Base Chain. The computed length for proposed algorithm is also O ((C log⁡x)/(log log⁡x )). An experiment was performed to compute the constant C for 3-integer and 4-integer expansions. Also, another study was done to compute the optimal second base for two dimensional logarithmic number system and the optimal second and third base combination for three dimensional logarithmic number system.