Performance evaluation of highly efficient techniques for software implementation of LFSR

Linear feedback shift registers (LFSR) are widely used in many different areas. In this paper, we study the operation of LFSR defined over extension fields GF(2n)GF(2n), instead of traditional binary fields, quantifying and comparing the theoretical with the real performance improvement. We also examine other techniques for efficient implementation, analyzing the effectiveness of both approaches. The experiments show that speedups up to 10.15 can be easily achieved. Surprisingly, data also show that the use of extension fields greater than GF(216)GF(216) is not always worth, due to the increasing internal operation costs. The benefits are clear for all possible applications of LFSR, and specifically for cryptographic purposes.