Arithmetic Operations in Finite Fields of Medium Prime Characteristic Using the Lagrange Representation

Abstract

In this paper, we propose a complete set of algorithms for the arithmetic operations in finite fields of prime medium characteristic. The elements of the fields IF <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">pk</sub> are represented using the newly defined Lagrange representation, where polynomials are expressed using their values at sufficiently many points. Our multiplication algorithm, which uses a Montgomery approach, can be implemented in O(k) multiplications and O(k <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> log k) additions in the base field IF <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> . For the inversion, we propose a variant of the extended Euclidean GCD algorithm, where the inputs are given in the Lagrange representation. The Lagrange representation scheme and the arithmetic algorithms presented in the present work represent an interesting alternative for elliptic curve cryptography