Modular arithmetic and the FFT
Richard P. Brent, Paul A. Zimmermann · Cambridge University Press eBooks · 2010
In this chapter our main topic is modular arithmetic, i.e. how to compute efficiently modulo a given integer N . In most applications, the modulus N is fixed, and special-purpose algorithms benefit from some precomputations, depending only on N , to speed up arithmetic modulo N . There is an overlap between Chapter 1 and this chapter. For example, integer division and modular multiplication are closely related. In Chapter 1 we present algorithms where no (or only a few) precomputations with respect to the modulus N are performed. In this chapter, we consider algorithms which benefit from such precomputations. Unless explicitly stated, we consider that the modulus N occupies n words in the word-base β, i.e. β n −1 ≤ N < β n . Representation We consider in this section the different possible representations of residues modulo N . As in Chapter 1, we consider mainly dense representations. Classical representation The classical representation stores a residue (class) a as an integer 0 ≤ a < N . Residues are thus always fully reduced, i.e. in canonical form. Another non-redundant form consists in choosing a symmetric representation, say − N /2 ≤ a < N /2. This form might save some reductions in additions or subtractions (see §2.2). Negative numbers might be stored either with a separate sign (sign-magnitude representation) or with a two's-complement representation. Since N takes n words in base β, an alternative redundant representation chooses 0 ≤ a < β n to represent a residue class.