Incomplete reduction in modular arithmetic

Abstract

The authors describe a novel method for obtaining fast software implementations of the arithmetic operations in the finite field GF( p) with an arbitrary prime modulus p 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.