New Greedy Algorithm for Computing Double-Base Chains

We improve the greedy algorithm which converts integers into double-base chains by introducing tree structure. The new method accelerates the convergence of greedy algorithm, which makes the double-base expansions shorter than before. And it reduces the cost of computing scalar multiplication on elliptic curves. Furthermore, new algorithm performs well in flexibility. We could adjust it to return more efficient expansions for scalar multiplication on special curves. We also discuss the impact of parameters on the performance of new method.