6.2 The Barrett Reduction

The Barrett reduction algorithm [6] was inspired by fast division algorithms that multiply by the reciprocal to emulate division. Barrett’s observation was that the residue c of a modulo b is equal to

(6.1)

Since algorithms such as modular exponentiation would be using the same modulus extensively, typical DSP² intuition would indicate the next step would be to replace a/b by a multiplication by the reciprocal. However, DSP intuition on its own will not work, as these numbers are considerably larger than the precision of common DSP floating point data types. It would take another common optimization to optimize the algorithm.

6.2.1 Fixed Point Arithmetic

The trick used to optimize equation 6.1 is based on a technique of emulating floating point data types with fixed precision integers. Fixed point arithmetic would become very popular, as it greatly optimized the “3D-shooter” genre of games in the mid 1990s when floating point units were fairly slow, if not unavailable. The idea behind fixed point arithmetic is to take a normal k-bit integer data type and break it into p-bit integer and a q-bit fraction part (where p+ q= k).

In this system, a k-bit integer n would actually represent n/ 2^q. For example, with q= 4 the integer n=37 would actually represent the value 2.3125. To multiply two fixed point numbers, the integers are multiplied using traditional arithmetic and subsequently normalized by moving the implied decimal point back to where it should be. For example, with q= 4, to multiply the integers 9 and 5 they must be converted to fixed point first by multiplying by 2^q. Let a= 9(2^q) represent the fixed point representation of 9, and b= 5(2^q) represent the fixed point representation of 5. The product ab is equal to 45(2^2q), which when normalized by dividing by 2^q produces 45(2^q).

This technique became popular since a normal integer multiplication and logical shift right are the only required operations to perform a multiplication of two fixed point numbers. Using fixed point arithmetic, division can be easily approximated by multiplying by the reciprocal. If 2^qis equivalent to one, then, 2^q/bis equivalent to the fixed point approximation of 1/b using real arithmetic. Using this fact, dividing an integer a by another integer b can be achieved with the following expression.

(6.2)

The precision of the division is proportional to the value of q. If the divisor b is used frequently, as is the case with modular exponentiation, pre-computing 2^q/bwill allow a division to be performed with a multiplication and a right shift. Both operations are considerably faster than division on most processors.

Consider dividing 19 by 5. The correct result is 19/5 =3. With q=3, the reciprocal is 2^q/5 = 1, which leads to a product of 19, which when divided by 2^q produces 2. However, with q= 4 the reciprocal is 2^q/5 =3 and the result of the emulated division is 3 · 19/2^q=3, which is correct. The value of 2^q must be close to or ideally larger than the dividend. In effect, if a is the dividend, then q should allow 0≤ a/2^q≤1 for this approach to work correctly. Plugging this form of division into the original equation, the following modular residue equation arises.

(6.3)

Using the notation from [6], the value of 2^q/b will be represented by the μ symbol. Using the μ variable also helps reinforce the idea that it is meant to be computed once and re-used.

(6.4)

Provided that 2^q ≥ a, this algorithm will produce a quotient that is either exactly correct or off by a value of one. In the context of Barrett reduction the value of a is bound by 0 ≤ a ≤ (b−1)², meaning that 2^q ≥ b² is sufficient to ensure the reciprocal will have enough precision.

Let n represent the number of digits in b. This algorithm requires approximately 2n² single precision multiplications to produce the quotient, and another n² single precision multiplications to find the residue. In total, 3n² single precision multiplications are required to reduce the number.

For example, if b= 1179677 and q= 41 (2^q> b²), the reciprocal μ is equal to 2^q/b = 1864089. Consider reducing a= 180388626447 modulo b using the preceding reduction equation. The quotient using the new formula is (a.μ)/2^q = 152913. By subtracting 152913b from a, the correct residue a= 677346 (mod b) is found.

6.2.2 Choosing a Radix Point

