1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/doc/redux.txt Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,86 @@
1.4 +Modular Reduction
1.5 +
1.6 +Usually, modular reduction is accomplished by long division, using the
1.7 +mp_div() or mp_mod() functions. However, when performing modular
1.8 +exponentiation, you spend a lot of time reducing by the same modulus
1.9 +again and again. For this purpose, doing a full division for each
1.10 +multiplication is quite inefficient.
1.11 +
1.12 +For this reason, the mp_exptmod() function does not perform modular
1.13 +reductions in the usual way, but instead takes advantage of an
1.14 +algorithm due to Barrett, as described by Menezes, Oorschot and
1.15 +VanStone in their book _Handbook of Applied Cryptography_, published
1.16 +by the CRC Press (see Chapter 14 for details). This method reduces
1.17 +most of the computation of reduction to efficient shifting and masking
1.18 +operations, and avoids the multiple-precision division entirely.
1.19 +
1.20 +Here is a brief synopsis of Barrett reduction, as it is implemented in
1.21 +this library.
1.22 +
1.23 +Let b denote the radix of the computation (one more than the maximum
1.24 +value that can be denoted by an mp_digit). Let m be the modulus, and
1.25 +let k be the number of significant digits of m. Let x be the value to
1.26 +be reduced modulo m. By the Division Theorem, there exist unique
1.27 +integers Q and R such that:
1.28 +
1.29 + x = Qm + R, 0 <= R < m
1.30 +
1.31 +Barrett reduction takes advantage of the fact that you can easily
1.32 +approximate Q to within two, given a value M such that:
1.33 +
1.34 + 2k
1.35 + b
1.36 + M = floor( ----- )
1.37 + m
1.38 +
1.39 +Computation of M requires a full-precision division step, so if you
1.40 +are only doing a single reduction by m, you gain no advantage.
1.41 +However, when multiple reductions by the same m are required, this
1.42 +division need only be done once, beforehand. Using this, we can use
1.43 +the following equation to compute Q', an approximation of Q:
1.44 +
1.45 + x
1.46 + floor( ------ ) M
1.47 + k-1
1.48 + b
1.49 +Q' = floor( ----------------- )
1.50 + k+1
1.51 + b
1.52 +
1.53 +The divisions by b^(k-1) and b^(k+1) and the floor() functions can be
1.54 +efficiently implemented with shifts and masks, leaving only a single
1.55 +multiplication to be performed to get this approximation. It can be
1.56 +shown that Q - 2 <= Q' <= Q, so in the worst case, we can get out with
1.57 +two additional subtractions to bring the value into line with the
1.58 +actual value of Q.
1.59 +
1.60 +Once we've got Q', we basically multiply that by m and subtract from
1.61 +x, yielding:
1.62 +
1.63 + x - Q'm = Qm + R - Q'm
1.64 +
1.65 +Since we know the constraint on Q', this is one of:
1.66 +
1.67 + R
1.68 + m + R
1.69 + 2m + R
1.70 +
1.71 +Since R < m by the Division Theorem, we can simply subtract off m
1.72 +until we get a value in the correct range, which will happen with no
1.73 +more than 2 subtractions:
1.74 +
1.75 + v = x - Q'm
1.76 +
1.77 + while(v >= m)
1.78 + v = v - m
1.79 + endwhile
1.80 +
1.81 +
1.82 +In random performance trials, modular exponentiation using this method
1.83 +of reduction gave around a 40% speedup over using the division for
1.84 +reduction.
1.85 +
1.86 +------------------------------------------------------------------
1.87 + This Source Code Form is subject to the terms of the Mozilla Public
1.88 + # License, v. 2.0. If a copy of the MPL was not distributed with this
1.89 + # file, You can obtain one at http://mozilla.org/MPL/2.0/.
