1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/doc/mul.txt Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,77 @@
1.4 +Multiplication
1.5 +
1.6 +This describes the multiplication algorithm used by the MPI library.
1.7 +
1.8 +This is basically a standard "schoolbook" algorithm. It is slow --
1.9 +O(mn) for m = #a, n = #b -- but easy to implement and verify.
1.10 +Basically, we run two nested loops, as illustrated here (R is the
1.11 +radix):
1.12 +
1.13 +k = 0
1.14 +for j <- 0 to (#b - 1)
1.15 + for i <- 0 to (#a - 1)
1.16 + w = (a[j] * b[i]) + k + c[i+j]
1.17 + c[i+j] = w mod R
1.18 + k = w div R
1.19 + endfor
1.20 + c[i+j] = k;
1.21 + k = 0;
1.22 +endfor
1.23 +
1.24 +It is necessary that 'w' have room for at least two radix R digits.
1.25 +The product of any two digits in radix R is at most:
1.26 +
1.27 + (R - 1)(R - 1) = R^2 - 2R + 1
1.28 +
1.29 +Since a two-digit radix-R number can hold R^2 - 1 distinct values,
1.30 +this insures that the product will fit into the two-digit register.
1.31 +
1.32 +To insure that two digits is enough for w, we must also show that
1.33 +there is room for the carry-in from the previous multiplication, and
1.34 +the current value of the product digit that is being recomputed.
1.35 +Assuming each of these may be as big as R - 1 (and no larger,
1.36 +certainly), two digits will be enough if and only if:
1.37 +
1.38 + (R^2 - 2R + 1) + 2(R - 1) <= R^2 - 1
1.39 +
1.40 +Solving this equation shows that, indeed, this is the case:
1.41 +
1.42 + R^2 - 2R + 1 + 2R - 2 <= R^2 - 1
1.43 +
1.44 + R^2 - 1 <= R^2 - 1
1.45 +
1.46 +This suggests that a good radix would be one more than the largest
1.47 +value that can be held in half a machine word -- so, for example, as
1.48 +in this implementation, where we used a radix of 65536 on a machine
1.49 +with 4-byte words. Another advantage of a radix of this sort is that
1.50 +binary-level operations are easy on numbers in this representation.
1.51 +
1.52 +Here's an example multiplication worked out longhand in radix-10,
1.53 +using the above algorithm:
1.54 +
1.55 + a = 999
1.56 + b = x 999
1.57 + -------------
1.58 + p = 98001
1.59 +
1.60 +w = (a[jx] * b[ix]) + kin + c[ix + jx]
1.61 +c[ix+jx] = w % RADIX
1.62 +k = w / RADIX
1.63 + product
1.64 +ix jx a[jx] b[ix] kin w c[i+j] kout 000000
1.65 +0 0 9 9 0 81+0+0 1 8 000001
1.66 +0 1 9 9 8 81+8+0 9 8 000091
1.67 +0 2 9 9 8 81+8+0 9 8 000991
1.68 + 8 0 008991
1.69 +1 0 9 9 0 81+0+9 0 9 008901
1.70 +1 1 9 9 9 81+9+9 9 9 008901
1.71 +1 2 9 9 9 81+9+8 8 9 008901
1.72 + 9 0 098901
1.73 +2 0 9 9 0 81+0+9 0 9 098001
1.74 +2 1 9 9 9 81+9+8 8 9 098001
1.75 +2 2 9 9 9 81+9+9 9 9 098001
1.76 +
1.77 +------------------------------------------------------------------
1.78 + This Source Code Form is subject to the terms of the Mozilla Public
1.79 + # License, v. 2.0. If a copy of the MPL was not distributed with this
1.80 + # file, You can obtain one at http://mozilla.org/MPL/2.0/.