Using the fixed point representation, a modular reduction can be performed with 3n² single precision multiplications³. If that were the best that could be achieved. a full division⁴ might as well be used in its place. The key to optimizing the reduction is to reduce the precision of the initial multiplication that finds the quotient.

Let a represent the number of which the residue is sought. Let b represent the modulus used to find the residue. Let m represent the number of digits in b. For the purposes of this discussion we will assume that the number of digits in a is 2m, which is generally true if two m-digit numbers have been multiplied. Dividing a by b is the same as dividing a 2m digit integer by an m digit integer. Digits below the m−1′th digit of a will contribute at most a value of 1 to the quotient, because β^k<bfor any 0≤ k ≤ m−1. Another way to express this is by re-writing a as two parts. If a′≡ a(mod b^m)and a″=a−a′, thenwhich is equivalent toSince a′is bound to be less than b, the quotient is bound by 0≤<1.

Since the digits of a′do not contribute much to the quotient the observation is that they might as well be zero. However, if the digits “might as well be zero,” they might as well not be there in the first place. Let q₀ = a/β^m−1represent the input with the irrelevant digits trimmed. Now the modular reduction is trimmed to the almost equivalent equation

(6.5)

Note that the original divisor 2^q has been replaced with β^m+1 where in this case q is a multiple of lg(β). Also note that the exponent on the divisor when added to the amount q₀ was shifted by equals 2m. If the optimization had not been performed the divisor would have the exponent 2m, so in the end the exponents do “add up.” Using equation 6.5 the quotient(q₀ · μ)/β^m+1can be off from the true quotient by at most two. The original fixed point quotient can be off by as much as one (provided the radix point is chosen suitably), and now that the lower irrelevant digits have been trimmed the quotient can be off by an additional value of one for a total of at most two. This implies that 0≤ a− b · (q₀ · μ)/β^m+1<3b. By first subtracting b times the quotient and then conditionally subtracting b once or twice the residue is found.

The quotient is now found using (m + 1)(m) = m² + m single precision multiplications and the residue with an additional m² single precision multiplications, ignoring the subtractions required. In total, 2m² + m single precision multiplications are required to find the residue. This is considerably faster than the original attempt.

For example, let β= 10 represent the radix of the digits. Let b= 9999 represent the modulus, which implies m= 4. Let a= 99929878 represent the value of which the residue is desired; in this case, q= 8 since 10⁷<9999², meaning that μ= β^q/b= 10001. With the new observation the multiplicand for the quotient is equal to q₀ = a/β^m−1= 99929. The quotient is then(q₀ · μ)/β^m+1= 9993. Subtract 9993b from a and the correct residue a= 9871 (mod b) is found.

6.2.3 Trimming the Quotient

So far, the reduction algorithm has been optimized from 3m² single precision multiplications down to 2m²+ m single precision multiplications. As it stands now, the algorithm is already fairly fast compared to a full integer division algorithm. However, there is still room for optimization.

After the first multiplication inside the quotient (q₀ · μ) the value is shifted right by m + 1 places, effectively nullifying the lower half of the product. It would be nice to be able to remove those digits from the product to effectively cut down the number of single precision multiplications. If the number of digits in the modulus m is far less than β, a full product is not required for the algorithm to work properly. In fact, the lower m−2 digits will not affect the upper half of the product at all and do not need to be computed.

The value of μ is an m-digit number and q₀ is an m + 1 digit number. Using a full multiplier (m + 1)(m) = m² + m single precision multiplications would be required. Using a multiplier that will only produce digits at and above the m−1′th digit reduces the number of single precision multiplications to m²+m/2 single precision multiplications.

6.2.4 Trimming the Residue

After the quotient has been calculated it is used to reduce the input. As previously noted, the algorithm is not exact and can be off by a small multiple of the modulus; that is, 0≤ a− b · (q₀ · μ)/β^m+1<3b. If b is m digits, the result of reduction equation is a value of at most m + 1 digits (provided 3<β) implying that the upper m−1 digits are implicitly zero.

