bound to a result in the range of . It follows that this extra carry word can be avoided completely if it is known in advance that . On a typical binary implementation, this is equivalent to saying that this carry word can be avoided if the number of bits of is smaller than the number of bits of . Otherwise, the carry will be either zero or one. Depending upon the processor, it may be possible to store this word as a carry flag instead of a full-sized word. It is possible to combine multiprecision multiplication and REDC into a single algorithm. This combined algorithm is usually called Montgomery multiplication. Several different implementations are described by Koç, Acar, and Kaliski. The algorithm may use as little as words of storage (plus a carry bit). As an example, let , , and . Suppose that and . The Montgomery representations of and are and . Compute . The initial input to MultiPrecisionREDC will be [6, 4, 8, 5, 6, 7]. The number will be represented as [7, 9, 9]. The extended Euclidean algorithm says that , so will be 7. i ← 0 m ← j T c - ------- - 0 0485670 2 (After first iteration of first loop) 1 0485670 2 2 0485670 2 3 0487670 0 (After first iteration of second loop) 4 0487670 0 5 0487670 0 6 0487670 0 i ← 1 m ← j T c - ------- - 0 0087670 6 (After first iteration of first loop) 1 0067670 8 2 0067670 8 3 0067470 1 (After first iteration of second loop) 4 0067480 0 5 0067480 0 i ← 2 m ← j T c - ------- - 0 0007480 2 (After first iteration of first loop) 1 0007480 2 2 0007480 2 3 0007400 1 (After first iteration of second loop) 4 0007401 0 Therefore, before the final comparison and subtraction, . The final subtraction yields the number 50. Since the Montgomery representation of is , this is the expected result. When working in base 2, determining the correct at each stage is particularly easy: If the current working bit is even, then is zero and if it's odd, then is one. Furthermore, because each step of MultiPrecisionREDC requires knowing only the lowest bit, Montgomery multiplication can be easily combined with a carry-save adder. Side-channel attacks Because Montgomery reduction avoids the