A Generalization of Addition Chains and Fast Inversions in Binary Fields
Kimmo U. Jarvinen, Vassil S. Dimitrov, Reza Azarderakhsh · IEEE Transactions on Computers · 2014
In this paper, we study a generalization of addition chains where$k$previous values are summed together on each step instead of only two values as in traditional addition chains. Such chains are called$k$-chains and we show that they have applications in finding efficient parallelizations in problems that are known to be difficult to parallelize. In particular, 3-chains improve computations of inversions in finite fields using hybrid-double multipliers. Recently, it was shown that this operation can be efficiently computed using a ternary algorithm but we show that 3-chains provide a significantly more efficient solution.