A Generalization of Addition Chains and Fast Inversions in Binary Fields

摘要

In this paper, we study a generalization of addition chains where previous values are summed together on each step instead of only two values as in traditional addition chains. Such chains are called -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.