Fast Inversions in Small Finite Fields by Using Binary Trees
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 「log2p」(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 pipefined 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%.
inversion finite field binary tree pipelining hardware implementation Application Specific Integrated Circuit (ASIC) Field Programmable Logic Array (FPGA)
HAIBO YI SHAOHUA TANG RANGA VEMURI
School of Computer Science and Engineering, South China University of Technology,Guangzhou 510006, C Department of Electrical and Computer Engineering, University of Cincinnati, Cincinnati, OH 45219, U
国内会议
桂林
英文
43-53
2017-05-01（万方平台首次上网日期，不代表论文的发表时间）