summaryrefslogtreecommitdiff
path: root/security/nss/lib/freebl/mpi/utils/README
diff options
context:
space:
mode:
Diffstat (limited to 'security/nss/lib/freebl/mpi/utils/README')
-rw-r--r--security/nss/lib/freebl/mpi/utils/README206
1 files changed, 0 insertions, 206 deletions
diff --git a/security/nss/lib/freebl/mpi/utils/README b/security/nss/lib/freebl/mpi/utils/README
deleted file mode 100644
index 61c8e2efa5..0000000000
--- a/security/nss/lib/freebl/mpi/utils/README
+++ /dev/null
@@ -1,206 +0,0 @@
-This Source Code Form is subject to the terms of the Mozilla Public
-License, v. 2.0. If a copy of the MPL was not distributed with this
-file, You can obtain one at http://mozilla.org/MPL/2.0/.
-
-Additional MPI utilities
-------------------------
-
-The files 'mpprime.h' and 'mpprime.c' define some useful extensions to
-the MPI library for dealing with prime numbers (in particular, testing
-for divisbility, and the Rabin-Miller probabilistic primality test).
-
-The files 'mplogic.h' and 'mplogic.c' define extensions to the MPI
-library for doing bitwise logical operations and shifting.
-
-This document assumes you have read the help file for the MPI library
-and understand its conventions.
-
-Divisibility (mpprime.h)
-------------
-
-To test a number for divisibility by another number:
-
-mpp_divis(a, b) - test if b|a
-mpp_divis_d(a, d) - test if d|a
-
-Each of these functions returns MP_YES if its initial argument is
-divisible by its second, or MP_NO if it is not. Other errors may be
-returned as appropriate (such as MP_RANGE if you try to test for
-divisibility by zero).
-
-Randomness (mpprime.h)
-----------
-
-To generate random data:
-
-mpp_random(a) - fill a with random data
-mpp_random_size(a, p) - fill a with p digits of random data
-
-The mpp_random_size() function increases the precision of a to at
-least p, then fills all those digits randomly. The mp_random()
-function fills a to its current precision (as determined by the number
-of significant digits, USED(a))
-
-Note that these functions simply use the C library's rand() function
-to fill a with random digits up to its precision. This should be
-adequate for primality testing, but should not be used for
-cryptographic applications where truly random values are required for
-security.
-
-You should call srand() in your driver program in order to seed the
-random generator; this function doesn't call it.
-
-Primality Testing (mpprime.h)
------------------
-
-mpp_divis_vector(a, v, s, w) - is a divisible by any of the s values
- in v, and if so, w = which.
-mpp_divis_primes(a, np) - is a divisible by any of the first np primes?
-mpp_fermat(a, w) - is a pseudoprime with respect to witness w?
-mpp_pprime(a, nt) - run nt iterations of Rabin-Miller on a.
-
-The mpp_divis_vector() function tests a for divisibility by each
-member of an array of digits. The array is v, the size of that array
-is s. Returns MP_YES if a is divisible, and stores the index of the
-offending digit in w. Returns MP_NO if a is not divisible by any of
-the digits in the array.
-
-A small table of primes is compiled into the library (typically the
-first 128 primes, although you can change this by editing the file
-'primes.c' before you build). The global variable prime_tab_size
-contains the number of primes in the table, and the values themselves
-are in the array prime_tab[], which is an array of mp_digit.
-
-The mpp_divis_primes() function is basically just a wrapper around
-mpp_divis_vector() that uses prime_tab[] as the test vector. The np
-parameter is a pointer to an mp_digit -- on input, it should specify
-the number of primes to be tested against. If a is divisible by any
-of the primes, MP_YES is returned and np is given the prime value that
-divided a (you can use this if you're factoring, for example).
-Otherwise, MP_NO is returned and np is untouched.
-
-The function mpp_fermat() performs Fermat's test, using w as a
-witness. This test basically relies on the fact that if a is prime,
-and w is relatively prime to a, then:
-
- w^a = w (mod a)
-
-That is,
-
- w^(a - 1) = 1 (mod a)
-
-The function returns MP_YES if the test passes, MP_NO if it fails. If
-w is relatively prime to a, and the test fails, a is definitely
-composite. If w is relatively prime to a and the test passes, then a
-is either prime, or w is a false witness (the probability of this
-happening depends on the choice of w and of a ... consult a number
-theory textbook for more information about this).
-
-Note: If (w, a) != 1, the output of this test is meaningless.
-----
-
-The function mpp_pprime() performs the Rabin-Miller probabilistic
-primality test for nt rounds. If all the tests pass, MP_YES is
-returned, and a is probably prime. The probability that an answer of
-MP_YES is incorrect is no greater than 1 in 4^nt, and in fact is
-usually much less than that (this is a pessimistic estimate). If any
-test fails, MP_NO is returned, and a is definitely composite.
-
-Bruce Schneier recommends at least 5 iterations of this test for most
-cryptographic applications; Knuth suggests that 25 are reasonable.
-Run it as many times as you feel are necessary.
-
-See the programs 'makeprime.c' and 'isprime.c' for reasonable examples
-of how to use these functions for primality testing.
-
-
-Bitwise Logic (mplogic.c)
--------------
-
-The four commonest logical operations are implemented as:
-
-mpl_not(a, b) - Compute bitwise (one's) complement, b = ~a
-
-mpl_and(a, b, c) - Compute bitwise AND, c = a & b
-
-mpl_or(a, b, c) - Compute bitwise OR, c = a | b
-
-mpl_xor(a, b, c) - Compute bitwise XOR, c = a ^ b
-
-Left and right shifts are available as well. These take a number to
-shift, a destination, and a shift amount. The shift amount must be a
-digit value between 0 and DIGIT_BIT inclusive; if it is not, MP_RANGE
-will be returned and the shift will not happen.
-
-mpl_rsh(a, b, d) - Compute logical right shift, b = a >> d
-
-mpl_lsh(a, b, d) - Compute logical left shift, b = a << d
-
-Since these are logical shifts, they fill with zeroes (the library
-uses a signed magnitude representation, so there are no sign bits to
-extend anyway).
-
-
-Command-line Utilities
-----------------------
-
-A handful of interesting command-line utilities are provided. These
-are:
-
-lap.c - Find the order of a mod m. Usage is 'lap <a> <m>'.
- This uses a dumb algorithm, so don't use it for
- a really big modulus.
-
-invmod.c - Find the inverse of a mod m, if it exists. Usage
- is 'invmod <a> <m>'
-
-sieve.c - A simple bitmap-based implementation of the Sieve
- of Eratosthenes. Used to generate the table of
- primes in primes.c. Usage is 'sieve <nbits>'
-
-prng.c - Uses the routines in bbs_rand.{h,c} to generate
- one or more 32-bit pseudo-random integers. This
- is mainly an example, not intended for use in a
- cryptographic application (the system time is
- the only source of entropy used)
-
-dec2hex.c - Convert decimal to hexadecimal
-
-hex2dec.c - Convert hexadecimal to decimal
-
-basecvt.c - General radix conversion tool (supports 2-64)
-
-isprime.c - Probabilistically test an integer for primality
- using the Rabin-Miller pseudoprime test combined
- with division by small primes.
-
-primegen.c - Generate primes at random.
-
-exptmod.c - Perform modular exponentiation
-
-ptab.pl - A Perl script to munge the output of the sieve
- program into a compilable C structure.
-
-
-Other Files
------------
-
-PRIMES - Some randomly generated numbers which are prime with
- extremely high probability.
-
-README - You're reading me already.
-
-
-About the Author
-----------------
-
-This software was written by Michael J. Fromberger. You can contact
-the author as follows:
-
-E-mail: <sting@linguist.dartmouth.edu>
-
-Postal: 8000 Cummings Hall, Thayer School of Engineering
- Dartmouth College, Hanover, New Hampshire, USA
-
-PGP key: http://linguist.dartmouth.edu/~sting/keys/mjf.html
- 9736 188B 5AFA 23D6 D6AA BE0D 5856 4525 289D 9907