Acceleration of finite field arithmetic with an application to reverse engineering genetic networks

Abstract

Finite field arithmetic plays an important role in a wide range of applications. This research is originally motivated by an application of computational biology where genetic networks are modeled by means of finite fields. Nonetheless, this work has application in various research fields including digital signal processing, error correcting codes, Reed-Solomon encoders/decoders, elliptic curve cryptosystems, or computational and algorithmic aspects of commutative algebra. We present a set of efficient algorithms for finite field arithmetic over GF(2m), which are implemented on a High Performance Reconfigurable Computing platform. In this way, we deliver new and efficient designs on Field Programmable Gate Arrays (FPGA) for accelerating finite field arithmetic. Among the arithmetic operations, the most frequently used and time consuming operation is multiplication. We have designed a fast and space-saving multiplier, which has been used for creating other efficient architectures for inversion and exponentiation which have in turn been used for developing a new and efficient architecture for finite field interpolation. Here, the bit-level representation of the elements in GF(2m) and some special structures in the formulation of multiplication and inversion algorithms, have been exploited in order to use efficiently the FPGAs resources. Furthermore, we have also proposed a novel approach for multiplication over finite fields GF(pm), with p 6= 2, where the com putational complexity is reduced from O(n2) to O(n log n).