diff options
Diffstat (limited to 'security/nss/lib/freebl/mpi/doc')
19 files changed, 0 insertions, 7965 deletions
diff --git a/security/nss/lib/freebl/mpi/doc/LICENSE b/security/nss/lib/freebl/mpi/doc/LICENSE deleted file mode 100644 index 35cca68ce..000000000 --- a/security/nss/lib/freebl/mpi/doc/LICENSE +++ /dev/null @@ -1,11 +0,0 @@ -Within this directory, each of the file listed below is licensed under -the terms given in the file LICENSE-MPL, also in this directory. - -basecvt.pod -gcd.pod -invmod.pod -isprime.pod -lap.pod -mpi-test.pod -prime.txt -prng.pod diff --git a/security/nss/lib/freebl/mpi/doc/LICENSE-MPL b/security/nss/lib/freebl/mpi/doc/LICENSE-MPL deleted file mode 100644 index 9ff410e4b..000000000 --- a/security/nss/lib/freebl/mpi/doc/LICENSE-MPL +++ /dev/null @@ -1,32 +0,0 @@ -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 Netscape security libraries. - -The Initial Developer of the Original Code is Netscape -Communications Corporation. Portions created by Netscape are -Copyright (C) 1994-2000 Netscape Communications Corporation. 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. - - diff --git a/security/nss/lib/freebl/mpi/doc/basecvt.pod b/security/nss/lib/freebl/mpi/doc/basecvt.pod deleted file mode 100644 index 5c072ccd6..000000000 --- a/security/nss/lib/freebl/mpi/doc/basecvt.pod +++ /dev/null @@ -1,63 +0,0 @@ -=head1 NAME - - basecvt - radix conversion for arbitrary precision integers - -=head1 SYNOPSIS - - basecvt <ibase> <obase> [values] - -=head1 DESCRIPTION - -The B<basecvt> program is a command-line tool for converting integers -of arbitrary precision from one radix to another. The current version -supports radix values from 2 (binary) to 64, inclusive. The first two -command line arguments specify the input and output radix, in base 10. -Any further arguments are taken to be integers notated in the input -radix, and these are converted to the output radix. The output is -written, one integer per line, to standard output. - -When reading integers, only digits considered "valid" for the input -radix are considered. Processing of an integer terminates when an -invalid input digit is encountered. So, for example, if you set the -input radix to 10 and enter '10ACF', B<basecvt> would assume that you -had entered '10' and ignore the rest of the string. - -If no values are provided, no output is written, but the program -simply terminates with a zero exit status. Error diagnostics are -written to standard error in the event of out-of-range radix -specifications. Regardless of the actual values of the input and -output radix, the radix arguments are taken to be in base 10 (decimal) -notation. - -=head1 DIGITS - -For radices from 2-10, standard ASCII decimal digits 0-9 are used for -both input and output. For radices from 11-36, the ASCII letters A-Z -are also included, following the convention used in hexadecimal. In -this range, input is accepted in either upper or lower case, although -on output only lower-case letters are used. - -For radices from 37-62, the output includes both upper- and lower-case -ASCII letters, and case matters. In this range, case is distinguished -both for input and for output values. - -For radices 63 and 64, the characters '+' (plus) and '/' (forward -solidus) are also used. These are derived from the MIME base64 -encoding scheme. The overall encoding is not the same as base64, -because the ASCII digits are used for the bottom of the range, and the -letters are shifted upward; however, the output will consist of the -same character set. - -This input and output behaviour is inherited from the MPI library used -by B<basecvt>, and so is not configurable at runtime. - -=head1 SEE ALSO - - dec2hex(1), hex2dec(1) - -=head1 AUTHOR - - Michael J. Fromberger <sting@linguist.dartmouth.edu> - Thayer School of Engineering, Hanover, New Hampshire, USA - - $Date$ diff --git a/security/nss/lib/freebl/mpi/doc/build b/security/nss/lib/freebl/mpi/doc/build deleted file mode 100755 index 64a2e6ac9..000000000 --- a/security/nss/lib/freebl/mpi/doc/build +++ /dev/null @@ -1,66 +0,0 @@ -#!/bin/sh -# ***** 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 -# the Initial Developer. All Rights Reserved. -# -# Contributor(s): -# Netscape Communications Corporation -# -# 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$ -# - -VERS="1.7p6" -SECT="1" -NAME="MPI Tools" - -echo "Building manual pages ..." -case $# in - 0) - files=`ls *.pod` - ;; - *) - files=$* - ;; -esac - -for name in $files -do - echo -n "$name ... " -# sname=`noext $name` - sname=`basename $name .pod` - pod2man --section="$SECT" --center="$NAME" --release="$VERS" $name > $sname.$SECT - echo "(done)" -done - -echo "Finished building." - diff --git a/security/nss/lib/freebl/mpi/doc/div.txt b/security/nss/lib/freebl/mpi/doc/div.txt deleted file mode 100644 index aaf4e14b8..000000000 --- a/security/nss/lib/freebl/mpi/doc/div.txt +++ /dev/null @@ -1,101 +0,0 @@ -Division - -This describes the division algorithm used by the MPI library. - -Input: a, b; a > b -Compute: Q, R; a = Qb + R - -The input numbers are normalized so that the high-order digit of b is -at least half the radix. This guarantees that we have a reasonable -way to guess at the digits of the quotient (this method was taken from -Knuth, vol. 2, with adaptations). - -To normalize, test the high-order digit of b. If it is less than half -the radix, multiply both a and b by d, where: - - radix - 1 - d = ----------- - bmax + 1 - -...where bmax is the high-order digit of b. Otherwise, set d = 1. - -Given normalize values for a and b, let the notation a[n] denote the -nth digit of a. Let #a be the number of significant figures of a (not -including any leading zeroes). - - Let R = 0 - Let p = #a - 1 - - while(p >= 0) - do - R = (R * radix) + a[p] - p = p - 1 - while(R < b and p >= 0) - - if(R < b) - break - - q = (R[#R - 1] * radix) + R[#R - 2] - q = q / b[#b - 1] - - T = b * q - - while(T > L) - q = q - 1 - T = T - b - endwhile - - L = L - T - - Q = (Q * radix) + q - - endwhile - -At this point, Q is the quotient, and R is the normalized remainder. -To denormalize R, compute: - - R = (R / d) - -At this point, you are finished. - ------------------------------------------------------------------- -***** 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$ - - diff --git a/security/nss/lib/freebl/mpi/doc/expt.txt b/security/nss/lib/freebl/mpi/doc/expt.txt deleted file mode 100644 index cea9dcc58..000000000 --- a/security/nss/lib/freebl/mpi/doc/expt.txt +++ /dev/null @@ -1,132 +0,0 @@ -Exponentiation - -For exponentiation, the MPI library uses a simple and fairly standard -square-and-multiply method. The algorithm is this: - -Input: a, b -Output: a ** b - - s = 1 - - while(b != 0) - if(b is odd) - s = s * a - endif - - b = b / 2 - - x = x * x - endwhile - - return s - -The modular exponentiation is done the same way, except replacing: - - s = s * a - -with - s = (s * a) mod m - -and replacing - - x = x * x - -with - - x = (x * x) mod m - -Here is a sample exponentiation using the MPI library, as compared to -the same problem solved by the Unix 'bc' program on my system: - -Computation of 2,381,283 ** 235 - -'bc' says: - -4385CA4A804D199FBEAD95FAD0796FAD0D0B51FC9C16743C45568C789666985DB719\ -4D90E393522F74C9601262C0514145A49F3B53D00983F95FDFCEA3D0043ECEF6227E\ -6FB59C924C3EE74447B359B5BF12A555D46CB819809EF423F004B55C587D6F0E8A55\ -4988036A42ACEF9F71459F97CEF6E574BD7373657111648626B1FF8EE15F663B2C0E\ -6BBE5082D4CDE8E14F263635AE8F35DB2C280819517BE388B5573B84C5A19C871685\ -FD408A6471F9D6AFAF5129A7548EAE926B40874B340285F44765BF5468CE20A13267\ -CD88CE6BC786ACED36EC7EA50F67FF27622575319068A332C3C0CB23E26FB55E26F4\ -5F732753A52B8E2FB4D4F42D894242613CA912A25486C3DEC9C66E5DB6182F6C1761\ -CF8CD0D255BE64B93836B27D452AE38F950EB98B517D4CF50D48F0165EF0CCCE1F5C\ -49BF18219FDBA0EEDD1A7E8B187B70C2BAED5EC5C6821EF27FAFB1CFF70111C52235\ -5E948B93A015AA1AE152B110BB5658CB14D3E45A48BFE7F082C1182672A455A695CD\ -A1855E8781E625F25B41B516E77F589FA420C3B058861EA138CF7A2C58DB3C7504FD\ -D29554D78237834CC5AE710D403CC4F6973D5012B7E117A8976B14A0B5AFA889BD47\ -92C461F0F96116F00A97AE9E83DC5203680CAF9A18A062566C145650AB86BE4F907F\ -A9F7AB4A700B29E1E5BACCD6DCBFA513E10832815F710807EED2E279081FEC61D619\ -AB270BEB3D3A1787B35A9DD41A8766CF21F3B5C693B3BAB1C2FA14A4ED202BC35743\ -E5CBE2391624D4F8C9BFBBC78D69764E7C6C5B11BF005677BFAD17D9278FFC1F158F\ -1B3683FF7960FA0608103792C4163DC0AF3E06287BB8624F8FE3A0FFBDF82ACECA2F\ -CFFF2E1AC93F3CA264A1B - -MPI says: - -4385CA4A804D199FBEAD95FAD0796FAD0D0B51FC9C16743C45568C789666985DB719\ -4D90E393522F74C9601262C0514145A49F3B53D00983F95FDFCEA3D0043ECEF6227E\ -6FB59C924C3EE74447B359B5BF12A555D46CB819809EF423F004B55C587D6F0E8A55\ -4988036A42ACEF9F71459F97CEF6E574BD7373657111648626B1FF8EE15F663B2C0E\ -6BBE5082D4CDE8E14F263635AE8F35DB2C280819517BE388B5573B84C5A19C871685\ -FD408A6471F9D6AFAF5129A7548EAE926B40874B340285F44765BF5468CE20A13267\ -CD88CE6BC786ACED36EC7EA50F67FF27622575319068A332C3C0CB23E26FB55E26F4\ -5F732753A52B8E2FB4D4F42D894242613CA912A25486C3DEC9C66E5DB6182F6C1761\ -CF8CD0D255BE64B93836B27D452AE38F950EB98B517D4CF50D48F0165EF0CCCE1F5C\ -49BF18219FDBA0EEDD1A7E8B187B70C2BAED5EC5C6821EF27FAFB1CFF70111C52235\ -5E948B93A015AA1AE152B110BB5658CB14D3E45A48BFE7F082C1182672A455A695CD\ -A1855E8781E625F25B41B516E77F589FA420C3B058861EA138CF7A2C58DB3C7504FD\ -D29554D78237834CC5AE710D403CC4F6973D5012B7E117A8976B14A0B5AFA889BD47\ -92C461F0F96116F00A97AE9E83DC5203680CAF9A18A062566C145650AB86BE4F907F\ -A9F7AB4A700B29E1E5BACCD6DCBFA513E10832815F710807EED2E279081FEC61D619\ -AB270BEB3D3A1787B35A9DD41A8766CF21F3B5C693B3BAB1C2FA14A4ED202BC35743\ -E5CBE2391624D4F8C9BFBBC78D69764E7C6C5B11BF005677BFAD17D9278FFC1F158F\ -1B3683FF7960FA0608103792C4163DC0AF3E06287BB8624F8FE3A0FFBDF82ACECA2F\ -CFFF2E1AC93F3CA264A1B - -Diff says: -% diff bc.txt mp.txt -% - ------------------------------------------------------------------- -***** 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$ - - - diff --git a/security/nss/lib/freebl/mpi/doc/gcd.pod b/security/nss/lib/freebl/mpi/doc/gcd.pod deleted file mode 100644 index 53b955f7e..000000000 --- a/security/nss/lib/freebl/mpi/doc/gcd.pod +++ /dev/null @@ -1,27 +0,0 @@ -=head1 NAME - - gcd - compute greatest common divisor of two integers - -=head1 SYNOPSIS - - gcd <a> <b> - -=head1 DESCRIPTION - -The B<gcd> program computes the greatest common divisor of two -arbitrary-precision integers I<a> and I<b>. The result is written in -standard decimal notation to the standard output. - -If I<b> is zero, B<gcd> will print an error message and exit. - -=head1 SEE ALSO - -invmod(1), isprime(1), lap(1) - -=head1 AUTHOR - - Michael J. Fromberger <sting@linguist.dartmouth.edu> - Thayer School of Engineering, Hanover, New Hampshire, USA - - $Date$ - diff --git a/security/nss/lib/freebl/mpi/doc/invmod.pod b/security/nss/lib/freebl/mpi/doc/invmod.pod deleted file mode 100644 index faa8f9d0c..000000000 --- a/security/nss/lib/freebl/mpi/doc/invmod.pod +++ /dev/null @@ -1,33 +0,0 @@ -=head1 NAME - - invmod - compute modular inverse of an integer - -=head1 SYNOPSIS - - invmod <a> <m> - -=head1 DESCRIPTION - -The B<invmod> program computes the inverse of I<a>, modulo I<m>, if -that inverse exists. Both I<a> and I<m> are arbitrary-precision -integers in decimal notation. The result is written in standard -decimal notation to the standard output. - -If there is no inverse, the message: - - No inverse - -...will be printed to the standard output (an inverse exists if and -only if the greatest common divisor of I<a> and I<m> is 1). - -=head1 SEE ALSO - -gcd(1), isprime(1), lap(1) - -=head1 AUTHOR - - Michael J. Fromberger <sting@linguist.dartmouth.edu> - Thayer School of Engineering, Hanover, New Hampshire, USA - - $Date$ - diff --git a/security/nss/lib/freebl/mpi/doc/isprime.pod b/security/nss/lib/freebl/mpi/doc/isprime.pod deleted file mode 100644 index a17c1c1bd..000000000 --- a/security/nss/lib/freebl/mpi/doc/isprime.pod +++ /dev/null @@ -1,62 +0,0 @@ -=head1 NAME - - isprime - probabilistic primality testing - -=head1 SYNOPSIS - - isprime <a> - -=head1 DESCRIPTION - -The B<isprime> program attempts to determine whether the arbitrary -precision integer I<a> is prime. It first tests I<a> for divisibility -by the first 170 or so small primes, and assuming I<a> is not -divisible by any of these, applies 15 iterations of the Rabin-Miller -probabilistic primality test. - -If the program discovers that the number is composite, it will print: - - Not prime (reason) - -Where I<reason> is either: - - divisible by small prime x - -Or: - - failed nth pseudoprime test - -In the first case, I<x> indicates the first small prime factor that -was found. In the second case, I<n> indicates which of the -pseudoprime tests failed (numbered from 1) - -If this happens, the number is definitely not prime. However, if the -number succeeds, this message results: - - Probably prime, 1 in 4^15 chance of false positive - -If this happens, the number is prime with very high probability, but -its primality has not been absolutely proven, only demonstrated to a -very convincing degree. - -The value I<a> can be input in standard decimal notation, or, if it is -prefixed with I<Ox>, it will be read as hexadecimal. - -=head1 ENVIRONMENT - -You can control how many iterations of Rabin-Miller are performed on -the candidate number by setting the I<RM_TESTS> environment variable -to an integer value before starting up B<isprime>. This will change -the output slightly if the number passes all the tests. - -=head1 SEE ALSO - -gcd(1), invmod(1), lap(1) - -=head1 AUTHOR - - Michael J. Fromberger <sting@linguist.dartmouth.edu> - Thayer School of Engineering, Hanover, New Hampshire, USA - - $Date$ - diff --git a/security/nss/lib/freebl/mpi/doc/lap.pod b/security/nss/lib/freebl/mpi/doc/lap.pod deleted file mode 100644 index ac100639b..000000000 --- a/security/nss/lib/freebl/mpi/doc/lap.pod +++ /dev/null @@ -1,35 +0,0 @@ -=head1 NAME - - lap - compute least annihilating power of a number - -=head1 SYNOPSIS - - lap <a> <m> - -=head1 DESCRIPTION - -The B<lap> program computes the order of I<a> modulo I<m>, for -arbitrary precision integers I<a> and I<m>. The B<order> of I<a> -modulo I<m> is defined as the smallest positive value I<n> for which -I<a> raised to the I<n>th power, modulo I<m>, is equal to 1. The -order may not exist, if I<m> is composite. - -=head1 RESTRICTIONS - -This program is very slow, especially for large moduli. It is -intended as a way to help find primitive elements in a modular field, -but it does not do so in a particularly inefficient manner. It was -written simply to help verify that a particular candidate does not -have an obviously short cycle mod I<m>. - -=head1 SEE ALSO - -gcd(1), invmod(1), isprime(1) - -=head1 AUTHOR - - Michael J. Fromberger <sting@linguist.dartmouth.edu> - Thayer School of Engineering, Hanover, New Hampshire, USA - - $Date$ - diff --git a/security/nss/lib/freebl/mpi/doc/mpi-test.pod b/security/nss/lib/freebl/mpi/doc/mpi-test.pod deleted file mode 100644 index 16050f09f..000000000 --- a/security/nss/lib/freebl/mpi/doc/mpi-test.pod +++ /dev/null @@ -1,49 +0,0 @@ -=head1 NAME - - mpi-test - automated test program for MPI library - -=head1 SYNOPSIS - - mpi-test <suite-name> [quiet] - mpi-test list - mpi-test help - -=head1 DESCRIPTION - -The B<mpi-test> program is a general unit test driver for the MPI -library. It is used to verify that the library works as it is -supposed to on your architecture. As with most such things, passing -all the tests in B<mpi-test> does not guarantee the code is correct, -but if any of them fail, there are certainly problems. - -Each major function of the library can be tested individually. For a -list of the test suites understood by B<mpi-test>, run it with the -I<list> command line option: - - mpi-test list - -This will display a list of the available test suites and a brief -synopsis of what each one does. For a brief overview of this -document, run B<mpi-test> I<help>. - -B<mpi-test> exits with a zero status if the selected test succeeds, or -a nonzero status if it fails. If a I<suite-name> which is not -understood by B<mpi-test> is given, a diagnostic is printed to the -standard error, and the program exits with a result code of 2. If a -test fails, the result code will be 1, and a diagnostic is ordinarily -printed to the standard error. However, if the I<quiet> option is -provided, these diagnostics will be suppressed. - -=head1 RESTRICTIONS - -Only a few canned test cases are provided. The solutions have been -verified using the GNU bc(1) program, so bugs there may cause problems -here; however, this is very unlikely, so if a test fails, it is almost -certainly my fault, not bc(1)'s. - -=head1 AUTHOR - - Michael J. Fromberger <sting@linguist.dartmouth.edu> - Thayer School of Engineering, Hanover, New Hampshire, USA - - $Date$ diff --git a/security/nss/lib/freebl/mpi/doc/mul.txt b/security/nss/lib/freebl/mpi/doc/mul.txt deleted file mode 100644 index 01464f251..000000000 --- a/security/nss/lib/freebl/mpi/doc/mul.txt +++ /dev/null @@ -1,114 +0,0 @@ -Multiplication - -This describes the multiplication algorithm used by the MPI library. - -This is basically a standard "schoolbook" algorithm. It is slow -- -O(mn) for m = #a, n = #b -- but easy to implement and verify. -Basically, we run two nested loops, as illustrated here (R is the -radix): - -k = 0 -for j <- 0 to (#b - 1) - for i <- 0 to (#a - 1) - w = (a[j] * b[i]) + k + c[i+j] - c[i+j] = w mod R - k = w div R - endfor - c[i+j] = k; - k = 0; -endfor - -It is necessary that 'w' have room for at least two radix R digits. -The product of any two digits in radix R is at most: - - (R - 1)(R - 1) = R^2 - 2R + 1 - -Since a two-digit radix-R number can hold R^2 - 1 distinct values, -this insures that the product will fit into the two-digit register. - -To insure that two digits is enough for w, we must also show that -there is room for the carry-in from the previous multiplication, and -the current value of the product digit that is being recomputed. -Assuming each of these may be as big as R - 1 (and no larger, -certainly), two digits will be enough if and only if: - - (R^2 - 2R + 1) + 2(R - 1) <= R^2 - 1 - -Solving this equation shows that, indeed, this is the case: - - R^2 - 2R + 1 + 2R - 2 <= R^2 - 1 - - R^2 - 1 <= R^2 - 1 - -This suggests that a good radix would be one more than the largest -value that can be held in half a machine word -- so, for example, as -in this implementation, where we used a radix of 65536 on a machine -with 4-byte words. Another advantage of a radix of this sort is that -binary-level operations are easy on numbers in this representation. - -Here's an example multiplication worked out longhand in radix-10, -using the above algorithm: - - a = 999 - b = x 999 - ------------- - p = 98001 - -w = (a[jx] * b[ix]) + kin + c[ix + jx] -c[ix+jx] = w % RADIX -k = w / RADIX - product -ix jx a[jx] b[ix] kin w c[i+j] kout 000000 -0 0 9 9 0 81+0+0 1 8 000001 -0 1 9 9 8 81+8+0 9 8 000091 -0 2 9 9 8 81+8+0 9 8 000991 - 8 0 008991 -1 0 9 9 0 81+0+9 0 9 008901 -1 1 9 9 9 81+9+9 9 9 008901 -1 2 9 9 9 81+9+8 8 9 008901 - 9 0 098901 -2 0 9 9 0 81+0+9 0 9 098001 -2 1 9 9 9 81+9+8 8 9 098001 -2 2 9 9 9 81+9+9 9 9 098001 - ------------------------------------------------------------------- -***** 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$ - - diff --git a/security/nss/lib/freebl/mpi/doc/pi.txt b/security/nss/lib/freebl/mpi/doc/pi.txt deleted file mode 100644 index 01c82abe9..000000000 --- a/security/nss/lib/freebl/mpi/doc/pi.txt +++ /dev/null @@ -1,90 +0,0 @@ -This file describes how pi is computed by the program in 'pi.c' (see -the utils subdirectory). - -Basically, we use Machin's formula, which is what everyone in the -world uses as a simple method for computing approximations to pi. -This works for up to a few thousand digits without too much effort. -Beyond that, though, it gets too slow. - -Machin's formula states: - - pi := 16 * arctan(1/5) - 4 * arctan(1/239) - -We compute this in integer arithmetic by first multiplying everything -through by 10^d, where 'd' is the number of digits of pi we wanted to -compute. It turns out, the last few digits will be wrong, but the -number that are wrong is usually very small (ordinarly only 2-3). -Having done this, we compute the arctan() function using the formula: - - 1 1 1 1 1 - arctan(1/x) := --- - ----- + ----- - ----- + ----- - ... - x 3 x^3 5 x^5 7 x^7 9 x^9 - -This is done iteratively by computing the first term manually, and -then iteratively dividing x^2 and k, where k = 3, 5, 7, ... out of the -current figure. This is then added to (or subtracted from) a running -sum, as appropriate. The iteration continues until we overflow our -available precision and the current figure goes to zero under integer -division. At that point, we're finished. - -Actually, we get a couple extra bits of precision out of the fact that -we know we're computing y * arctan(1/x), by setting up the multiplier -as: - - y * 10^d - -... instead of just 10^d. There is also a bit of cleverness in how -the loop is constructed, to avoid special-casing the first term. -Check out the code for arctan() in 'pi.c', if you are interested in -seeing how it is set up. - -Thanks to Jason P. for this algorithm, which I assembled from notes -and programs found on his cool "Pile of Pi Programs" page, at: - - http://www.isr.umd.edu/~jasonp/pipage.html - -Thanks also to Henrik Johansson <Henrik.Johansson@Nexus.Comm.SE>, from -whose pi program I borrowed the clever idea of pre-multiplying by x in -order to avoid a special case on the loop iteration. - ------------------------------------------------------------------- -***** 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$ - - diff --git a/security/nss/lib/freebl/mpi/doc/prime.txt b/security/nss/lib/freebl/mpi/doc/prime.txt deleted file mode 100644 index 694797d5f..000000000 --- a/security/nss/lib/freebl/mpi/doc/prime.txt +++ /dev/null @@ -1,6542 +0,0 @@ -2 -3 -5 -7 -11 -13 -17 -19 -23 -29 -31 -37 -41 -43 -47 -53 -59 -61 -67 -71 -73 -79 -83 -89 -97 -101 -103 -107 -109 -113 -127 -131 -137 -139 -149 -151 -157 -163 -167 -173 -179 -181 -191 -193 -197 -199 -211 -223 -227 -229 -233 -239 -241 -251 -257 -263 -269 -271 -277 -281 -283 -293 -307 -311 -313 -317 -331 -337 -347 -349 -353 -359 -367 -373 -379 -383 -389 -397 -401 -409 -419 -421 -431 -433 -439 -443 -449 -457 -461 -463 -467 -479 -487 -491 -499 -503 -509 -521 -523 -541 -547 -557 -563 -569 -571 -577 -587 -593 -599 -601 -607 -613 -617 -619 -631 -641 -643 -647 -653 -659 -661 -673 -677 -683 -691 -701 -709 -719 -727 -733 -739 -743 -751 -757 -761 -769 -773 -787 -797 -809 -811 -821 -823 -827 -829 -839 -853 -857 -859 -863 -877 -881 -883 -887 -907 -911 -919 -929 -937 -941 -947 -953 -967 -971 -977 -983 -991 -997 -1009 -1013 -1019 -1021 -1031 -1033 -1039 -1049 -1051 -1061 -1063 -1069 -1087 -1091 -1093 -1097 -1103 -1109 -1117 -1123 -1129 -1151 -1153 -1163 -1171 -1181 -1187 -1193 -1201 -1213 -1217 -1223 -1229 -1231 -1237 -1249 -1259 -1277 -1279 -1283 -1289 -1291 -1297 -1301 -1303 -1307 -1319 -1321 -1327 -1361 -1367 -1373 -1381 -1399 -1409 -1423 -1427 -1429 -1433 -1439 -1447 -1451 -1453 -1459 -1471 -1481 -1483 -1487 -1489 -1493 -1499 -1511 -1523 -1531 -1543 -1549 -1553 -1559 -1567 -1571 -1579 -1583 -1597 -1601 -1607 -1609 -1613 -1619 -1621 -1627 -1637 -1657 -1663 -1667 -1669 -1693 -1697 -1699 -1709 -1721 -1723 -1733 -1741 -1747 -1753 -1759 -1777 -1783 -1787 -1789 -1801 -1811 -1823 -1831 -1847 -1861 -1867 -1871 -1873 -1877 -1879 -1889 -1901 -1907 -1913 -1931 -1933 -1949 -1951 -1973 -1979 -1987 -1993 -1997 -1999 -2003 -2011 -2017 -2027 -2029 -2039 -2053 -2063 -2069 -2081 -2083 -2087 -2089 -2099 -2111 -2113 -2129 -2131 -2137 -2141 -2143 -2153 -2161 -2179 -2203 -2207 -2213 -2221 -2237 -2239 -2243 -2251 -2267 -2269 -2273 -2281 -2287 -2293 -2297 -2309 -2311 -2333 -2339 -2341 -2347 -2351 -2357 -2371 -2377 -2381 -2383 -2389 -2393 -2399 -2411 -2417 -2423 -2437 -2441 -2447 -2459 -2467 -2473 -2477 -2503 -2521 -2531 -2539 -2543 -2549 -2551 -2557 -2579 -2591 -2593 -2609 -2617 -2621 -2633 -2647 -2657 -2659 -2663 -2671 -2677 -2683 -2687 -2689 -2693 -2699 -2707 -2711 -2713 -2719 -2729 -2731 -2741 -2749 -2753 -2767 -2777 -2789 -2791 -2797 -2801 -2803 -2819 -2833 -2837 -2843 -2851 -2857 -2861 -2879 -2887 -2897 -2903 -2909 -2917 -2927 -2939 -2953 -2957 -2963 -2969 -2971 -2999 -3001 -3011 -3019 -3023 -3037 -3041 -3049 -3061 -3067 -3079 -3083 -3089 -3109 -3119 -3121 -3137 -3163 -3167 -3169 -3181 -3187 -3191 -3203 -3209 -3217 -3221 -3229 -3251 -3253 -3257 -3259 -3271 -3299 -3301 -3307 -3313 -3319 -3323 -3329 -3331 -3343 -3347 -3359 -3361 -3371 -3373 -3389 -3391 -3407 -3413 -3433 -3449 -3457 -3461 -3463 -3467 -3469 -3491 -3499 -3511 -3517 -3527 -3529 -3533 -3539 -3541 -3547 -3557 -3559 -3571 -3581 -3583 -3593 -3607 -3613 -3617 -3623 -3631 -3637 -3643 -3659 -3671 -3673 -3677 -3691 -3697 -3701 -3709 -3719 -3727 -3733 -3739 -3761 -3767 -3769 -3779 -3793 -3797 -3803 -3821 -3823 -3833 -3847 -3851 -3853 -3863 -3877 -3881 -3889 -3907 -3911 -3917 -3919 -3923 -3929 -3931 -3943 -3947 -3967 -3989 -4001 -4003 -4007 -4013 -4019 -4021 -4027 -4049 -4051 -4057 -4073 -4079 -4091 -4093 -4099 -4111 -4127 -4129 -4133 -4139 -4153 -4157 -4159 -4177 -4201 -4211 -4217 -4219 -4229 -4231 -4241 -4243 -4253 -4259 -4261 -4271 -4273 -4283 -4289 -4297 -4327 -4337 -4339 -4349 -4357 -4363 -4373 -4391 -4397 -4409 -4421 -4423 -4441 -4447 -4451 -4457 -4463 -4481 -4483 -4493 -4507 -4513 -4517 -4519 -4523 -4547 -4549 -4561 -4567 -4583 -4591 -4597 -4603 -4621 -4637 -4639 -4643 -4649 -4651 -4657 -4663 -4673 -4679 -4691 -4703 -4721 -4723 -4729 -4733 -4751 -4759 -4783 -4787 -4789 -4793 -4799 -4801 -4813 -4817 -4831 -4861 -4871 -4877 -4889 -4903 -4909 -4919 -4931 -4933 -4937 -4943 -4951 -4957 -4967 -4969 -4973 -4987 -4993 -4999 -5003 -5009 -5011 -5021 -5023 -5039 -5051 -5059 -5077 -5081 -5087 -5099 -5101 -5107 -5113 -5119 -5147 -5153 -5167 -5171 -5179 -5189 -5197 -5209 -5227 -5231 -5233 -5237 -5261 -5273 -5279 -5281 -5297 -5303 -5309 -5323 -5333 -5347 -5351 -5381 -5387 -5393 -5399 -5407 -5413 -5417 -5419 -5431 -5437 -5441 -5443 -5449 -5471 -5477 -5479 -5483 -5501 -5503 -5507 -5519 -5521 -5527 -5531 -5557 -5563 -5569 -5573 -5581 -5591 -5623 -5639 -5641 -5647 -5651 -5653 -5657 -5659 -5669 -5683 -5689 -5693 -5701 -5711 -5717 -5737 -5741 -5743 -5749 -5779 -5783 -5791 -5801 -5807 -5813 -5821 -5827 -5839 -5843 -5849 -5851 -5857 -5861 -5867 -5869 -5879 -5881 -5897 -5903 -5923 -5927 -5939 -5953 -5981 -5987 -6007 -6011 -6029 -6037 -6043 -6047 -6053 -6067 -6073 -6079 -6089 -6091 -6101 -6113 -6121 -6131 -6133 -6143 -6151 -6163 -6173 -6197 -6199 -6203 -6211 -6217 -6221 -6229 -6247 -6257 -6263 -6269 -6271 -6277 -6287 -6299 -6301 -6311 -6317 -6323 -6329 -6337 -6343 -6353 -6359 -6361 -6367 -6373 -6379 -6389 -6397 -6421 -6427 -6449 -6451 -6469 -6473 -6481 -6491 -6521 -6529 -6547 -6551 -6553 -6563 -6569 -6571 -6577 -6581 -6599 -6607 -6619 -6637 -6653 -6659 -6661 -6673 -6679 -6689 -6691 -6701 -6703 -6709 -6719 -6733 -6737 -6761 -6763 -6779 -6781 -6791 -6793 -6803 -6823 -6827 -6829 -6833 -6841 -6857 -6863 -6869 -6871 -6883 -6899 -6907 -6911 -6917 -6947 -6949 -6959 -6961 -6967 -6971 -6977 -6983 -6991 -6997 -7001 -7013 -7019 -7027 -7039 -7043 -7057 -7069 -7079 -7103 -7109 -7121 -7127 -7129 -7151 -7159 -7177 -7187 -7193 -7207 -7211 -7213 -7219 -7229 -7237 -7243 -7247 -7253 -7283 -7297 -7307 -7309 -7321 -7331 -7333 -7349 -7351 -7369 -7393 -7411 -7417 -7433 -7451 -7457 -7459 -7477 -7481 -7487 -7489 -7499 -7507 -7517 -7523 -7529 -7537 -7541 -7547 -7549 -7559 -7561 -7573 -7577 -7583 -7589 -7591 -7603 -7607 -7621 -7639 -7643 -7649 -7669 -7673 -7681 -7687 -7691 -7699 -7703 -7717 -7723 -7727 -7741 -7753 -7757 -7759 -7789 -7793 -7817 -7823 -7829 -7841 -7853 -7867 -7873 -7877 -7879 -7883 -7901 -7907 -7919 -7927 -7933 -7937 -7949 -7951 -7963 -7993 -8009 -8011 -8017 -8039 -8053 -8059 -8069 -8081 -8087 -8089 -8093 -8101 -8111 -8117 -8123 -8147 -8161 -8167 -8171 -8179 -8191 -8209 -8219 -8221 -8231 -8233 -8237 -8243 -8263 -8269 -8273 -8287 -8291 -8293 -8297 -8311 -8317 -8329 -8353 -8363 -8369 -8377 -8387 -8389 -8419 -8423 -8429 -8431 -8443 -8447 -8461 -8467 -8501 -8513 -8521 -8527 -8537 -8539 -8543 -8563 -8573 -8581 -8597 -8599 -8609 -8623 -8627 -8629 -8641 -8647 -8663 -8669 -8677 -8681 -8689 -8693 -8699 -8707 -8713 -8719 -8731 -8737 -8741 -8747 -8753 -8761 -8779 -8783 -8803 -8807 -8819 -8821 -8831 -8837 -8839 -8849 -8861 -8863 -8867 -8887 -8893 -8923 -8929 -8933 -8941 -8951 -8963 -8969 -8971 -8999 -9001 -9007 -9011 -9013 -9029 -9041 -9043 -9049 -9059 -9067 -9091 -9103 -9109 -9127 -9133 -9137 -9151 -9157 -9161 -9173 -9181 -9187 -9199 -9203 -9209 -9221 -9227 -9239 -9241 -9257 -9277 -9281 -9283 -9293 -9311 -9319 -9323 -9337 -9341 -9343 -9349 -9371 -9377 -9391 -9397 -9403 -9413 -9419 -9421 -9431 -9433 -9437 -9439 -9461 -9463 -9467 -9473 -9479 -9491 -9497 -9511 -9521 -9533 -9539 -9547 -9551 -9587 -9601 -9613 -9619 -9623 -9629 -9631 -9643 -9649 -9661 -9677 -9679 -9689 -9697 -9719 -9721 -9733 -9739 -9743 -9749 -9767 -9769 -9781 -9787 -9791 -9803 -9811 -9817 -9829 -9833 -9839 -9851 -9857 -9859 -9871 -9883 -9887 -9901 -9907 -9923 -9929 -9931 -9941 -9949 -9967 -9973 -10007 -10009 -10037 -10039 -10061 -10067 -10069 -10079 -10091 -10093 -10099 -10103 -10111 -10133 -10139 -10141 -10151 -10159 -10163 -10169 -10177 -10181 -10193 -10211 -10223 -10243 -10247 -10253 -10259 -10267 -10271 -10273 -10289 -10301 -10303 -10313 -10321 -10331 -10333 -10337 -10343 -10357 -10369 -10391 -10399 -10427 -10429 -10433 -10453 -10457 -10459 -10463 -10477 -10487 -10499 -10501 -10513 -10529 -10531 -10559 -10567 -10589 -10597 -10601 -10607 -10613 -10627 -10631 -10639 -10651 -10657 -10663 -10667 -10687 -10691 -10709 -10711 -10723 -10729 -10733 -10739 -10753 -10771 -10781 -10789 -10799 -10831 -10837 -10847 -10853 -10859 -10861 -10867 -10883 -10889 -10891 -10903 -10909 -10937 -10939 -10949 -10957 -10973 -10979 -10987 -10993 -11003 -11027 -11047 -11057 -11059 -11069 -11071 -11083 -11087 -11093 -11113 -11117 -11119 -11131 -11149 -11159 -11161 -11171 -11173 -11177 -11197 -11213 -11239 -11243 -11251 -11257 -11261 -11273 -11279 -11287 -11299 -11311 -11317 -11321 -11329 -11351 -11353 -11369 -11383 -11393 -11399 -11411 -11423 -11437 -11443 -11447 -11467 -11471 -11483 -11489 -11491 -11497 -11503 -11519 -11527 -11549 -11551 -11579 -11587 -11593 -11597 -11617 -11621 -11633 -11657 -11677 -11681 -11689 -11699 -11701 -11717 -11719 -11731 -11743 -11777 -11779 -11783 -11789 -11801 -11807 -11813 -11821 -11827 -11831 -11833 -11839 -11863 -11867 -11887 -11897 -11903 -11909 -11923 -11927 -11933 -11939 -11941 -11953 -11959 -11969 -11971 -11981 -11987 -12007 -12011 -12037 -12041 -12043 -12049 -12071 -12073 -12097 -12101 -12107 -12109 -12113 -12119 -12143 -12149 -12157 -12161 -12163 -12197 -12203 -12211 -12227 -12239 -12241 -12251 -12253 -12263 -12269 -12277 -12281 -12289 -12301 -12323 -12329 -12343 -12347 -12373 -12377 -12379 -12391 -12401 -12409 -12413 -12421 -12433 -12437 -12451 -12457 -12473 -12479 -12487 -12491 -12497 -12503 -12511 -12517 -12527 -12539 -12541 -12547 -12553 -12569 -12577 -12583 -12589 -12601 -12611 -12613 -12619 -12637 -12641 -12647 -12653 -12659 -12671 -12689 -12697 -12703 -12713 -12721 -12739 -12743 -12757 -12763 -12781 -12791 -12799 -12809 -12821 -12823 -12829 -12841 -12853 -12889 -12893 -12899 -12907 -12911 -12917 -12919 -12923 -12941 -12953 -12959 -12967 -12973 -12979 -12983 -13001 -13003 -13007 -13009 -13033 -13037 -13043 -13049 -13063 -13093 -13099 -13103 -13109 -13121 -13127 -13147 -13151 -13159 -13163 -13171 -13177 -13183 -13187 -13217 -13219 -13229 -13241 -13249 -13259 -13267 -13291 -13297 -13309 -13313 -13327 -13331 -13337 -13339 -13367 -13381 -13397 -13399 -13411 -13417 -13421 -13441 -13451 -13457 -13463 -13469 -13477 -13487 -13499 -13513 -13523 -13537 -13553 -13567 -13577 -13591 -13597 -13613 -13619 -13627 -13633 -13649 -13669 -13679 -13681 -13687 -13691 -13693 -13697 -13709 -13711 -13721 -13723 -13729 -13751 -13757 -13759 -13763 -13781 -13789 -13799 -13807 -13829 -13831 -13841 -13859 -13873 -13877 -13879 -13883 -13901 -13903 -13907 -13913 -13921 -13931 -13933 -13963 -13967 -13997 -13999 -14009 -14011 -14029 -14033 -14051 -14057 -14071 -14081 -14083 -14087 -14107 -14143 -14149 -14153 -14159 -14173 -14177 -14197 -14207 -14221 -14243 -14249 -14251 -14281 -14293 -14303 -14321 -14323 -14327 -14341 -14347 -14369 -14387 -14389 -14401 -14407 -14411 -14419 -14423 -14431 -14437 -14447 -14449 -14461 -14479 -14489 -14503 -14519 -14533 -14537 -14543 -14549 -14551 -14557 -14561 -14563 -14591 -14593 -14621 -14627 -14629 -14633 -14639 -14653 -14657 -14669 -14683 -14699 -14713 -14717 -14723 -14731 -14737 -14741 -14747 -14753 -14759 -14767 -14771 -14779 -14783 -14797 -14813 -14821 -14827 -14831 -14843 -14851 -14867 -14869 -14879 -14887 -14891 -14897 -14923 -14929 -14939 -14947 -14951 -14957 -14969 -14983 -15013 -15017 -15031 -15053 -15061 -15073 -15077 -15083 -15091 -15101 -15107 -15121 -15131 -15137 -15139 -15149 -15161 -15173 -15187 -15193 -15199 -15217 -15227 -15233 -15241 -15259 -15263 -15269 -15271 -15277 -15287 -15289 -15299 -15307 -15313 -15319 -15329 -15331 -15349 -15359 -15361 -15373 -15377 -15383 -15391 -15401 -15413 -15427 -15439 -15443 -15451 -15461 -15467 -15473 -15493 -15497 -15511 -15527 -15541 -15551 -15559 -15569 -15581 -15583 -15601 -15607 -15619 -15629 -15641 -15643 -15647 -15649 -15661 -15667 -15671 -15679 -15683 -15727 -15731 -15733 -15737 -15739 -15749 -15761 -15767 -15773 -15787 -15791 -15797 -15803 -15809 -15817 -15823 -15859 -15877 -15881 -15887 -15889 -15901 -15907 -15913 -15919 -15923 -15937 -15959 -15971 -15973 -15991 -16001 -16007 -16033 -16057 -16061 -16063 -16067 -16069 -16073 -16087 -16091 -16097 -16103 -16111 -16127 -16139 -16141 -16183 -16187 -16189 -16193 -16217 -16223 -16229 -16231 -16249 -16253 -16267 -16273 -16301 -16319 -16333 -16339 -16349 -16361 -16363 -16369 -16381 -16411 -16417 -16421 -16427 -16433 -16447 -16451 -16453 -16477 -16481 -16487 -16493 -16519 -16529 -16547 -16553 -16561 -16567 -16573 -16603 -16607 -16619 -16631 -16633 -16649 -16651 -16657 -16661 -16673 -16691 -16693 -16699 -16703 -16729 -16741 -16747 -16759 -16763 -16787 -16811 -16823 -16829 -16831 -16843 -16871 -16879 -16883 -16889 -16901 -16903 -16921 -16927 -16931 -16937 -16943 -16963 -16979 -16981 -16987 -16993 -17011 -17021 -17027 -17029 -17033 -17041 -17047 -17053 -17077 -17093 -17099 -17107 -17117 -17123 -17137 -17159 -17167 -17183 -17189 -17191 -17203 -17207 -17209 -17231 -17239 -17257 -17291 -17293 -17299 -17317 -17321 -17327 -17333 -17341 -17351 -17359 -17377 -17383 -17387 -17389 -17393 -17401 -17417 -17419 -17431 -17443 -17449 -17467 -17471 -17477 -17483 -17489 -17491 -17497 -17509 -17519 -17539 -17551 -17569 -17573 -17579 -17581 -17597 -17599 -17609 -17623 -17627 -17657 -17659 -17669 -17681 -17683 -17707 -17713 -17729 -17737 -17747 -17749 -17761 -17783 -17789 -17791 -17807 -17827 -17837 -17839 -17851 -17863 -17881 -17891 -17903 -17909 -17911 -17921 -17923 -17929 -17939 -17957 -17959 -17971 -17977 -17981 -17987 -17989 -18013 -18041 -18043 -18047 -18049 -18059 -18061 -18077 -18089 -18097 -18119 -18121 -18127 -18131 -18133 -18143 -18149 -18169 -18181 -18191 -18199 -18211 -18217 -18223 -18229 -18233 -18251 -18253 -18257 -18269 -18287 -18289 -18301 -18307 -18311 -18313 -18329 -18341 -18353 -18367 -18371 -18379 -18397 -18401 -18413 -18427 -18433 -18439 -18443 -18451 -18457 -18461 -18481 -18493 -18503 -18517 -18521 -18523 -18539 -18541 -18553 -18583 -18587 -18593 -18617 -18637 -18661 -18671 -18679 -18691 -18701 -18713 -18719 -18731 -18743 -18749 -18757 -18773 -18787 -18793 -18797 -18803 -18839 -18859 -18869 -18899 -18911 -18913 -18917 -18919 -18947 -18959 -18973 -18979 -19001 -19009 -19013 -19031 -19037 -19051 -19069 -19073 -19079 -19081 -19087 -19121 -19139 -19141 -19157 -19163 -19181 -19183 -19207 -19211 -19213 -19219 -19231 -19237 -19249 -19259 -19267 -19273 -19289 -19301 -19309 -19319 -19333 -19373 -19379 -19381 -19387 -19391 -19403 -19417 -19421 -19423 -19427 -19429 -19433 -19441 -19447 -19457 -19463 -19469 -19471 -19477 -19483 -19489 -19501 -19507 -19531 -19541 -19543 -19553 -19559 -19571 -19577 -19583 -19597 -19603 -19609 -19661 -19681 -19687 -19697 -19699 -19709 -19717 -19727 -19739 -19751 -19753 -19759 -19763 -19777 -19793 -19801 -19813 -19819 -19841 -19843 -19853 -19861 -19867 -19889 -19891 -19913 -19919 -19927 -19937 -19949 -19961 -19963 -19973 -19979 -19991 -19993 -19997 -20011 -20021 -20023 -20029 -20047 -20051 -20063 -20071 -20089 -20101 -20107 -20113 -20117 -20123 -20129 -20143 -20147 -20149 -20161 -20173 -20177 -20183 -20201 -20219 -20231 -20233 -20249 -20261 -20269 -20287 -20297 -20323 -20327 -20333 -20341 -20347 -20353 -20357 -20359 -20369 -20389 -20393 -20399 -20407 -20411 -20431 -20441 -20443 -20477 -20479 -20483 -20507 -20509 -20521 -20533 -20543 -20549 -20551 -20563 -20593 -20599 -20611 -20627 -20639 -20641 -20663 -20681 -20693 -20707 -20717 -20719 -20731 -20743 -20747 -20749 -20753 -20759 -20771 -20773 -20789 -20807 -20809 -20849 -20857 -20873 -20879 -20887 -20897 -20899 -20903 -20921 -20929 -20939 -20947 -20959 -20963 -20981 -20983 -21001 -21011 -21013 -21017 -21019 -21023 -21031 -21059 -21061 -21067 -21089 -21101 -21107 -21121 -21139 -21143 -21149 -21157 -21163 -21169 -21179 -21187 -21191 -21193 -21211 -21221 -21227 -21247 -21269 -21277 -21283 -21313 -21317 -21319 -21323 -21341 -21347 -21377 -21379 -21383 -21391 -21397 -21401 -21407 -21419 -21433 -21467 -21481 -21487 -21491 -21493 -21499 -21503 -21517 -21521 -21523 -21529 -21557 -21559 -21563 -21569 -21577 -21587 -21589 -21599 -21601 -21611 -21613 -21617 -21647 -21649 -21661 -21673 -21683 -21701 -21713 -21727 -21737 -21739 -21751 -21757 -21767 -21773 -21787 -21799 -21803 -21817 -21821 -21839 -21841 -21851 -21859 -21863 -21871 -21881 -21893 -21911 -21929 -21937 -21943 -21961 -21977 -21991 -21997 -22003 -22013 -22027 -22031 -22037 -22039 -22051 -22063 -22067 -22073 -22079 -22091 -22093 -22109 -22111 -22123 -22129 -22133 -22147 -22153 -22157 -22159 -22171 -22189 -22193 -22229 -22247 -22259 -22271 -22273 -22277 -22279 -22283 -22291 -22303 -22307 -22343 -22349 -22367 -22369 -22381 -22391 -22397 -22409 -22433 -22441 -22447 -22453 -22469 -22481 -22483 -22501 -22511 -22531 -22541 -22543 -22549 -22567 -22571 -22573 -22613 -22619 -22621 -22637 -22639 -22643 -22651 -22669 -22679 -22691 -22697 -22699 -22709 -22717 -22721 -22727 -22739 -22741 -22751 -22769 -22777 -22783 -22787 -22807 -22811 -22817 -22853 -22859 -22861 -22871 -22877 -22901 -22907 -22921 -22937 -22943 -22961 -22963 -22973 -22993 -23003 -23011 -23017 -23021 -23027 -23029 -23039 -23041 -23053 -23057 -23059 -23063 -23071 -23081 -23087 -23099 -23117 -23131 -23143 -23159 -23167 -23173 -23189 -23197 -23201 -23203 -23209 -23227 -23251 -23269 -23279 -23291 -23293 -23297 -23311 -23321 -23327 -23333 -23339 -23357 -23369 -23371 -23399 -23417 -23431 -23447 -23459 -23473 -23497 -23509 -23531 -23537 -23539 -23549 -23557 -23561 -23563 -23567 -23581 -23593 -23599 -23603 -23609 -23623 -23627 -23629 -23633 -23663 -23669 -23671 -23677 -23687 -23689 -23719 -23741 -23743 -23747 -23753 -23761 -23767 -23773 -23789 -23801 -23813 -23819 -23827 -23831 -23833 -23857 -23869 -23873 -23879 -23887 -23893 -23899 -23909 -23911 -23917 -23929 -23957 -23971 -23977 -23981 -23993 -24001 -24007 -24019 -24023 -24029 -24043 -24049 -24061 -24071 -24077 -24083 -24091 -24097 -24103 -24107 -24109 -24113 -24121 -24133 -24137 -24151 -24169 -24179 -24181 -24197 -24203 -24223 -24229 -24239 -24247 -24251 -24281 -24317 -24329 -24337 -24359 -24371 -24373 -24379 -24391 -24407 -24413 -24419 -24421 -24439 -24443 -24469 -24473 -24481 -24499 -24509 -24517 -24527 -24533 -24547 -24551 -24571 -24593 -24611 -24623 -24631 -24659 -24671 -24677 -24683 -24691 -24697 -24709 -24733 -24749 -24763 -24767 -24781 -24793 -24799 -24809 -24821 -24841 -24847 -24851 -24859 -24877 -24889 -24907 -24917 -24919 -24923 -24943 -24953 -24967 -24971 -24977 -24979 -24989 -25013 -25031 -25033 -25037 -25057 -25073 -25087 -25097 -25111 -25117 -25121 -25127 -25147 -25153 -25163 -25169 -25171 -25183 -25189 -25219 -25229 -25237 -25243 -25247 -25253 -25261 -25301 -25303 -25307 -25309 -25321 -25339 -25343 -25349 -25357 -25367 -25373 -25391 -25409 -25411 -25423 -25439 -25447 -25453 -25457 -25463 -25469 -25471 -25523 -25537 -25541 -25561 -25577 -25579 -25583 -25589 -25601 -25603 -25609 -25621 -25633 -25639 -25643 -25657 -25667 -25673 -25679 -25693 -25703 -25717 -25733 -25741 -25747 -25759 -25763 -25771 -25793 -25799 -25801 -25819 -25841 -25847 -25849 -25867 -25873 -25889 -25903 -25913 -25919 -25931 -25933 -25939 -25943 -25951 -25969 -25981 -25997 -25999 -26003 -26017 -26021 -26029 -26041 -26053 -26083 -26099 -26107 -26111 -26113 -26119 -26141 -26153 -26161 -26171 -26177 -26183 -26189 -26203 -26209 -26227 -26237 -26249 -26251 -26261 -26263 -26267 -26293 -26297 -26309 -26317 -26321 -26339 -26347 -26357 -26371 -26387 -26393 -26399 -26407 -26417 -26423 -26431 -26437 -26449 -26459 -26479 -26489 -26497 -26501 -26513 -26539 -26557 -26561 -26573 -26591 -26597 -26627 -26633 -26641 -26647 -26669 -26681 -26683 -26687 -26693 -26699 -26701 -26711 -26713 -26717 -26723 -26729 -26731 -26737 -26759 -26777 -26783 -26801 -26813 -26821 -26833 -26839 -26849 -26861 -26863 -26879 -26881 -26891 -26893 -26903 -26921 -26927 -26947 -26951 -26953 -26959 -26981 -26987 -26993 -27011 -27017 -27031 -27043 -27059 -27061 -27067 -27073 -27077 -27091 -27103 -27107 -27109 -27127 -27143 -27179 -27191 -27197 -27211 -27239 -27241 -27253 -27259 -27271 -27277 -27281 -27283 -27299 -27329 -27337 -27361 -27367 -27397 -27407 -27409 -27427 -27431 -27437 -27449 -27457 -27479 -27481 -27487 -27509 -27527 -27529 -27539 -27541 -27551 -27581 -27583 -27611 -27617 -27631 -27647 -27653 -27673 -27689 -27691 -27697 -27701 -27733 -27737 -27739 -27743 -27749 -27751 -27763 -27767 -27773 -27779 -27791 -27793 -27799 -27803 -27809 -27817 -27823 -27827 -27847 -27851 -27883 -27893 -27901 -27917 -27919 -27941 -27943 -27947 -27953 -27961 -27967 -27983 -27997 -28001 -28019 -28027 -28031 -28051 -28057 -28069 -28081 -28087 -28097 -28099 -28109 -28111 -28123 -28151 -28163 -28181 -28183 -28201 -28211 -28219 -28229 -28277 -28279 -28283 -28289 -28297 -28307 -28309 -28319 -28349 -28351 -28387 -28393 -28403 -28409 -28411 -28429 -28433 -28439 -28447 -28463 -28477 -28493 -28499 -28513 -28517 -28537 -28541 -28547 -28549 -28559 -28571 -28573 -28579 -28591 -28597 -28603 -28607 -28619 -28621 -28627 -28631 -28643 -28649 -28657 -28661 -28663 -28669 -28687 -28697 -28703 -28711 -28723 -28729 -28751 -28753 -28759 -28771 -28789 -28793 -28807 -28813 -28817 -28837 -28843 -28859 -28867 -28871 -28879 -28901 -28909 -28921 -28927 -28933 -28949 -28961 -28979 -29009 -29017 -29021 -29023 -29027 -29033 -29059 -29063 -29077 -29101 -29123 -29129 -29131 -29137 -29147 -29153 -29167 -29173 -29179 -29191 -29201 -29207 -29209 -29221 -29231 -29243 -29251 -29269 -29287 -29297 -29303 -29311 -29327 -29333 -29339 -29347 -29363 -29383 -29387 -29389 -29399 -29401 -29411 -29423 -29429 -29437 -29443 -29453 -29473 -29483 -29501 -29527 -29531 -29537 -29567 -29569 -29573 -29581 -29587 -29599 -29611 -29629 -29633 -29641 -29663 -29669 -29671 -29683 -29717 -29723 -29741 -29753 -29759 -29761 -29789 -29803 -29819 -29833 -29837 -29851 -29863 -29867 -29873 -29879 -29881 -29917 -29921 -29927 -29947 -29959 -29983 -29989 -30011 -30013 -30029 -30047 -30059 -30071 -30089 -30091 -30097 -30103 -30109 -30113 -30119 -30133 -30137 -30139 -30161 -30169 -30181 -30187 -30197 -30203 -30211 -30223 -30241 -30253 -30259 -30269 -30271 -30293 -30307 -30313 -30319 -30323 -30341 -30347 -30367 -30389 -30391 -30403 -30427 -30431 -30449 -30467 -30469 -30491 -30493 -30497 -30509 -30517 -30529 -30539 -30553 -30557 -30559 -30577 -30593 -30631 -30637 -30643 -30649 -30661 -30671 -30677 -30689 -30697 -30703 -30707 -30713 -30727 -30757 -30763 -30773 -30781 -30803 -30809 -30817 -30829 -30839 -30841 -30851 -30853 -30859 -30869 -30871 -30881 -30893 -30911 -30931 -30937 -30941 -30949 -30971 -30977 -30983 -31013 -31019 -31033 -31039 -31051 -31063 -31069 -31079 -31081 -31091 -31121 -31123 -31139 -31147 -31151 -31153 -31159 -31177 -31181 -31183 -31189 -31193 -31219 -31223 -31231 -31237 -31247 -31249 -31253 -31259 -31267 -31271 -31277 -31307 -31319 -31321 -31327 -31333 -31337 -31357 -31379 -31387 -31391 -31393 -31397 -31469 -31477 -31481 -31489 -31511 -31513 -31517 -31531 -31541 -31543 -31547 -31567 -31573 -31583 -31601 -31607 -31627 -31643 -31649 -31657 -31663 -31667 -31687 -31699 -31721 -31723 -31727 -31729 -31741 -31751 -31769 -31771 -31793 -31799 -31817 -31847 -31849 -31859 -31873 -31883 -31891 -31907 -31957 -31963 -31973 -31981 -31991 -32003 -32009 -32027 -32029 -32051 -32057 -32059 -32063 -32069 -32077 -32083 -32089 -32099 -32117 -32119 -32141 -32143 -32159 -32173 -32183 -32189 -32191 -32203 -32213 -32233 -32237 -32251 -32257 -32261 -32297 -32299 -32303 -32309 -32321 -32323 -32327 -32341 -32353 -32359 -32363 -32369 -32371 -32377 -32381 -32401 -32411 -32413 -32423 -32429 -32441 -32443 -32467 -32479 -32491 -32497 -32503 -32507 -32531 -32533 -32537 -32561 -32563 -32569 -32573 -32579 -32587 -32603 -32609 -32611 -32621 -32633 -32647 -32653 -32687 -32693 -32707 -32713 -32717 -32719 -32749 -32771 -32779 -32783 -32789 -32797 -32801 -32803 -32831 -32833 -32839 -32843 -32869 -32887 -32909 -32911 -32917 -32933 -32939 -32941 -32957 -32969 -32971 -32983 -32987 -32993 -32999 -33013 -33023 -33029 -33037 -33049 -33053 -33071 -33073 -33083 -33091 -33107 -33113 -33119 -33149 -33151 -33161 -33179 -33181 -33191 -33199 -33203 -33211 -33223 -33247 -33287 -33289 -33301 -33311 -33317 -33329 -33331 -33343 -33347 -33349 -33353 -33359 -33377 -33391 -33403 -33409 -33413 -33427 -33457 -33461 -33469 -33479 -33487 -33493 -33503 -33521 -33529 -33533 -33547 -33563 -33569 -33577 -33581 -33587 -33589 -33599 -33601 -33613 -33617 -33619 -33623 -33629 -33637 -33641 -33647 -33679 -33703 -33713 -33721 -33739 -33749 -33751 -33757 -33767 -33769 -33773 -33791 -33797 -33809 -33811 -33827 -33829 -33851 -33857 -33863 -33871 -33889 -33893 -33911 -33923 -33931 -33937 -33941 -33961 -33967 -33997 -34019 -34031 -34033 -34039 -34057 -34061 -34123 -34127 -34129 -34141 -34147 -34157 -34159 -34171 -34183 -34211 -34213 -34217 -34231 -34253 -34259 -34261 -34267 -34273 -34283 -34297 -34301 -34303 -34313 -34319 -34327 -34337 -34351 -34361 -34367 -34369 -34381 -34403 -34421 -34429 -34439 -34457 -34469 -34471 -34483 -34487 -34499 -34501 -34511 -34513 -34519 -34537 -34543 -34549 -34583 -34589 -34591 -34603 -34607 -34613 -34631 -34649 -34651 -34667 -34673 -34679 -34687 -34693 -34703 -34721 -34729 -34739 -34747 -34757 -34759 -34763 -34781 -34807 -34819 -34841 -34843 -34847 -34849 -34871 -34877 -34883 -34897 -34913 -34919 -34939 -34949 -34961 -34963 -34981 -35023 -35027 -35051 -35053 -35059 -35069 -35081 -35083 -35089 -35099 -35107 -35111 -35117 -35129 -35141 -35149 -35153 -35159 -35171 -35201 -35221 -35227 -35251 -35257 -35267 -35279 -35281 -35291 -35311 -35317 -35323 -35327 -35339 -35353 -35363 -35381 -35393 -35401 -35407 -35419 -35423 -35437 -35447 -35449 -35461 -35491 -35507 -35509 -35521 -35527 -35531 -35533 -35537 -35543 -35569 -35573 -35591 -35593 -35597 -35603 -35617 -35671 -35677 -35729 -35731 -35747 -35753 -35759 -35771 -35797 -35801 -35803 -35809 -35831 -35837 -35839 -35851 -35863 -35869 -35879 -35897 -35899 -35911 -35923 -35933 -35951 -35963 -35969 -35977 -35983 -35993 -35999 -36007 -36011 -36013 -36017 -36037 -36061 -36067 -36073 -36083 -36097 -36107 -36109 -36131 -36137 -36151 -36161 -36187 -36191 -36209 -36217 -36229 -36241 -36251 -36263 -36269 -36277 -36293 -36299 -36307 -36313 -36319 -36341 -36343 -36353 -36373 -36383 -36389 -36433 -36451 -36457 -36467 -36469 -36473 -36479 -36493 -36497 -36523 -36527 -36529 -36541 -36551 -36559 -36563 -36571 -36583 -36587 -36599 -36607 -36629 -36637 -36643 -36653 -36671 -36677 -36683 -36691 -36697 -36709 -36713 -36721 -36739 -36749 -36761 -36767 -36779 -36781 -36787 -36791 -36793 -36809 -36821 -36833 -36847 -36857 -36871 -36877 -36887 -36899 -36901 -36913 -36919 -36923 -36929 -36931 -36943 -36947 -36973 -36979 -36997 -37003 -37013 -37019 -37021 -37039 -37049 -37057 -37061 -37087 -37097 -37117 -37123 -37139 -37159 -37171 -37181 -37189 -37199 -37201 -37217 -37223 -37243 -37253 -37273 -37277 -37307 -37309 -37313 -37321 -37337 -37339 -37357 -37361 -37363 -37369 -37379 -37397 -37409 -37423 -37441 -37447 -37463 -37483 -37489 -37493 -37501 -37507 -37511 -37517 -37529 -37537 -37547 -37549 -37561 -37567 -37571 -37573 -37579 -37589 -37591 -37607 -37619 -37633 -37643 -37649 -37657 -37663 -37691 -37693 -37699 -37717 -37747 -37781 -37783 -37799 -37811 -37813 -37831 -37847 -37853 -37861 -37871 -37879 -37889 -37897 -37907 -37951 -37957 -37963 -37967 -37987 -37991 -37993 -37997 -38011 -38039 -38047 -38053 -38069 -38083 -38113 -38119 -38149 -38153 -38167 -38177 -38183 -38189 -38197 -38201 -38219 -38231 -38237 -38239 -38261 -38273 -38281 -38287 -38299 -38303 -38317 -38321 -38327 -38329 -38333 -38351 -38371 -38377 -38393 -38431 -38447 -38449 -38453 -38459 -38461 -38501 -38543 -38557 -38561 -38567 -38569 -38593 -38603 -38609 -38611 -38629 -38639 -38651 -38653 -38669 -38671 -38677 -38693 -38699 -38707 -38711 -38713 -38723 -38729 -38737 -38747 -38749 -38767 -38783 -38791 -38803 -38821 -38833 -38839 -38851 -38861 -38867 -38873 -38891 -38903 -38917 -38921 -38923 -38933 -38953 -38959 -38971 -38977 -38993 -39019 -39023 -39041 -39043 -39047 -39079 -39089 -39097 -39103 -39107 -39113 -39119 -39133 -39139 -39157 -39161 -39163 -39181 -39191 -39199 -39209 -39217 -39227 -39229 -39233 -39239 -39241 -39251 -39293 -39301 -39313 -39317 -39323 -39341 -39343 -39359 -39367 -39371 -39373 -39383 -39397 -39409 -39419 -39439 -39443 -39451 -39461 -39499 -39503 -39509 -39511 -39521 -39541 -39551 -39563 -39569 -39581 -39607 -39619 -39623 -39631 -39659 -39667 -39671 -39679 -39703 -39709 -39719 -39727 -39733 -39749 -39761 -39769 -39779 -39791 -39799 -39821 -39827 -39829 -39839 -39841 -39847 -39857 -39863 -39869 -39877 -39883 -39887 -39901 -39929 -39937 -39953 -39971 -39979 -39983 -39989 -40009 -40013 -40031 -40037 -40039 -40063 -40087 -40093 -40099 -40111 -40123 -40127 -40129 -40151 -40153 -40163 -40169 -40177 -40189 -40193 -40213 -40231 -40237 -40241 -40253 -40277 -40283 -40289 -40343 -40351 -40357 -40361 -40387 -40423 -40427 -40429 -40433 -40459 -40471 -40483 -40487 -40493 -40499 -40507 -40519 -40529 -40531 -40543 -40559 -40577 -40583 -40591 -40597 -40609 -40627 -40637 -40639 -40693 -40697 -40699 -40709 -40739 -40751 -40759 -40763 -40771 -40787 -40801 -40813 -40819 -40823 -40829 -40841 -40847 -40849 -40853 -40867 -40879 -40883 -40897 -40903 -40927 -40933 -40939 -40949 -40961 -40973 -40993 -41011 -41017 -41023 -41039 -41047 -41051 -41057 -41077 -41081 -41113 -41117 -41131 -41141 -41143 -41149 -41161 -41177 -41179 -41183 -41189 -41201 -41203 -41213 -41221 -41227 -41231 -41233 -41243 -41257 -41263 -41269 -41281 -41299 -41333 -41341 -41351 -41357 -41381 -41387 -41389 -41399 -41411 -41413 -41443 -41453 -41467 -41479 -41491 -41507 -41513 -41519 -41521 -41539 -41543 -41549 -41579 -41593 -41597 -41603 -41609 -41611 -41617 -41621 -41627 -41641 -41647 -41651 -41659 -41669 -41681 -41687 -41719 -41729 -41737 -41759 -41761 -41771 -41777 -41801 -41809 -41813 -41843 -41849 -41851 -41863 -41879 -41887 -41893 -41897 -41903 -41911 -41927 -41941 -41947 -41953 -41957 -41959 -41969 -41981 -41983 -41999 -42013 -42017 -42019 -42023 -42043 -42061 -42071 -42073 -42083 -42089 -42101 -42131 -42139 -42157 -42169 -42179 -42181 -42187 -42193 -42197 -42209 -42221 -42223 -42227 -42239 -42257 -42281 -42283 -42293 -42299 -42307 -42323 -42331 -42337 -42349 -42359 -42373 -42379 -42391 -42397 -42403 -42407 -42409 -42433 -42437 -42443 -42451 -42457 -42461 -42463 -42467 -42473 -42487 -42491 -42499 -42509 -42533 -42557 -42569 -42571 -42577 -42589 -42611 -42641 -42643 -42649 -42667 -42677 -42683 -42689 -42697 -42701 -42703 -42709 -42719 -42727 -42737 -42743 -42751 -42767 -42773 -42787 -42793 -42797 -42821 -42829 -42839 -42841 -42853 -42859 -42863 -42899 -42901 -42923 -42929 -42937 -42943 -42953 -42961 -42967 -42979 -42989 -43003 -43013 -43019 -43037 -43049 -43051 -43063 -43067 -43093 -43103 -43117 -43133 -43151 -43159 -43177 -43189 -43201 -43207 -43223 -43237 -43261 -43271 -43283 -43291 -43313 -43319 -43321 -43331 -43391 -43397 -43399 -43403 -43411 -43427 -43441 -43451 -43457 -43481 -43487 -43499 -43517 -43541 -43543 -43573 -43577 -43579 -43591 -43597 -43607 -43609 -43613 -43627 -43633 -43649 -43651 -43661 -43669 -43691 -43711 -43717 -43721 -43753 -43759 -43777 -43781 -43783 -43787 -43789 -43793 -43801 -43853 -43867 -43889 -43891 -43913 -43933 -43943 -43951 -43961 -43963 -43969 -43973 -43987 -43991 -43997 -44017 -44021 -44027 -44029 -44041 -44053 -44059 -44071 -44087 -44089 -44101 -44111 -44119 -44123 -44129 -44131 -44159 -44171 -44179 -44189 -44201 -44203 -44207 -44221 -44249 -44257 -44263 -44267 -44269 -44273 -44279 -44281 -44293 -44351 -44357 -44371 -44381 -44383 -44389 -44417 -44449 -44453 -44483 -44491 -44497 -44501 -44507 -44519 -44531 -44533 -44537 -44543 -44549 -44563 -44579 -44587 -44617 -44621 -44623 -44633 -44641 -44647 -44651 -44657 -44683 -44687 -44699 -44701 -44711 -44729 -44741 -44753 -44771 -44773 -44777 -44789 -44797 -44809 -44819 -44839 -44843 -44851 -44867 -44879 -44887 -44893 -44909 -44917 -44927 -44939 -44953 -44959 -44963 -44971 -44983 -44987 -45007 -45013 -45053 -45061 -45077 -45083 -45119 -45121 -45127 -45131 -45137 -45139 -45161 -45179 -45181 -45191 -45197 -45233 -45247 -45259 -45263 -45281 -45289 -45293 -45307 -45317 -45319 -45329 -45337 -45341 -45343 -45361 -45377 -45389 -45403 -45413 -45427 -45433 -45439 -45481 -45491 -45497 -45503 -45523 -45533 -45541 -45553 -45557 -45569 -45587 -45589 -45599 -45613 -45631 -45641 -45659 -45667 -45673 -45677 -45691 -45697 -45707 -45737 -45751 -45757 -45763 -45767 -45779 -45817 -45821 -45823 -45827 -45833 -45841 -45853 -45863 -45869 -45887 -45893 -45943 -45949 -45953 -45959 -45971 -45979 -45989 -46021 -46027 -46049 -46051 -46061 -46073 -46091 -46093 -46099 -46103 -46133 -46141 -46147 -46153 -46171 -46181 -46183 -46187 -46199 -46219 -46229 -46237 -46261 -46271 -46273 -46279 -46301 -46307 -46309 -46327 -46337 -46349 -46351 -46381 -46399 -46411 -46439 -46441 -46447 -46451 -46457 -46471 -46477 -46489 -46499 -46507 -46511 -46523 -46549 -46559 -46567 -46573 -46589 -46591 -46601 -46619 -46633 -46639 -46643 -46649 -46663 -46679 -46681 -46687 -46691 -46703 -46723 -46727 -46747 -46751 -46757 -46769 -46771 -46807 -46811 -46817 -46819 -46829 -46831 -46853 -46861 -46867 -46877 -46889 -46901 -46919 -46933 -46957 -46993 -46997 -47017 -47041 -47051 -47057 -47059 -47087 -47093 -47111 -47119 -47123 -47129 -47137 -47143 -47147 -47149 -47161 -47189 -47207 -47221 -47237 -47251 -47269 -47279 -47287 -47293 -47297 -47303 -47309 -47317 -47339 -47351 -47353 -47363 -47381 -47387 -47389 -47407 -47417 -47419 -47431 -47441 -47459 -47491 -47497 -47501 -47507 -47513 -47521 -47527 -47533 -47543 -47563 -47569 -47581 -47591 -47599 -47609 -47623 -47629 -47639 -47653 -47657 -47659 -47681 -47699 -47701 -47711 -47713 -47717 -47737 -47741 -47743 -47777 -47779 -47791 -47797 -47807 -47809 -47819 -47837 -47843 -47857 -47869 -47881 -47903 -47911 -47917 -47933 -47939 -47947 -47951 -47963 -47969 -47977 -47981 -48017 -48023 -48029 -48049 -48073 -48079 -48091 -48109 -48119 -48121 -48131 -48157 -48163 -48179 -48187 -48193 -48197 -48221 -48239 -48247 -48259 -48271 -48281 -48299 -48311 -48313 -48337 -48341 -48353 -48371 -48383 -48397 -48407 -48409 -48413 -48437 -48449 -48463 -48473 -48479 -48481 -48487 -48491 -48497 -48523 -48527 -48533 -48539 -48541 -48563 -48571 -48589 -48593 -48611 -48619 -48623 -48647 -48649 -48661 -48673 -48677 -48679 -48731 -48733 -48751 -48757 -48761 -48767 -48779 -48781 -48787 -48799 -48809 -48817 -48821 -48823 -48847 -48857 -48859 -48869 -48871 -48883 -48889 -48907 -48947 -48953 -48973 -48989 -48991 -49003 -49009 -49019 -49031 -49033 -49037 -49043 -49057 -49069 -49081 -49103 -49109 -49117 -49121 -49123 -49139 -49157 -49169 -49171 -49177 -49193 -49199 -49201 -49207 -49211 -49223 -49253 -49261 -49277 -49279 -49297 -49307 -49331 -49333 -49339 -49363 -49367 -49369 -49391 -49393 -49409 -49411 -49417 -49429 -49433 -49451 -49459 -49463 -49477 -49481 -49499 -49523 -49529 -49531 -49537 -49547 -49549 -49559 -49597 -49603 -49613 -49627 -49633 -49639 -49663 -49667 -49669 -49681 -49697 -49711 -49727 -49739 -49741 -49747 -49757 -49783 -49787 -49789 -49801 -49807 -49811 -49823 -49831 -49843 -49853 -49871 -49877 -49891 -49919 -49921 -49927 -49937 -49939 -49943 -49957 -49991 -49993 -49999 -50021 -50023 -50033 -50047 -50051 -50053 -50069 -50077 -50087 -50093 -50101 -50111 -50119 -50123 -50129 -50131 -50147 -50153 -50159 -50177 -50207 -50221 -50227 -50231 -50261 -50263 -50273 -50287 -50291 -50311 -50321 -50329 -50333 -50341 -50359 -50363 -50377 -50383 -50387 -50411 -50417 -50423 -50441 -50459 -50461 -50497 -50503 -50513 -50527 -50539 -50543 -50549 -50551 -50581 -50587 -50591 -50593 -50599 -50627 -50647 -50651 -50671 -50683 -50707 -50723 -50741 -50753 -50767 -50773 -50777 -50789 -50821 -50833 -50839 -50849 -50857 -50867 -50873 -50891 -50893 -50909 -50923 -50929 -50951 -50957 -50969 -50971 -50989 -50993 -51001 -51031 -51043 -51047 -51059 -51061 -51071 -51109 -51131 -51133 -51137 -51151 -51157 -51169 -51193 -51197 -51199 -51203 -51217 -51229 -51239 -51241 -51257 -51263 -51283 -51287 -51307 -51329 -51341 -51343 -51347 -51349 -51361 -51383 -51407 -51413 -51419 -51421 -51427 -51431 -51437 -51439 -51449 -51461 -51473 -51479 -51481 -51487 -51503 -51511 -51517 -51521 -51539 -51551 -51563 -51577 -51581 -51593 -51599 -51607 -51613 -51631 -51637 -51647 -51659 -51673 -51679 -51683 -51691 -51713 -51719 -51721 -51749 -51767 -51769 -51787 -51797 -51803 -51817 -51827 -51829 -51839 -51853 -51859 -51869 -51871 -51893 -51899 -51907 -51913 -51929 -51941 -51949 -51971 -51973 -51977 -51991 -52009 -52021 -52027 -52051 -52057 -52067 -52069 -52081 -52103 -52121 -52127 -52147 -52153 -52163 -52177 -52181 -52183 -52189 -52201 -52223 -52237 -52249 -52253 -52259 -52267 -52289 -52291 -52301 -52313 -52321 -52361 -52363 -52369 -52379 -52387 -52391 -52433 -52453 -52457 -52489 -52501 -52511 -52517 -52529 -52541 -52543 -52553 -52561 -52567 -52571 -52579 -52583 -52609 -52627 -52631 -52639 -52667 -52673 -52691 -52697 -52709 -52711 -52721 -52727 -52733 -52747 -52757 -52769 -52783 -52807 -52813 -52817 -52837 -52859 -52861 -52879 -52883 -52889 -52901 -52903 -52919 -52937 -52951 -52957 -52963 -52967 -52973 -52981 -52999 -53003 -53017 -53047 -53051 -53069 -53077 -53087 -53089 -53093 -53101 -53113 -53117 -53129 -53147 -53149 -53161 -53171 -53173 -53189 -53197 -53201 -53231 -53233 -53239 -53267 -53269 -53279 -53281 -53299 -53309 -53323 -53327 -53353 -53359 -53377 -53381 -53401 -53407 -53411 -53419 -53437 -53441 -53453 -53479 -53503 -53507 -53527 -53549 -53551 -53569 -53591 -53593 -53597 -53609 -53611 -53617 -53623 -53629 -53633 -53639 -53653 -53657 -53681 -53693 -53699 -53717 -53719 -53731 -53759 -53773 -53777 -53783 -53791 -53813 -53819 -53831 -53849 -53857 -53861 -53881 -53887 -53891 -53897 -53899 -53917 -53923 -53927 -53939 -53951 -53959 -53987 -53993 -54001 -54011 -54013 -54037 -54049 -54059 -54083 -54091 -54101 -54121 -54133 -54139 -54151 -54163 -54167 -54181 -54193 -54217 -54251 -54269 -54277 -54287 -54293 -54311 -54319 -54323 -54331 -54347 -54361 -54367 -54371 -54377 -54401 -54403 -54409 -54413 -54419 -54421 -54437 -54443 -54449 -54469 -54493 -54497 -54499 -54503 -54517 -54521 -54539 -54541 -54547 -54559 -54563 -54577 -54581 -54583 -54601 -54617 -54623 -54629 -54631 -54647 -54667 -54673 -54679 -54709 -54713 -54721 -54727 -54751 -54767 -54773 -54779 -54787 -54799 -54829 -54833 -54851 -54869 -54877 -54881 -54907 -54917 -54919 -54941 -54949 -54959 -54973 -54979 -54983 -55001 -55009 -55021 -55049 -55051 -55057 -55061 -55073 -55079 -55103 -55109 -55117 -55127 -55147 -55163 -55171 -55201 -55207 -55213 -55217 -55219 -55229 -55243 -55249 -55259 -55291 -55313 -55331 -55333 -55337 -55339 -55343 -55351 -55373 -55381 -55399 -55411 -55439 -55441 -55457 -55469 -55487 -55501 -55511 -55529 -55541 -55547 -55579 -55589 -55603 -55609 -55619 -55621 -55631 -55633 -55639 -55661 -55663 -55667 -55673 -55681 -55691 -55697 -55711 -55717 -55721 -55733 -55763 -55787 -55793 -55799 -55807 -55813 -55817 -55819 -55823 -55829 -55837 -55843 -55849 -55871 -55889 -55897 -55901 -55903 -55921 -55927 -55931 -55933 -55949 -55967 -55987 -55997 -56003 -56009 -56039 -56041 -56053 -56081 -56087 -56093 -56099 -56101 -56113 -56123 -56131 -56149 -56167 -56171 -56179 -56197 -56207 -56209 -56237 -56239 -56249 -56263 -56267 -56269 -56299 -56311 -56333 -56359 -56369 -56377 -56383 -56393 -56401 -56417 -56431 -56437 -56443 -56453 -56467 -56473 -56477 -56479 -56489 -56501 -56503 -56509 -56519 -56527 -56531 -56533 -56543 -56569 -56591 -56597 -56599 -56611 -56629 -56633 -56659 -56663 -56671 -56681 -56687 -56701 -56711 -56713 -56731 -56737 -56747 -56767 -56773 -56779 -56783 -56807 -56809 -56813 -56821 -56827 -56843 -56857 -56873 -56891 -56893 -56897 -56909 -56911 -56921 -56923 -56929 -56941 -56951 -56957 -56963 -56983 -56989 -56993 -56999 -57037 -57041 -57047 -57059 -57073 -57077 -57089 -57097 -57107 -57119 -57131 -57139 -57143 -57149 -57163 -57173 -57179 -57191 -57193 -57203 -57221 -57223 -57241 -57251 -57259 -57269 -57271 -57283 -57287 -57301 -57329 -57331 -57347 -57349 -57367 -57373 -57383 -57389 -57397 -57413 -57427 -57457 -57467 -57487 -57493 -57503 -57527 -57529 -57557 -57559 -57571 -57587 -57593 -57601 -57637 -57641 -57649 -57653 -57667 -57679 -57689 -57697 -57709 -57713 -57719 -57727 -57731 -57737 -57751 -57773 -57781 -57787 -57791 -57793 -57803 -57809 -57829 -57839 -57847 -57853 -57859 -57881 -57899 -57901 -57917 -57923 -57943 -57947 -57973 -57977 -57991 -58013 -58027 -58031 -58043 -58049 -58057 -58061 -58067 -58073 -58099 -58109 -58111 -58129 -58147 -58151 -58153 -58169 -58171 -58189 -58193 -58199 -58207 -58211 -58217 -58229 -58231 -58237 -58243 -58271 -58309 -58313 -58321 -58337 -58363 -58367 -58369 -58379 -58391 -58393 -58403 -58411 -58417 -58427 -58439 -58441 -58451 -58453 -58477 -58481 -58511 -58537 -58543 -58549 -58567 -58573 -58579 -58601 -58603 -58613 -58631 -58657 -58661 -58679 -58687 -58693 -58699 -58711 -58727 -58733 -58741 -58757 -58763 -58771 -58787 -58789 -58831 -58889 -58897 -58901 -58907 -58909 -58913 -58921 -58937 -58943 -58963 -58967 -58979 -58991 -58997 -59009 -59011 -59021 -59023 -59029 -59051 -59053 -59063 -59069 -59077 -59083 -59093 -59107 -59113 -59119 -59123 -59141 -59149 -59159 -59167 -59183 -59197 -59207 -59209 -59219 -59221 -59233 -59239 -59243 -59263 -59273 -59281 -59333 -59341 -59351 -59357 -59359 -59369 -59377 -59387 -59393 -59399 -59407 -59417 -59419 -59441 -59443 -59447 -59453 -59467 -59471 -59473 -59497 -59509 -59513 -59539 -59557 -59561 -59567 -59581 -59611 -59617 -59621 -59627 -59629 -59651 -59659 -59663 -59669 -59671 -59693 -59699 -59707 -59723 -59729 -59743 -59747 -59753 -59771 -59779 -59791 -59797 -59809 -59833 -59863 -59879 -59887 -59921 -59929 -59951 -59957 -59971 -59981 -59999 -60013 -60017 -60029 -60037 -60041 -60077 -60083 -60089 -60091 -60101 -60103 -60107 -60127 -60133 -60139 -60149 -60161 -60167 -60169 -60209 -60217 -60223 -60251 -60257 -60259 -60271 -60289 -60293 -60317 -60331 -60337 -60343 -60353 -60373 -60383 -60397 -60413 -60427 -60443 -60449 -60457 -60493 -60497 -60509 -60521 -60527 -60539 -60589 -60601 -60607 -60611 -60617 -60623 -60631 -60637 -60647 -60649 -60659 -60661 -60679 -60689 -60703 -60719 -60727 -60733 -60737 -60757 -60761 -60763 -60773 -60779 -60793 -60811 -60821 -60859 -60869 -60887 -60889 -60899 -60901 -60913 -60917 -60919 -60923 -60937 -60943 -60953 -60961 -61001 -61007 -61027 -61031 -61043 -61051 -61057 -61091 -61099 -61121 -61129 -61141 -61151 -61153 -61169 -61211 -61223 -61231 -61253 -61261 -61283 -61291 -61297 -61331 -61333 -61339 -61343 -61357 -61363 -61379 -61381 -61403 -61409 -61417 -61441 -61463 -61469 -61471 -61483 -61487 -61493 -61507 -61511 -61519 -61543 -61547 -61553 -61559 -61561 -61583 -61603 -61609 -61613 -61627 -61631 -61637 -61643 -61651 -61657 -61667 -61673 -61681 -61687 -61703 -61717 -61723 -61729 -61751 -61757 -61781 -61813 -61819 -61837 -61843 -61861 -61871 -61879 -61909 -61927 -61933 -61949 -61961 -61967 -61979 -61981 -61987 -61991 -62003 -62011 -62017 -62039 -62047 -62053 -62057 -62071 -62081 -62099 -62119 -62129 -62131 -62137 -62141 -62143 -62171 -62189 -62191 -62201 -62207 -62213 -62219 -62233 -62273 -62297 -62299 -62303 -62311 -62323 -62327 -62347 -62351 -62383 -62401 -62417 -62423 -62459 -62467 -62473 -62477 -62483 -62497 -62501 -62507 -62533 -62539 -62549 -62563 -62581 -62591 -62597 -62603 -62617 -62627 -62633 -62639 -62653 -62659 -62683 -62687 -62701 -62723 -62731 -62743 -62753 -62761 -62773 -62791 -62801 -62819 -62827 -62851 -62861 -62869 -62873 -62897 -62903 -62921 -62927 -62929 -62939 -62969 -62971 -62981 -62983 -62987 -62989 -63029 -63031 -63059 -63067 -63073 -63079 -63097 -63103 -63113 -63127 -63131 -63149 -63179 -63197 -63199 -63211 -63241 -63247 -63277 -63281 -63299 -63311 -63313 -63317 -63331 -63337 -63347 -63353 -63361 -63367 -63377 -63389 -63391 -63397 -63409 -63419 -63421 -63439 -63443 -63463 -63467 -63473 -63487 -63493 -63499 -63521 -63527 -63533 -63541 -63559 -63577 -63587 -63589 -63599 -63601 -63607 -63611 -63617 -63629 -63647 -63649 -63659 -63667 -63671 -63689 -63691 -63697 -63703 -63709 -63719 -63727 -63737 -63743 -63761 -63773 -63781 -63793 -63799 -63803 -63809 -63823 -63839 -63841 -63853 -63857 -63863 -63901 -63907 -63913 -63929 -63949 -63977 -63997 -64007 -64013 -64019 -64033 -64037 -64063 -64067 -64081 -64091 -64109 -64123 -64151 -64153 -64157 -64171 -64187 -64189 -64217 -64223 -64231 -64237 -64271 -64279 -64283 -64301 -64303 -64319 -64327 -64333 -64373 -64381 -64399 -64403 -64433 -64439 -64451 -64453 -64483 -64489 -64499 -64513 -64553 -64567 -64577 -64579 -64591 -64601 -64609 -64613 -64621 -64627 -64633 -64661 -64663 -64667 -64679 -64693 -64709 -64717 -64747 -64763 -64781 -64783 -64793 -64811 -64817 -64849 -64853 -64871 -64877 -64879 -64891 -64901 -64919 -64921 -64927 -64937 -64951 -64969 -64997 -65003 -65011 -65027 -65029 -65033 -65053 -65063 -65071 -65089 -65099 -65101 -65111 -65119 -65123 -65129 -65141 -65147 -65167 -65171 -65173 -65179 -65183 -65203 -65213 -65239 -65257 -65267 -65269 -65287 -65293 -65309 -65323 -65327 -65353 -65357 -65371 -65381 -65393 -65407 -65413 -65419 -65423 -65437 -65447 -65449 -65479 -65497 -65519 -65521 diff --git a/security/nss/lib/freebl/mpi/doc/prng.pod b/security/nss/lib/freebl/mpi/doc/prng.pod deleted file mode 100644 index 1ae75da82..000000000 --- a/security/nss/lib/freebl/mpi/doc/prng.pod +++ /dev/null @@ -1,41 +0,0 @@ -=head1 NAME - - prng - pseudo-random number generator - -=head1 SYNOPSIS - - prng [count] - -=head1 DESCRIPTION - -B<Prng> generates 32-bit pseudo-random integers using the -Blum-Blum-Shub (BBS) quadratic residue generator. It is seeded using -the standard C library's rand() function, which itself seeded from the -system clock and the process ID number. Thus, the values generated -are not particularly useful for cryptographic applications, but they -are in general much better than the typical output of the usual -multiplicative congruency generator used by most runtime libraries. - -You may optionally specify how many random values should be generated -by giving a I<count> argument on the command line. If you do not -specify a count, only one random value will be generated. The results -are output to the standard output in decimal notation, one value per -line. - -=head1 RESTRICTIONS - -As stated above, B<prng> uses the C library's rand() function to seed -the generator, so it is not terribly suitable for cryptographic -applications. Also note that each time you run the program, a new -seed is generated, so it is better to run it once with a I<count> -parameter than it is to run it multiple times to generate several -values. - -=head1 AUTHOR - - Michael J. Fromberger <sting@linguist.dartmouth.edu> - Copyright (C) 1998 Michael J. Fromberger, All Rights Reserved - Thayer School of Engineering, Dartmouth College, Hanover, NH USA - - $Date$ - diff --git a/security/nss/lib/freebl/mpi/doc/redux.txt b/security/nss/lib/freebl/mpi/doc/redux.txt deleted file mode 100644 index d6eb7844f..000000000 --- a/security/nss/lib/freebl/mpi/doc/redux.txt +++ /dev/null @@ -1,121 +0,0 @@ -Modular Reduction - -Usually, modular reduction is accomplished by long division, using the -mp_div() or mp_mod() functions. However, when performing modular -exponentiation, you spend a lot of time reducing by the same modulus -again and again. For this purpose, doing a full division for each -multiplication is quite inefficient. - -For this reason, the mp_exptmod() function does not perform modular -reductions in the usual way, but instead takes advantage of an -algorithm due to Barrett, as described by Menezes, Oorschot and -VanStone in their book _Handbook of Applied Cryptography_, published -by the CRC Press (see Chapter 14 for details). This method reduces -most of the computation of reduction to efficient shifting and masking -operations, and avoids the multiple-precision division entirely. - -Here is a brief synopsis of Barrett reduction, as it is implemented in -this library. - -Let b denote the radix of the computation (one more than the maximum -value that can be denoted by an mp_digit). Let m be the modulus, and -let k be the number of significant digits of m. Let x be the value to -be reduced modulo m. By the Division Theorem, there exist unique -integers Q and R such that: - - x = Qm + R, 0 <= R < m - -Barrett reduction takes advantage of the fact that you can easily -approximate Q to within two, given a value M such that: - - 2k - b - M = floor( ----- ) - m - -Computation of M requires a full-precision division step, so if you -are only doing a single reduction by m, you gain no advantage. -However, when multiple reductions by the same m are required, this -division need only be done once, beforehand. Using this, we can use -the following equation to compute Q', an approximation of Q: - - x - floor( ------ ) M - k-1 - b -Q' = floor( ----------------- ) - k+1 - b - -The divisions by b^(k-1) and b^(k+1) and the floor() functions can be -efficiently implemented with shifts and masks, leaving only a single -multiplication to be performed to get this approximation. It can be -shown that Q - 2 <= Q' <= Q, so in the worst case, we can get out with -two additional subtractions to bring the value into line with the -actual value of Q. - -Once we've got Q', we basically multiply that by m and subtract from -x, yielding: - - x - Q'm = Qm + R - Q'm - -Since we know the constraint on Q', this is one of: - - R - m + R - 2m + R - -Since R < m by the Division Theorem, we can simply subtract off m -until we get a value in the correct range, which will happen with no -more than 2 subtractions: - - v = x - Q'm - - while(v >= m) - v = v - m - endwhile - - -In random performance trials, modular exponentiation using this method -of reduction gave around a 40% speedup over using the division for -reduction. - ------------------------------------------------------------------- -***** 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$ diff --git a/security/nss/lib/freebl/mpi/doc/sqrt.txt b/security/nss/lib/freebl/mpi/doc/sqrt.txt deleted file mode 100644 index c709217a5..000000000 --- a/security/nss/lib/freebl/mpi/doc/sqrt.txt +++ /dev/null @@ -1,87 +0,0 @@ -Square Root - -A simple iterative algorithm is used to compute the greatest integer -less than or equal to the square root. Essentially, this is Newton's -linear approximation, computed by finding successive values of the -equation: - - x[k]^2 - V -x[k+1] = x[k] - ------------ - 2 x[k] - -...where V is the value for which the square root is being sought. In -essence, what is happening here is that we guess a value for the -square root, then figure out how far off we were by squaring our guess -and subtracting the target. Using this value, we compute a linear -approximation for the error, and adjust the "guess". We keep doing -this until the precision gets low enough that the above equation -yields a quotient of zero. At this point, our last guess is one -greater than the square root we're seeking. - -The initial guess is computed by dividing V by 4, which is a heuristic -I have found to be fairly good on average. This also has the -advantage of being very easy to compute efficiently, even for large -values. - -So, the resulting algorithm works as follows: - - x = V / 4 /* compute initial guess */ - - loop - t = (x * x) - V /* Compute absolute error */ - u = 2 * x /* Adjust by tangent slope */ - t = t / u - - /* Loop is done if error is zero */ - if(t == 0) - break - - /* Adjust guess by error term */ - x = x - t - end - - x = x - 1 - -The result of the computation is the value of x. - ------------------------------------------------------------------- -***** 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$ - - 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$ - - diff --git a/security/nss/lib/freebl/mpi/doc/timing.txt b/security/nss/lib/freebl/mpi/doc/timing.txt deleted file mode 100644 index 4c77da79f..000000000 --- a/security/nss/lib/freebl/mpi/doc/timing.txt +++ /dev/null @@ -1,250 +0,0 @@ -MPI Library Timing Tests - -Hardware/OS -(A) SGI O2 1 x MIPS R10000 250MHz IRIX 6.5.3 -(B) IBM RS/6000 43P-240 1 x PowerPC 603e 223MHz AIX 4.3 -(C) Dell GX1/L+ 1 x Pentium III 550MHz Linux 2.2.12-20 -(D) PowerBook G3 1 x PowerPC 750 266MHz LinuxPPC 2.2.6-15apmac -(E) PowerBook G3 1 x PowerPC 750 266MHz MacOS 8.5.1 -(F) PowerBook G3 1 x PowerPC 750 400MHz MacOS 9.0.2 - -Compiler -(1) MIPSpro C 7.2.1 -O3 optimizations -(2) GCC 2.95.1 -O3 optimizations -(3) IBM AIX xlc -O3 optimizations (version unknown) -(4) EGCS 2.91.66 -O3 optimizations -(5) Metrowerks CodeWarrior 5.0 C, all optimizations -(6) MIPSpro C 7.30 -O3 optimizations -(7) same as (6), with optimized libmalloc.so - -Timings are given in seconds, computed using the C library's clock() -function. The first column gives the hardware and compiler -configuration used for the test. The second column indicates the -number of tests that were aggregated to get the statistics for that -size. These were compiled using 16 bit digits. - -Source data were generated randomly using a fixed seed, so they should -be internally consistent, but may vary on different systems depending -on the C library. Also, since the resolution of the timer accessed by -clock() varies, there may be some variance in the precision of these -measurements. - -Prime Generation (primegen) - -128 bits: -A1 200 min=0.03, avg=0.19, max=0.72, sum=38.46 -A2 200 min=0.02, avg=0.16, max=0.62, sum=32.55 -B3 200 min=0.01, avg=0.07, max=0.22, sum=13.29 -C4 200 min=0.00, avg=0.03, max=0.20, sum=6.14 -D4 200 min=0.00, avg=0.05, max=0.33, sum=9.70 -A6 200 min=0.01, avg=0.09, max=0.36, sum=17.48 -A7 200 min=0.00, avg=0.05, max=0.24, sum=10.07 - -192 bits: -A1 200 min=0.05, avg=0.45, max=3.13, sum=89.96 -A2 200 min=0.04, avg=0.39, max=2.61, sum=77.55 -B3 200 min=0.02, avg=0.18, max=1.25, sum=36.97 -C4 200 min=0.01, avg=0.09, max=0.33, sum=18.24 -D4 200 min=0.02, avg=0.15, max=0.54, sum=29.63 -A6 200 min=0.02, avg=0.24, max=1.70, sum=47.84 -A7 200 min=0.01, avg=0.15, max=1.05, sum=30.88 - -256 bits: -A1 200 min=0.08, avg=0.92, max=6.13, sum=184.79 -A2 200 min=0.06, avg=0.76, max=5.03, sum=151.11 -B3 200 min=0.04, avg=0.41, max=2.68, sum=82.35 -C4 200 min=0.02, avg=0.19, max=0.69, sum=37.91 -D4 200 min=0.03, avg=0.31, max=1.15, sum=63.00 -A6 200 min=0.04, avg=0.48, max=3.13, sum=95.46 -A7 200 min=0.03, avg=0.37, max=2.36, sum=73.60 - -320 bits: -A1 200 min=0.11, avg=1.59, max=6.14, sum=318.81 -A2 200 min=0.09, avg=1.27, max=4.93, sum=254.03 -B3 200 min=0.07, avg=0.82, max=3.13, sum=163.80 -C4 200 min=0.04, avg=0.44, max=1.91, sum=87.59 -D4 200 min=0.06, avg=0.73, max=3.22, sum=146.73 -A6 200 min=0.07, avg=0.93, max=3.50, sum=185.01 -A7 200 min=0.05, avg=0.76, max=2.94, sum=151.78 - -384 bits: -A1 200 min=0.16, avg=2.69, max=11.41, sum=537.89 -A2 200 min=0.13, avg=2.15, max=9.03, sum=429.14 -B3 200 min=0.11, avg=1.54, max=6.49, sum=307.78 -C4 200 min=0.06, avg=0.81, max=4.84, sum=161.13 -D4 200 min=0.10, avg=1.38, max=8.31, sum=276.81 -A6 200 min=0.11, avg=1.73, max=7.36, sum=345.55 -A7 200 min=0.09, avg=1.46, max=6.12, sum=292.02 - -448 bits: -A1 200 min=0.23, avg=3.36, max=15.92, sum=672.63 -A2 200 min=0.17, avg=2.61, max=12.25, sum=522.86 -B3 200 min=0.16, avg=2.10, max=9.83, sum=420.86 -C4 200 min=0.09, avg=1.44, max=7.64, sum=288.36 -D4 200 min=0.16, avg=2.50, max=13.29, sum=500.17 -A6 200 min=0.15, avg=2.31, max=10.81, sum=461.58 -A7 200 min=0.14, avg=2.03, max=9.53, sum=405.16 - -512 bits: -A1 200 min=0.30, avg=6.12, max=22.18, sum=1223.35 -A2 200 min=0.25, avg=4.67, max=16.90, sum=933.18 -B3 200 min=0.23, avg=4.13, max=14.94, sum=825.45 -C4 200 min=0.13, avg=2.08, max=9.75, sum=415.22 -D4 200 min=0.24, avg=4.04, max=20.18, sum=808.11 -A6 200 min=0.22, avg=4.47, max=16.19, sum=893.83 -A7 200 min=0.20, avg=4.03, max=14.65, sum=806.02 - -Modular Exponentation (metime) - -The following results are aggregated from 200 pseudo-randomly -generated tests, based on a fixed seed. - - base, exponent, and modulus size (bits) -P/C 128 192 256 320 384 448 512 640 768 896 1024 -------- ----------------------------------------------------------------- -A1 0.015 0.027 0.047 0.069 0.098 0.133 0.176 0.294 0.458 0.680 1.040 -A2 0.013 0.024 0.037 0.053 0.077 0.102 0.133 0.214 0.326 0.476 0.668 -B3 0.005 0.011 0.021 0.036 0.056 0.084 0.121 0.222 0.370 0.573 0.840 -C4 0.002 0.006 0.011 0.020 0.032 0.048 0.069 0.129 0.223 0.344 0.507 -D4 0.004 0.010 0.019 0.034 0.056 0.085 0.123 0.232 0.390 0.609 0.899 -E5 0.007 0.015 0.031 0.055 0.088 0.133 0.183 0.342 0.574 0.893 1.317 -A6 0.008 0.016 0.038 0.042 0.064 0.093 0.133 0.239 0.393 0.604 0.880 -A7 0.005 0.011 0.020 0.036 0.056 0.083 0.121 0.223 0.374 0.583 0.855 - -Multiplication and Squaring tests, (mulsqr) - -The following results are aggregated from 500000 pseudo-randomly -generated tests, based on a per-run wall-clock seed. Times are given -in seconds, except where indicated in microseconds (us). - -(A1) - -bits multiply square ad percent time/mult time/square -64 9.33 9.15 > 1.9 18.7us 18.3us -128 10.88 10.44 > 4.0 21.8us 20.9us -192 13.30 11.89 > 10.6 26.7us 23.8us -256 14.88 12.64 > 15.1 29.8us 25.3us -320 18.64 15.01 > 19.5 37.3us 30.0us -384 23.11 17.70 > 23.4 46.2us 35.4us -448 28.28 20.88 > 26.2 56.6us 41.8us -512 34.09 24.51 > 28.1 68.2us 49.0us -640 47.86 33.25 > 30.5 95.7us 66.5us -768 64.91 43.54 > 32.9 129.8us 87.1us -896 84.49 55.48 > 34.3 169.0us 111.0us -1024 107.25 69.21 > 35.5 214.5us 138.4us -1536 227.97 141.91 > 37.8 456.0us 283.8us -2048 394.05 242.15 > 38.5 788.1us 484.3us - -(A2) - -bits multiply square ad percent time/mult time/square -64 7.87 7.95 < 1.0 15.7us 15.9us -128 9.40 9.19 > 2.2 18.8us 18.4us -192 11.15 10.59 > 5.0 22.3us 21.2us -256 12.02 11.16 > 7.2 24.0us 22.3us -320 14.62 13.43 > 8.1 29.2us 26.9us -384 17.72 15.80 > 10.8 35.4us 31.6us -448 21.24 18.51 > 12.9 42.5us 37.0us -512 25.36 21.78 > 14.1 50.7us 43.6us -640 34.57 29.00 > 16.1 69.1us 58.0us -768 46.10 37.60 > 18.4 92.2us 75.2us -896 58.94 47.72 > 19.0 117.9us 95.4us -1024 73.76 59.12 > 19.8 147.5us 118.2us -1536 152.00 118.80 > 21.8 304.0us 237.6us -2048 259.41 199.57 > 23.1 518.8us 399.1us - -(B3) - -bits multiply square ad percent time/mult time/square -64 2.60 2.47 > 5.0 5.20us 4.94us -128 4.43 4.06 > 8.4 8.86us 8.12us -192 7.03 6.10 > 13.2 14.1us 12.2us -256 10.44 8.59 > 17.7 20.9us 17.2us -320 14.44 11.64 > 19.4 28.9us 23.3us -384 19.12 15.08 > 21.1 38.2us 30.2us -448 24.55 19.09 > 22.2 49.1us 38.2us -512 31.03 23.53 > 24.2 62.1us 47.1us -640 45.05 33.80 > 25.0 90.1us 67.6us -768 63.02 46.05 > 26.9 126.0us 92.1us -896 83.74 60.29 > 28.0 167.5us 120.6us -1024 106.73 76.65 > 28.2 213.5us 153.3us -1536 228.94 160.98 > 29.7 457.9us 322.0us -2048 398.08 275.93 > 30.7 796.2us 551.9us - -(C4) - -bits multiply square ad percent time/mult time/square -64 1.34 1.28 > 4.5 2.68us 2.56us -128 2.76 2.59 > 6.2 5.52us 5.18us -192 4.52 4.16 > 8.0 9.04us 8.32us -256 6.64 5.99 > 9.8 13.3us 12.0us -320 9.20 8.13 > 11.6 18.4us 16.3us -384 12.01 10.58 > 11.9 24.0us 21.2us -448 15.24 13.33 > 12.5 30.5us 26.7us -512 19.02 16.46 > 13.5 38.0us 32.9us -640 27.56 23.54 > 14.6 55.1us 47.1us -768 37.89 31.78 > 16.1 75.8us 63.6us -896 49.24 41.42 > 15.9 98.5us 82.8us -1024 62.59 52.18 > 16.6 125.2us 104.3us -1536 131.66 107.72 > 18.2 263.3us 215.4us -2048 226.45 182.95 > 19.2 453.0us 365.9us - -(A7) - -bits multiply square ad percent time/mult time/square -64 1.74 1.71 > 1.7 3.48us 3.42us -128 3.48 2.96 > 14.9 6.96us 5.92us -192 5.74 4.60 > 19.9 11.5us 9.20us -256 8.75 6.61 > 24.5 17.5us 13.2us -320 12.5 8.99 > 28.1 25.0us 18.0us -384 16.9 11.9 > 29.6 33.8us 23.8us -448 22.2 15.2 > 31.7 44.4us 30.4us -512 28.3 19.0 > 32.7 56.6us 38.0us -640 42.4 28.0 > 34.0 84.8us 56.0us -768 59.4 38.5 > 35.2 118.8us 77.0us -896 79.5 51.2 > 35.6 159.0us 102.4us -1024 102.6 65.5 > 36.2 205.2us 131.0us -1536 224.3 140.6 > 37.3 448.6us 281.2us -2048 393.4 244.3 > 37.9 786.8us 488.6us - ------------------------------------------------------------------- -***** 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$ - - |