nss-3.26/nss/lib/freebl/mpi/utils/README - nest-hello/510950009/nss - Git at Google

 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
	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