Fast Inversions in Small Finite Fields by Using Binary Trees

作者：Yi, Haibo; Tang, Shaohua^*; Vemuri, Ranga

来源：Computer Journal, 2016, 59(7): 1102-1112.

DOI：10.1093/comjnl/bxw009

• inversion
• finite field
• binary tree
• pipelining
• hardware implementation
• Application Specific Integrated Circuit (ASIC)
• Field Programmable Logic Array (FPGA)

Inversions in small finite fields are playing a key role in many areas. We present techniques to exploit binary trees for fast inversions in GF(2n) and GF(p), where n is a positive integer and p is a prime number. The non-pipelined versions of our design in GF(2n) and GF(p) have the execution time of (n -1)(TAND + TXOR) and [log2 p] (TAND + TXOR), where TAND and TXOR are delays of AND and XOR gates, respectively. The pipelined version of our design has a throughput rate of one result per TAND (or TXOR). The latency is the greater value between TAND and TXOR. In other words, the time complexities of non-pipelined and pipelined versions are O(n)(or O(log2p)) and O(1), respectively. Experimental results and comparisons show that our design provides significant reductions in both the execution time and time-area product, e. g. the execution time of inversion in GF(212) is reduced by 73% and time-area product of inversion in GF(26) is reduced by 77%.

• 出版日期2016-7
• 单位华南理工大学