1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/doc/square.txt Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,72 @@
1.4 +Squaring Algorithm
1.5 +
1.6 +When you are squaring a value, you can take advantage of the fact that
1.7 +half the multiplications performed by the more general multiplication
1.8 +algorithm (see 'mul.txt' for a description) are redundant when the
1.9 +multiplicand equals the multiplier.
1.10 +
1.11 +In particular, the modified algorithm is:
1.12 +
1.13 +k = 0
1.14 +for j <- 0 to (#a - 1)
1.15 + w = c[2*j] + (a[j] ^ 2);
1.16 + k = w div R
1.17 +
1.18 + for i <- j+1 to (#a - 1)
1.19 + w = (2 * a[j] * a[i]) + k + c[i+j]
1.20 + c[i+j] = w mod R
1.21 + k = w div R
1.22 + endfor
1.23 + c[i+j] = k;
1.24 + k = 0;
1.25 +endfor
1.26 +
1.27 +On the surface, this looks identical to the multiplication algorithm;
1.28 +however, note the following differences:
1.29 +
1.30 + - precomputation of the leading term in the outer loop
1.31 +
1.32 + - i runs from j+1 instead of from zero
1.33 +
1.34 + - doubling of a[i] * a[j] in the inner product
1.35 +
1.36 +Unfortunately, the construction of the inner product is such that we
1.37 +need more than two digits to represent the inner product, in some
1.38 +cases. In a C implementation, this means that some gymnastics must be
1.39 +performed in order to handle overflow, for which C has no direct
1.40 +abstraction. We do this by observing the following:
1.41 +
1.42 +If we have multiplied a[i] and a[j], and the product is more than half
1.43 +the maximum value expressible in two digits, then doubling this result
1.44 +will overflow into a third digit. If this occurs, we take note of the
1.45 +overflow, and double it anyway -- C integer arithmetic ignores
1.46 +overflow, so the two digits we get back should still be valid, modulo
1.47 +the overflow.
1.48 +
1.49 +Having doubled this value, we now have to add in the remainders and
1.50 +the digits already computed by earlier steps. If we did not overflow
1.51 +in the previous step, we might still cause an overflow here. That
1.52 +will happen whenever the maximum value expressible in two digits, less
1.53 +the amount we have to add, is greater than the result of the previous
1.54 +step. Thus, the overflow computation is:
1.55 +
1.56 +
1.57 + u = 0
1.58 + w = a[i] * a[j]
1.59 +
1.60 + if(w > (R - 1)/ 2)
1.61 + u = 1;
1.62 +
1.63 + w = w * 2
1.64 + v = c[i + j] + k
1.65 +
1.66 + if(u == 0 && (R - 1 - v) < w)
1.67 + u = 1
1.68 +
1.69 +If there is an overflow, u will be 1, otherwise u will be 0. The rest
1.70 +of the parameters are the same as they are in the above description.
1.71 +
1.72 +------------------------------------------------------------------
1.73 + This Source Code Form is subject to the terms of the Mozilla Public
1.74 + # License, v. 2.0. If a copy of the MPL was not distributed with this
1.75 + # file, You can obtain one at http://mozilla.org/MPL/2.0/.