The next optimization arises from this very fact. Instead of computing b · (q₀ · μ)/β^m+1 using a full O(m²) multiplication algorithm, only the lower m + 1 digits of the product have to be computed. Similarly, the value of a can be reduced modulo β^m+1 before the multiple of b is subtracted, which simplifies the subtraction as well. A multiplication that produces only the lower m + 1 digits requiressingle precision multiplications.

With both optimizations in place the algorithm is the algorithm Barrett proposed. It requires m² + 2m−1 single precision multiplications, which are considerably faster than the straightforward 3m² method.

6.2.5 The Barrett Algorithm

Algorithm mp_reduce. This algorithm will reduce the input a modulo 6 in place using the Barrett algorithm. It is loosely based on algorithm 14.42 of HAC [2, pp. 602], which is based on the paper from Paul Barrett [6]. The algorithm has several restrictions and assumptions that must be adhered to for the algorithm to work (Figure 6.1).

First, the modulus b is assumed positive and greater than one. If the modulus were less than or equal to one, subtracting a multiple of it would either accomplish nothing or actually enlarge the input. The input a must be in the range 0 ≤ a< b²for the quotient to have enough precision. If a is the product of two numbers that were already reduced modulo b, this will not be a problem. Technically, the algorithm will still work if a ≥ b² but it will take much longer to finish. The value of μ is passed as an argument to this algorithm and is assumed calculated and stored before the algorithm is used.

Recall that the multiplication for the quotient in step 3 must only produce digits at or above the m−1′th position. An algorithm called s_mp_mul_high_digs that has not been presented is used to accomplish this task. The algorithm is based on s_mp_mul_digs, except that instead of stopping at a given level of precision it starts at a given level of precision. This optimal algorithm can only be used if the number of digits in b is much smaller than β.

While it is known that a ≥ b · (q₀ · μ)/β^m+1, only the lower m + 1 digits are being used to compute the residue, so an implied “borrow” from the higher digits might leave a negative result. After the multiple of the modulus has been subtracted from a, the residue must be fixed up in case it is negative. The invariant β^m+1 must be added to the residue to make it positive again.

The while loop in step 9 will subtract b until the residue is less than b. If the algorithm is performed correctly, this step is performed at most twice, and on average once. However, if a ≥ b², it will iterate substantially more times than it should.

The first multiplication that determines the quotient can be performed by only producing the digits from m−1 and up. This essentially halves the number of single precision multiplications required. However, the optimization is only safe if β is much larger than the number of digits in the modulus. In the source code, this is evaluated on lines 36 to 44 where algorithm s_mp_mul_high_digs is used when it is safe to do so.

6.2.6 The Barrett Setup Algorithm

To use algorithm mp_reduce, the value of μ must be calculated in advance. Ideally, this value should be computed once and stored for future use so the Barrett algorithm can be used without delay.

Algorithm mp_reduce_setup. This algorithm computes the reciprocal μ required for Barrett reduction. First, β^2m is calculated as 2^2.lg(β).m, which is equivalent and much faster. The final value is computed by taking the integer quotient of μ/b (Figure 6.2).

This simple routine calculates the reciprocal μrequired by Barrett reduction. Note the extended usage of algorithm mp_div where the variable that would receive the remainder is passed as NULL. As will be discussed in 8.1, the division routine allows both the quotient and the remainder to be passed as NULL, meaning to ignore the value.

6.3.1 Digit Based Montgomery Reduction

Instead of computing the reduction on a bit-by-bit basis it is much faster to compute it on digit-by-digit basis. Consider the previous algorithm re-written to compute the Montgomery reduction in this new fashion (Figure 6.7).

The value μnβ^t is a multiple of the modulus n, meaning that it will not change the residue. If the first digit of the value μnβ^tequals the negative (modulo β) of the t′th digit of x, then the addition will result in a zero digit. This problem breaks down to solving the following congruency.

In each iteration of the loop in step 1 a new value of μ must be calculated. The value of−1/n₀ (mod β) is used extensively in this algorithm and should be precomputed. Let ρ represent the negative of the modular inverse of n₀ modulo β.

