New Methods for Finite Field ArithmeticT. YanikPh.D. Thesis, Department of Electrical & Computer Engineering, Oregon State University, November 21, 2001AbstractWe describe novel methods for obtaining fast software implementations of the arithmetic operations in the finite field GF(p) and GF(p^k). In GF(p) we realize an extensive speedup in modular addition and subtraction routines and some small speedup in the modular multiplication routine with an arbitrary prime modulus p which is of arbitrary length. The most important feature of the method is that it avoids bit-level operations which are slow on microprocessors and performs word-level operations which are significantly faster. The proposed method has applications in public-key cryptographic algorithms defined over the finite field GF(p), most notably the elliptic curve digital signature algorithm. The new method provides up to 13 % speedup in the execution of the ECDSA algorithm over the field GF(p) for the length of p in the range 161 <= k <= 256.In the finite extension field GF(p^k) we describe two new methods for obtaining fast software implementations of the modular multiplication operation with an arbitrary prime modulus p, which has less bit-length than the word-length of a microprocessor and an arbitrary generator polynomial. The second algorithm is a significant improvement over the first algorithm by using the same concepts introduced in GF(p) arithmetic. |