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