Finite field operations are used as computation primitives for executing numerous cryptographic algorithms, especially those related with the use of public keys (asymmetric cryptography). Classical examples are ciphering deciphering, authentication, and digital signature protocols based on RSA-type or elliptic curve algorithms. Other classical applications of finite fields are error correcting codes and residue number systems. This chapter proposes algorithms allowing the execution of the main arithmetic operations (addition, subtraction, multiplication) in finite rings Zm and polynomial rings Zp[x]/f(x). In the case of Zm, an exponentiation algorithm based on the Montgomery multiplication concept is also described. If p is prime and f(x) is an irreducible polynomial, then Zp, Zp[x]/f(x), GF(p), and GF(pn) are finite fields for which inversion algorithms are proposed.

Get Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.