A Generalization of Addition Chains and Fast Inversions in Binary Fields

作者：Jarvinen Kimmo^*; Dimitrov Vassil; Azarderakhsh Reza

来源：IEEE Transactions on Computers, 2015, 64(9): 2421-2432.

DOI：10.1109/TC.2014.2375182

• Addition chain
• finite field
• binary extension field
• normal basis
• hybrid-double multiplier
• inversion
• exponentiation
• pseudo-random number generation
• cryptography
• codes
• ASIC

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

• 出版日期2015-9