The Tor Browser / file comparison
comparison: security/nss/lib/freebl/mpi/doc/square.txt
security/nss/lib/freebl/mpi/doc/square.txt
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
equal
deleted
inserted
replaced
| -1:000000000000 | 0:0e9841541505 |
|---|---|
| 1 Squaring Algorithm | |
| 2 | |
| 3 When you are squaring a value, you can take advantage of the fact that | |
| 4 half the multiplications performed by the more general multiplication | |
| 5 algorithm (see 'mul.txt' for a description) are redundant when the | |
| 6 multiplicand equals the multiplier. | |
| 7 | |
| 8 In particular, the modified algorithm is: | |
| 9 | |
| 10 k = 0 | |
| 11 for j <- 0 to (#a - 1) | |
| 12 w = c[2*j] + (a[j] ^ 2); | |
| 13 k = w div R | |
| 14 | |
| 15 for i <- j+1 to (#a - 1) | |
| 16 w = (2 * a[j] * a[i]) + k + c[i+j] | |
| 17 c[i+j] = w mod R | |
| 18 k = w div R | |
| 19 endfor | |
| 20 c[i+j] = k; | |
| 21 k = 0; | |
| 22 endfor | |
| 23 | |
| 24 On the surface, this looks identical to the multiplication algorithm; | |
| 25 however, note the following differences: | |
| 26 | |
| 27 - precomputation of the leading term in the outer loop | |
| 28 | |
| 29 - i runs from j+1 instead of from zero | |
| 30 | |
| 31 - doubling of a[i] * a[j] in the inner product | |
| 32 | |
| 33 Unfortunately, the construction of the inner product is such that we | |
| 34 need more than two digits to represent the inner product, in some | |
| 35 cases. In a C implementation, this means that some gymnastics must be | |
| 36 performed in order to handle overflow, for which C has no direct | |
| 37 abstraction. We do this by observing the following: | |
| 38 | |
| 39 If we have multiplied a[i] and a[j], and the product is more than half | |
| 40 the maximum value expressible in two digits, then doubling this result | |
| 41 will overflow into a third digit. If this occurs, we take note of the | |
| 42 overflow, and double it anyway -- C integer arithmetic ignores | |
| 43 overflow, so the two digits we get back should still be valid, modulo | |
| 44 the overflow. | |
| 45 | |
| 46 Having doubled this value, we now have to add in the remainders and | |
| 47 the digits already computed by earlier steps. If we did not overflow | |
| 48 in the previous step, we might still cause an overflow here. That | |
| 49 will happen whenever the maximum value expressible in two digits, less | |
| 50 the amount we have to add, is greater than the result of the previous | |
| 51 step. Thus, the overflow computation is: | |
| 52 | |
| 53 | |
| 54 u = 0 | |
| 55 w = a[i] * a[j] | |
| 56 | |
| 57 if(w > (R - 1)/ 2) | |
| 58 u = 1; | |
| 59 | |
| 60 w = w * 2 | |
| 61 v = c[i + j] + k | |
| 62 | |
| 63 if(u == 0 && (R - 1 - v) < w) | |
| 64 u = 1 | |
| 65 | |
| 66 If there is an overflow, u will be 1, otherwise u will be 0. The rest | |
| 67 of the parameters are the same as they are in the above description. | |
| 68 | |
| 69 ------------------------------------------------------------------ | |
| 70 This Source Code Form is subject to the terms of the Mozilla Public | |
| 71 # License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 72 # file, You can obtain one at http://mozilla.org/MPL/2.0/. |