For example, let β= 10 represent the radix. Let n= 17 represent the modulus, which implies k= 2 and ρ≡7. Let x= 33 represent the value to reduce.

The result in Figure 6.8 of 900 is then divided by β^kto produce the result 9. The first observation is that 9 x (mod n), which implies the result is not the modular residue of x modulo n. However, recall that the residue is actually multiplied by β^−kin the algorithm. To get the true residue the value must be multiplied by β^k. In this case, β^k≡15 (mod n) and the correct residue is 9 · 15 = 16 (mod n).

6.3.2 Baseline Montgomery Reduction

The baseline Montgomery reduction algorithm will produce the residue for any size input. It is designed to be a catch-all algorithm for Montgomery reductions.

Algorithm mp_montgomery_reduce. This algorithm reduces the input x modulo n in place using the Montgomery reduction algorithm. The algorithm is loosely based on algorithm 14.32 of [2, pp.601], except it merges the multiplication of μnβ^t with the addition in the inner loop. The restrictions on this algorithm are fairly easy to adapt to. First, 0 ≤ x< n² bounds the input to numbers in the same range as for the Barrett algorithm. Additionally, if n>1 and n is odd there will exist a modular inverse ρ. ρ must be calculated in advance of this algorithm. Finally, the variable k is fixed and a pseudonym for n.used(Figure 6.9).

Step 2 decides whether a faster Montgomery algorithm can be used. It is based on the Comba technique, meaning that there are limits on the size of the input. This algorithm is discussed in 7.9.

Step 5 is the main reduction loop of the algorithm. The value of μ is calculated once per iteration in the outer loop. The inner loop calculates x + μnβ^ixby multiplying μn and adding the result to x shifted by ix digits. Both the addition and multiplication are performed in the same loop to save time and memory. Step 5.4 will handle any additional carries that escape the inner loop.

On quick inspection, this algorithm requires n single precision multiplications for the outer loop and n² single precision multiplications in the inner loop for a total n² + n single precision multiplications, which compares favorably to Barrett at n² + 2n−1 single precision multiplications.

This is the baseline implementation of the Montgomery reduction algorithm. Lines 31 to 36 determine if the Comba–based routine can be used instead. Line 47 computes the value of μ for that particular iteration of the outer loop.

The multiplication μnβ^ixis performed in one step in the inner loop. The alias tmpx refers to the ix′th digit of x, and the alias tmpn refers to the modulus n.

6.3.3 Faster “Comba” Montgomery Reduction

The Montgomery reduction requires fewer single precision multiplications than a Barrett reduction; however, it is much slower due to the serial nature of the inner loop. The Barrett reduction algorithm requires two slightly modified multipliers, which can be implemented with the Comba technique. The Montgomery reduction algorithm cannot directly use the Comba technique to any significant advantage since the inner loop calculates a k×1 product k times.

The biggest obstacle is that at the ix′th iteration of the outer loop, the value of x_ix is required to calculate μ. This means the carries from 0 to ix−1 must have been propagated upwards to form a valid ix′th digit. The solution as it turns out is very simple. Perform a Comba–like multiplier, and inside the outer loop just after the inner loop, fix up the ix + 1′th digit by forwarding the carry.

With this change in place, the Montgomery reduction algorithm can be performed with a Comba–style multiplication loop, which substantially increases the speed of the algorithm.

Algorithm fast_mp_montgomery_reduce. This algorithm will compute the Montgomery reduction of x modulo n using the Comba technique. It is on most computer platforms significantly faster than algorithm mp_montgomery_reduce and algorithm mp_reduce (Barrett reduction). The algorithm has the same restrictions on the input as the baseline reduction algorithm. An additional two restrictions are imposed on this algorithm. The number of digits k in the modulus n must not violate MP_W ARRAY > 2k+1 and n<δ. When β= 2²⁸, this algorithm can be used to reduce modulo a modulus of at most 3, 556 bits in length (Figure 6.10).

