Fast Inversions in Small Finite Fields by Using Binary Trees
Haibo Yi, Shaohua Tang, Ranga R. Vemuri · The Computer Journal · 2016
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(2^n)$| and |$GF(p)$| , where |$n$| is a positive integer and |$p$| is a prime number. The non-pipelined versions of our design in |$GF(2^n)$| and |$GF(p)$| have the execution time of |$(n-1)(T_{AND}+T_{XOR})$| and |$\lfloor \log _2p\rfloor (T_{AND}+T_{XOR})$| , where |$T_{AND}$| and |${T_{XOR}}$| are delays of AND and XOR gates, respectively. The pipelined version of our design has a throughput rate of one result per |$T_{AND}$| (or |$T_{XOR}$| ). The latency is the greater value between |$T_{AND}$| and |$T_{XOR}$| . In other words, the time complexities of non-pipelined and pipelined versions are |$O(n)$| (or |$O(log_2p)$| ) 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(2^{12})$| is reduced by 73 |$\%$| and time–area product of inversion in |$GF(2^6)$| is reduced by 77 |$\%$| .