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

摘要

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 {hbox{rlap{I}kern 2.0 pt{hbox{F}}}}_{p^k} 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^2 log k) additions in the base field {hbox{rlap{I}kern 2.0 pt{hbox{F}}}}_p. 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.