Triple-Base Number System for Scalar Multiplication

The triple-base number system is used to speed up scalar multiplication. At present, the main methods to calculate a triple-base chain are greedy algorithms. We propose a new method, called the add/sub algorithm, to calculate scalar multiplication. The density of such chains gained by this algorithm with base {2, 3, 5} is

$\frac{1}{5.61426}$

. It saves 22% additions compared with the binary/ternary method; 22.1% additions compared with the multibase non-adjacent form with base {2, 3, 5}; 13.7% additions compared with the greedy algorithm with base {2, 3, 5}; 20.9% compared with the tree approach with base {2, 3}; and saves 4.1% additions compared with the add/sub algorithm with base {2, 3, 7}, which is the same algorithm with different parameters. To our knowledge, the add/sub algorithm with base {2, 3, 5} is the fastest among the existing algorithms. Also, recoding is very easy and efficient and together with the add/sub algorithm are very suitable for software implementation. In addition, we improve the greedy algorithm by plane search which searches for the best approximation with a time complexity of

$\mathcal{O}(\log^3 k)$

compared with that of the original of

$\mathcal{O}(\log^4 k)$

.