diff options
Diffstat (limited to 'security/nss/lib/freebl/mpi/doc/square.txt')
| -rw-r--r-- | security/nss/lib/freebl/mpi/doc/square.txt | 109 |
1 files changed, 0 insertions, 109 deletions
diff --git a/security/nss/lib/freebl/mpi/doc/square.txt b/security/nss/lib/freebl/mpi/doc/square.txt deleted file mode 100644 index 319ea9657..000000000 --- a/security/nss/lib/freebl/mpi/doc/square.txt +++ /dev/null @@ -1,109 +0,0 @@ -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. - ------------------------------------------------------------------- -***** BEGIN LICENSE BLOCK ***** -Version: MPL 1.1/GPL 2.0/LGPL 2.1 - -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 the Initial Developer are Copyright (C) 1998, 2000 -the Initial Developer. All Rights Reserved. - -Contributor(s): - -Alternatively, the contents of this file may be used under the terms of -either the GNU General Public License Version 2 or later (the "GPL"), or -the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), -in which case the provisions of the GPL or the LGPL are applicable instead -of those above. If you wish to allow use of your version of this file only -under the terms of either the GPL or the LGPL, and not to allow others to -use your version of this file under the terms of the MPL, indicate your -decision by deleting the provisions above and replace them with the notice -and other provisions required by the GPL or the LGPL. If you do not delete -the provisions above, a recipient may use your version of this file under -the terms of any one of the MPL, the GPL or the LGPL. - -***** END LICENSE BLOCK ***** - -$Id$ - - |