Abstract. The intrinsic structure of binary fields poses a challenging complexity problem from both hardware and software point of view. Motivated by applications to modern cryptography, we describe some simple techniques aimed at performing computations over binary fields using systems with limited resources. This is particularly important when such computations must be carried out by means of very small and simple machines. The algorithms described in the present paper provide an increased efficiency in computations, when compared to the previously known algorithms for the arithmetic over prime fields.

DOI: 10.14232/actasm-012-813-7

AMS Subject Classification (1991): 14G50, 11T55

Keyword(s): binary field, cryptography, limited system

Received August 27, 2012, and in revised form January 10, 2013. (Registered under 63/2012.)