As in the other Comba reduction algorithms there is a Ŵ array that stores the columns of the product. It is initially filled with the contents of x with the excess digits zeroed. The reduction loop is very similar the to the baseline loop at heart. The multiplication in step 4.1 can be single precision only, since ab(mod β) = (a mod β) (b mod β). Some multipliers such as those on the ARM processors take a variable length time to complete depending on the number of bytes of result it must produce. By performing a single precision multiplication instead, half the amount of time is spent.

Also note that digit Ŵ_ix must have the carry from the ix−1′th digit propagated upwards for this to work. That is what step 4.3 will do. In effect, over the n.used iterations of the outer loop the n.used′th lower columns all have their carries propagated forwards. Note how the upper bits of those same words are not reduced modulo β. This is because those values will be discarded shortly and there is no point.

Step 5 will propagate the remainder of the carries upwards. In step 6, the columns are reduced modulo β and shifted simultaneously as they are stored in the destination x.

The Ŵ array is first filled with digits of x on Line 55, then the rest of the digits are zeroed on Line 60. Both loops share the same alias variables to make the code easier to read.

The value of μ is calculated in an interesting fashion. First, the value Ŵ_ixis reduced modulo β and cast to a mp_digit. This forces the compiler to use a single precision multiplication and prevents any concerns about loss of precision. Line 110 fixes the carry for the next iteration of the loop by propagating the carry from Ŵ_ixto Ŵ_ix+1.

The for loop on Line 129 propagates the rest of the carries upwards through the columns. The for loop on Line 146 reduces the columns modulo β and shifts them k places at the same time. The alias _Ŵactually refers to the array Ŵ starting at the n.used′th digit, that is _Ŵ_t=Ŵ_n.used+t.

6.3.4 Montgomery Setup

To calculate the variable ρ, a relatively simple algorithm will be required.

Algorithm mp_montgomery_setup. This algorithm will calculate the value of ρ required within the Montgomery reduction algorithms. It uses a very interesting trick to calculate 1/n₀ when βis a power of two (Figure 6.11).

This source code computes the value of ρ required to perform Montgomery reduction. It has been modified to avoid performing excess multiplications when β is not the default 28 bits.

6.4.1 Choice of Moduli

On the surface, this algorithm looks very expensive. It requires a couple of subtractions followed by multiplication and other modular reductions. The usefulness of this algorithm becomes exceedingly clear when an appropriate modulus is chosen.

Division in general is a very expensive operation to perform. The one exception is when the division is by a power of the radix of representation used. Division by 10, for example, is simple for pencil and paper mathematics since it amounts to shifting the decimal place to the right. Similarly, division by 2 (or powers of 2) is very simple for binary computers to perform. It would therefore seem logical to choose n of the form 2^p, which would imply that x/n is a simple shift of x right p bits.

However, there is one operation related to division of power of twos that is even faster. If n= β^p, then the division may be performed by moving whole digits to the right p places. In practice, division by β^pis much faster than division by 2^pfor any p. Also, with the choice of n= β^preducing x modulo n merely requires zeroing the digits above the p−1′th digit of x.

Throughout the next section the term restricted modulus will refer to a modulus of the form β^p−k, whereas the term unrestricted modulus will refer to a modulus of the form 2^p− k. The word restricted in this case refers to the fact that it is based on the 2^p logic, except p must be a multiple of lg(β).

6.4.2 Choice of k

Now that division and reduction (steps 1 and 3 of Figure 6.12)have been optimized to simple digit operations, the multiplication by k in step 2 is the most expensive operation. Fortunately, the choice of kis not terribly limited. For all intents and purposes it might as well be a single digit. The smaller the value of k, the faster the algorithm will be.

6.4.3 Restricted Diminished Radix Reduction

