The Tor Browser / file comparison
comparison: security/nss/lib/freebl/mpi/doc/redux.txt
security/nss/lib/freebl/mpi/doc/redux.txt
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:ccede1da6454 |
|---|---|
| 1 Modular Reduction | |
| 2 | |
| 3 Usually, modular reduction is accomplished by long division, using the | |
| 4 mp_div() or mp_mod() functions. However, when performing modular | |
| 5 exponentiation, you spend a lot of time reducing by the same modulus | |
| 6 again and again. For this purpose, doing a full division for each | |
| 7 multiplication is quite inefficient. | |
| 8 | |
| 9 For this reason, the mp_exptmod() function does not perform modular | |
| 10 reductions in the usual way, but instead takes advantage of an | |
| 11 algorithm due to Barrett, as described by Menezes, Oorschot and | |
| 12 VanStone in their book _Handbook of Applied Cryptography_, published | |
| 13 by the CRC Press (see Chapter 14 for details). This method reduces | |
| 14 most of the computation of reduction to efficient shifting and masking | |
| 15 operations, and avoids the multiple-precision division entirely. | |
| 16 | |
| 17 Here is a brief synopsis of Barrett reduction, as it is implemented in | |
| 18 this library. | |
| 19 | |
| 20 Let b denote the radix of the computation (one more than the maximum | |
| 21 value that can be denoted by an mp_digit). Let m be the modulus, and | |
| 22 let k be the number of significant digits of m. Let x be the value to | |
| 23 be reduced modulo m. By the Division Theorem, there exist unique | |
| 24 integers Q and R such that: | |
| 25 | |
| 26 x = Qm + R, 0 <= R < m | |
| 27 | |
| 28 Barrett reduction takes advantage of the fact that you can easily | |
| 29 approximate Q to within two, given a value M such that: | |
| 30 | |
| 31 2k | |
| 32 b | |
| 33 M = floor( ----- ) | |
| 34 m | |
| 35 | |
| 36 Computation of M requires a full-precision division step, so if you | |
| 37 are only doing a single reduction by m, you gain no advantage. | |
| 38 However, when multiple reductions by the same m are required, this | |
| 39 division need only be done once, beforehand. Using this, we can use | |
| 40 the following equation to compute Q', an approximation of Q: | |
| 41 | |
| 42 x | |
| 43 floor( ------ ) M | |
| 44 k-1 | |
| 45 b | |
| 46 Q' = floor( ----------------- ) | |
| 47 k+1 | |
| 48 b | |
| 49 | |
| 50 The divisions by b^(k-1) and b^(k+1) and the floor() functions can be | |
| 51 efficiently implemented with shifts and masks, leaving only a single | |
| 52 multiplication to be performed to get this approximation. It can be | |
| 53 shown that Q - 2 <= Q' <= Q, so in the worst case, we can get out with | |
| 54 two additional subtractions to bring the value into line with the | |
| 55 actual value of Q. | |
| 56 | |
| 57 Once we've got Q', we basically multiply that by m and subtract from | |
| 58 x, yielding: | |
| 59 | |
| 60 x - Q'm = Qm + R - Q'm | |
| 61 | |
| 62 Since we know the constraint on Q', this is one of: | |
| 63 | |
| 64 R | |
| 65 m + R | |
| 66 2m + R | |
| 67 | |
| 68 Since R < m by the Division Theorem, we can simply subtract off m | |
| 69 until we get a value in the correct range, which will happen with no | |
| 70 more than 2 subtractions: | |
| 71 | |
| 72 v = x - Q'm | |
| 73 | |
| 74 while(v >= m) | |
| 75 v = v - m | |
| 76 endwhile | |
| 77 | |
| 78 | |
| 79 In random performance trials, modular exponentiation using this method | |
| 80 of reduction gave around a 40% speedup over using the division for | |
| 81 reduction. | |
| 82 | |
| 83 ------------------------------------------------------------------ | |
| 84 This Source Code Form is subject to the terms of the Mozilla Public | |
| 85 # License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 86 # file, You can obtain one at http://mozilla.org/MPL/2.0/. |
