redux.txt (3146B)
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/.