The Restricted Diminished Radix algorithm can quickly reduce an input modulo a modulus of the form n= β^p− k. This algorithm can reduce an input x within the range 0 ≤ x< n² using only a couple of passes of the algorithm demonstrated in Figure 6.12. The implementation of this algorithm has been optimized to avoid additional overhead associated with a division by β^p, the multiplication by k or the addition of x and q. The resulting algorithm is very efficient and can lead to substantial improvements over Barrett and Montgomery reduction when modular exponentiations are performed.

Algorithm mp_dr_reduce. This algorithm will perform the Diminished Radix reduction of x modulo n. It has similar restrictions to that of the Barrett reduction with the addition that n must be of the form n= β^m− k where 0< k<β (Figure 6.14).

This algorithm essentially implements the pseudo-code in Figure 6.12, except with a slight optimization. The division by β^m, multiplication by k, and addition of x mod β^m are all performed simultaneously inside the loop in step 4. The division by β^m is emulated by accessing the term at the m + i′th position, which is subsequently multiplied by k and added to the term at the i′th position. After the loop the m′th digit is set to the carry and the upper digits are zeroed. Steps 5 and 6 emulate the reduction modulo β^m that should have happened to x before the addition of the multiple of the upper half.

In step 8, if x is still larger than n, another pass of the algorithm is required. First, n is subtracted from x and then the algorithm resumes at step 3.

The first step is to grow x as required to 2m digits, since the reduction is performed in place on x. The label on Line 52 is where the algorithm will resume if further reduction passes are required. In theory, it could be placed at the top of the function. However, the size of the modulus and question of whether x is large enough are invariant after the first pass, meaning that it would be a waste of time.

The aliases tmpx 1 and tmpx 2 refer to the digits of x, where the latter is offset by m digits. By reading digits from x offset by m digits, a division by β^m can be simulated virtually for free. The loop on Line 64 performs the bulk of the work (corresponds to step 4 of algorithm 7.11) in this algorithm.

By Line 67 the pointer tmpx 1 points to the m′th digit of x, which is where the final carry will be placed. Similarly, by Line 74 the same pointer will point to the m + 1′th digit where the zeroes will be placed.

Since the algorithm is only valid if both x and n are greater than zero, an unsigned comparison suffices to determine if another pass is required. With the same logic at Line 81 the value of x is known to be greater than or equal to n, meaning that an unsigned subtraction can be used as well. Since the destination of the subtraction is the larger of the inputs, the call to algorithm s_mp_sub cannot fail and the return code does not need to be checked.

6.4.4 Unrestricted Diminished Radix Reduction

The unrestricted Diminished Radix algorithm allows modular reductions to be performed when the modulus is of the form 2^p−k. This algorithm is a straightforward adaptation of algorithm 6.12.

In general, the restricted Diminished Radix reduction algorithm is much faster since it has considerably lower overhead. However, this new algorithm is much faster than either Montgomery or Barrett reduction when the moduli are of the appropriate form.

Algorithm mp_reduce_2k. This algorithm quickly reduces an input a modulo an unrestricted Diminished Radix modulus n. Division by 2^pis emulated with a right shift, which makes the algorithm fairly inexpensive to use (Figure 6.17).

The algorithm mp_count_bits calculates the number of bits in an mp_int, which is used to find the initial value of p. The call to mp_div_2d on Line 31 calculates both the quotient q and the remainder a required. By doing both in a single function call, the code size is kept fairly small. The multiplication by k is only performed if k>1. This allows reductions modulo 2^p −1 to be performed without any multiplications.

The unsigned s_mp_add, mp_cmp_mag, and s_mp_sub are used in place of their full sign counterparts since the inputs are only valid if they are positive. By using the unsigned versions, the overhead is kept to a minimum.

3. Prove that the “trick” in algorithm mp_montgomery_setup actually calculates the correct value of ρ.

2. Devise an algorithm to reduce modulo n + k for small k quickly.

4. Prove that the pseudo-code algorithm “Diminished Radix Reduction” (Figure 6.12)terminates. Also prove the probability that it will terminate within 1 ≤ k ≤ 10 iterations.