1 files changed, 104 insertions, 0 deletions
diff --git a/security/nss/lib/freebl/mpi/doc/square.txt b/security/nss/lib/freebl/mpi/doc/square.txt
new file mode 100644
index 000000000..e0d28798a
--- /dev/null
+++ b/security/nss/lib/freebl/mpi/doc/square.txt
@@ -0,0 +1,104 @@
+Squaring Algorithm
+
+When you are squaring a value, you can take advantage of the fact that
+half the multiplications performed by the more general multiplication
+algorithm (see 'mul.txt' for a description) are redundant when the
+multiplicand equals the multiplier.
+
+In particular, the modified algorithm is:
+
+k = 0
+for j <- 0 to (#a - 1)
+  w = c[2*j] + (a[j] ^ 2);
+  k = w div R
+
+  for i <- j+1 to (#a - 1)
+    w = (2 * a[j] * a[i]) + k + c[i+j]
+    c[i+j] = w mod R
+    k = w div R
+  endfor
+  c[i+j] = k;
+  k = 0;
+endfor
+
+On the surface, this looks identical to the multiplication algorithm;
+however, note the following differences:
+
+  - precomputation of the leading term in the outer loop
+
+  - i runs from j+1 instead of from zero
+
+  - doubling of a[i] * a[j] in the inner product
+
+Unfortunately, the construction of the inner product is such that we
+need more than two digits to represent the inner product, in some
+cases.  In a C implementation, this means that some gymnastics must be
+performed in order to handle overflow, for which C has no direct
+abstraction.  We do this by observing the following:
+
+If we have multiplied a[i] and a[j], and the product is more than half
+the maximum value expressible in two digits, then doubling this result
+will overflow into a third digit.  If this occurs, we take note of the
+overflow, and double it anyway -- C integer arithmetic ignores
+overflow, so the two digits we get back should still be valid, modulo
+the overflow.
+
+Having doubled this value, we now have to add in the remainders and
+the digits already computed by earlier steps.  If we did not overflow
+in the previous step, we might still cause an overflow here.  That
+will happen whenever the maximum value expressible in two digits, less
+the amount we have to add, is greater than the result of the previous
+step.  Thus, the overflow computation is:
+
+
+  u = 0
+  w = a[i] * a[j]
+
+  if(w > (R - 1)/ 2)
+    u = 1;
+
+  w = w * 2
+  v = c[i + j] + k
+
+  if(u == 0 && (R - 1 - v) < w)
+    u = 1
+
+If there is an overflow, u will be 1, otherwise u will be 0.  The rest
+of the parameters are the same as they are in the above description.
+
+------------------------------------------------------------------
+The contents of this file are subject to the Mozilla Public
+License Version 1.1 (the "License"); you may not use this file
+except in compliance with the License. You may obtain a copy of
+the License at http://www.mozilla.org/MPL/
+
+Software distributed under the License is distributed on an "AS
+IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
+implied. See the License for the specific language governing
+rights and limitations under the License.
+
+The Original Code is the MPI Arbitrary Precision Integer Arithmetic
+library.
+
+The Initial Developer of the Original Code is 
+Michael J. Fromberger <sting@linguist.dartmouth.edu>
+
+Portions created by Michael J. Fromberger are 
+Copyright (C) 1998, 2000 Michael J. Fromberger. All Rights Reserved.
+
+Contributor(s):
+
+Alternatively, the contents of this file may be used under the
+terms of the GNU General Public License Version 2 or later (the
+"GPL"), in which case the provisions of the GPL are applicable
+instead of those above.  If you wish to allow use of your
+version of this file only under the terms of the GPL and not to
+allow others to use your version of this file under the MPL,
+indicate your decision by deleting the provisions above and
+replace them with the notice and other provisions required by
+the GPL.  If you do not delete the provisions above, a recipient
+may use your version of this file under either the MPL or the GPL.
+
+$Id$
+
+