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