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) 1997-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: About the MPI Library michael@0: --------------------- michael@0: michael@0: The files 'mpi.h' and 'mpi.c' define a simple, arbitrary precision michael@0: signed integer arithmetic package. The implementation is not the most michael@0: efficient possible, but the code is small and should be fairly easily michael@0: portable to just about any machine that supports an ANSI C compiler, michael@0: as long as it is capable of at least 16-bit arithmetic (but also see michael@0: below for more on this). michael@0: michael@0: This library was written with an eye to cryptographic applications; michael@0: thus, some care is taken to make sure that temporary values are not michael@0: left lying around in memory when they are no longer in use. This adds michael@0: some overhead for zeroing buffers before they are released back into michael@0: the free pool; however, it gives you the assurance that there is only michael@0: one copy of your important values residing in your process's address michael@0: space at a time. Obviously, it is difficult to guarantee anything, in michael@0: a pre-emptive multitasking environment, but this at least helps you michael@0: keep a lid on the more obvious ways your data can get spread around in michael@0: memory. michael@0: michael@0: michael@0: Using the Library michael@0: ----------------- michael@0: michael@0: To use the MPI library in your program, you must include the header: michael@0: michael@0: #include "mpi.h" michael@0: michael@0: This header provides all the type and function declarations you'll michael@0: need to use the library. Almost all the names defined by the library michael@0: begin with the prefix 'mp_', so it should be easy to keep them from michael@0: clashing with your program's namespace (he says, glibly, knowing full michael@0: well there are always pathological cases). michael@0: michael@0: There are a few things you may want to configure about the library. michael@0: By default, the MPI library uses an unsigned short for its digit type, michael@0: and an unsigned int for its word type. The word type must be big michael@0: enough to contain at least two digits, for the primitive arithmetic to michael@0: work out. On my machine, a short is 2 bytes and an int is 4 bytes -- michael@0: but if you have 64-bit ints, you might want to use a 4-byte digit and michael@0: an 8-byte word. I have tested the library using 1-byte digits and michael@0: 2-byte words, as well. Whatever you choose to do, the things you need michael@0: to change are: michael@0: michael@0: (1) The type definitions for mp_digit and mp_word. michael@0: michael@0: (2) The macro DIGIT_FMT which tells mp_print() how to display a michael@0: single digit. This is just a printf() format string, so you michael@0: can adjust it appropriately. michael@0: michael@0: (3) The macros DIGIT_MAX and MP_WORD_MAX, which specify the michael@0: largest value expressible in an mp_digit and an mp_word, michael@0: respectively. michael@0: michael@0: Both the mp_digit and mp_word should be UNSIGNED integer types. The michael@0: code relies on having the full positive precision of the type used for michael@0: digits and words. michael@0: michael@0: The remaining type definitions should be left alone, for the most michael@0: part. The code in the library does not make any significant michael@0: assumptions about the sizes of things, but there is little if any michael@0: reason to change the other parameters, so I would recommend you leave michael@0: them as you found them. michael@0: michael@0: The library comes with a Perl script, 'types.pl', which will scan your michael@0: current Makefile settings, and attempt to find good definitions for michael@0: these types. It relies on a Unix sort of build environment, so it michael@0: probably won't work under MacOS or Windows, but it can be convenient michael@0: if you're porting to a new flavour of Unix. Just run 'types.pl' at michael@0: the command line, and it will spit out its results to the standard michael@0: output. michael@0: michael@0: michael@0: Conventions michael@0: ----------- michael@0: michael@0: Most functions in the library return a value of type mp_err. This michael@0: permits the library to communicate success or various kinds of failure michael@0: to the calling program. The return values currently defined are: michael@0: michael@0: MP_OKAY - okay, operation succeeded, all's well michael@0: MP_YES - okay, the answer is yes (same as MP_OKAY) michael@0: MP_NO - okay, but answer is no (not MP_OKAY) michael@0: MP_MEM - operation ran out of memory michael@0: MP_RANGE - input parameter was out of range michael@0: MP_BADARG - an invalid input parameter was provided michael@0: MP_UNDEF - no output value is defined for this input michael@0: michael@0: The only function which currently uses MP_UNDEF is mp_invmod(). michael@0: Division by zero is undefined, but the division functions will return michael@0: MP_RANGE for a zero divisor. MP_BADARG usually means you passed a michael@0: bogus mp_int structure to the function. MP_YES and MP_NO are not used michael@0: by the library itself; they're defined so you can use them in your own michael@0: extensions. michael@0: michael@0: If you need a readable interpretation of these error codes in your michael@0: program, you may also use the mp_strerror() function. This function michael@0: takes an mp_err as input, and returns a pointer to a human-readable michael@0: string describing the meaning of the error. These strings are stored michael@0: as constants within the library, so the caller should not attempt to michael@0: modify or free the memory associated with these strings. michael@0: michael@0: The library represents values in signed-magnitude format. Values michael@0: strictly less than zero are negative, all others are considered michael@0: positive (zero is positive by fiat). You can access the 'sign' member michael@0: of the mp_int structure directly, but better is to use the mp_cmp_z() michael@0: function, to find out which side of zero the value lies on. michael@0: michael@0: Most arithmetic functions have a single-digit variant, as well as the michael@0: full arbitrary-precision. An mp_digit is an unsigned value between 0 michael@0: and DIGIT_MAX inclusive. The radix is available as RADIX. The number michael@0: of bits in a given digit is given as DIGIT_BIT. michael@0: michael@0: Generally, input parameters are given before output parameters. michael@0: Unless otherwise specified, any input parameter can be re-used as an michael@0: output parameter, without confusing anything. michael@0: michael@0: The basic numeric type defined by the library is an mp_int. Virtually michael@0: all the functions in the library take a pointer to an mp_int as one of michael@0: their parameters. An explanation of how to create and use these michael@0: structures follows. And so, without further ado... michael@0: michael@0: michael@0: Initialization and Cleanup michael@0: -------------------------- michael@0: michael@0: The basic numeric type defined by the library is an 'mp_int'. michael@0: However, it is not sufficient to simply declare a variable of type michael@0: mp_int in your program. These variables also need to be initialized michael@0: before they can be used, to allocate the internal storage they require michael@0: for computation. michael@0: michael@0: This is done using one of the following functions: michael@0: michael@0: mp_init(mp_int *mp); michael@0: mp_init_copy(mp_int *mp, mp_int *from); michael@0: mp_init_size(mp_int *mp, mp_size p); michael@0: michael@0: Each of these requires a pointer to a structure of type mp_int. The michael@0: basic mp_init() simply initializes the mp_int to a default size, and michael@0: sets its value to zero. If you would like to initialize a copy of an michael@0: existing mp_int, use mp_init_copy(), where the 'from' parameter is the michael@0: mp_int you'd like to make a copy of. The third function, michael@0: mp_init_size(), permits you to specify how many digits of precision michael@0: should be preallocated for your mp_int. This can help the library michael@0: avoid unnecessary re-allocations later on. michael@0: michael@0: The default precision used by mp_init() can be retrieved using: michael@0: michael@0: precision = mp_get_prec(); michael@0: michael@0: This returns the number of digits that will be allocated. You can michael@0: change this value by using: michael@0: michael@0: mp_set_prec(unsigned int prec); michael@0: michael@0: Any positive value is acceptable -- if you pass zero, the default michael@0: precision will be re-set to the compiled-in library default (this is michael@0: specified in the header file 'mpi-config.h', and typically defaults to michael@0: 8 or 16). michael@0: michael@0: Just as you must allocate an mp_int before you can use it, you must michael@0: clean up the structure when you are done with it. This is performed michael@0: using the mp_clear() function. Remember that any mp_int that you michael@0: create as a local variable in a function must be mp_clear()'d before michael@0: that function exits, or else the memory allocated to that mp_int will michael@0: be orphaned and unrecoverable. michael@0: michael@0: To set an mp_int to a given value, the following functions are given: michael@0: michael@0: mp_set(mp_int *mp, mp_digit d); michael@0: mp_set_int(mp_int *mp, long z); michael@0: michael@0: The mp_set() function sets the mp_int to a single digit value, while michael@0: mp_set_int() sets the mp_int to a signed long integer value. michael@0: michael@0: To set an mp_int to zero, use: michael@0: michael@0: mp_zero(mp_int *mp); michael@0: michael@0: michael@0: Copying and Moving michael@0: ------------------ michael@0: michael@0: If you have two initialized mp_int's, and you want to copy the value michael@0: of one into the other, use: michael@0: michael@0: mp_copy(from, to) michael@0: michael@0: This takes care of clearing the old value of 'to', and copies the new michael@0: value into it. If 'to' is not yet initialized, use mp_init_copy() michael@0: instead (see above). michael@0: michael@0: Note: The library tries, whenever possible, to avoid allocating michael@0: ---- new memory. Thus, mp_copy() tries first to satisfy the needs michael@0: of the copy by re-using the memory already allocated to 'to'. michael@0: Only if this proves insufficient will mp_copy() actually michael@0: allocate new memory. michael@0: michael@0: For this reason, if you know a priori that 'to' has enough michael@0: available space to hold 'from', you don't need to check the michael@0: return value of mp_copy() for memory failure. The USED() michael@0: macro tells you how many digits are used by an mp_int, and michael@0: the ALLOC() macro tells you how many are allocated. michael@0: michael@0: If you have two initialized mp_int's, and you want to exchange their michael@0: values, use: michael@0: michael@0: mp_exch(a, b) michael@0: michael@0: This is better than using mp_copy() with a temporary, since it will michael@0: not (ever) touch the memory allocator -- it just swaps the exact michael@0: contents of the two structures. The mp_exch() function cannot fail; michael@0: if you pass it an invalid structure, it just ignores it, and does michael@0: nothing. michael@0: michael@0: michael@0: Basic Arithmetic michael@0: ---------------- michael@0: michael@0: Once you have initialized your integers, you can operate on them. The michael@0: basic arithmetic functions on full mp_int values are: michael@0: michael@0: mp_add(a, b, c) - computes c = a + b michael@0: mp_sub(a, b, c) - computes c = a - b michael@0: mp_mul(a, b, c) - computes c = a * b michael@0: mp_sqr(a, b) - computes b = a * a michael@0: mp_div(a, b, q, r) - computes q, r such that a = bq + r michael@0: mp_div_2d(a, d, q, r) - computes q = a / 2^d, r = a % 2^d michael@0: mp_expt(a, b, c) - computes c = a ** b michael@0: mp_2expt(a, k) - computes a = 2^k michael@0: mp_sqrt(a, c) - computes c = floor(sqrt(a)) michael@0: michael@0: The mp_div_2d() function efficiently computes division by powers of michael@0: two. Either the q or r parameter may be NULL, in which case that michael@0: portion of the computation will be discarded. michael@0: michael@0: The algorithms used for some of the computations here are described in michael@0: the following files which are included with this distribution: michael@0: michael@0: mul.txt Describes the multiplication algorithm michael@0: div.txt Describes the division algorithm michael@0: expt.txt Describes the exponentiation algorithm michael@0: sqrt.txt Describes the square-root algorithm michael@0: square.txt Describes the squaring algorithm michael@0: michael@0: There are single-digit versions of most of these routines, as well. michael@0: In the following prototypes, 'd' is a single mp_digit: michael@0: michael@0: mp_add_d(a, d, c) - computes c = a + d michael@0: mp_sub_d(a, d, c) - computes c = a - d michael@0: mp_mul_d(a, d, c) - computes c = a * d michael@0: mp_mul_2(a, c) - computes c = a * 2 michael@0: mp_div_d(a, d, q, r) - computes q, r such that a = bq + r michael@0: mp_div_2(a, c) - computes c = a / 2 michael@0: mp_expt_d(a, d, c) - computes c = a ** d michael@0: michael@0: The mp_mul_2() and mp_div_2() functions take advantage of the internal michael@0: representation of an mp_int to do multiplication by two more quickly michael@0: than mp_mul_d() would. Other basic functions of an arithmetic variety michael@0: include: michael@0: michael@0: mp_zero(a) - assign 0 to a michael@0: mp_neg(a, c) - negate a: c = -a michael@0: mp_abs(a, c) - absolute value: c = |a| michael@0: michael@0: michael@0: Comparisons michael@0: ----------- michael@0: michael@0: Several comparison functions are provided. Each of these, unless michael@0: otherwise specified, returns zero if the comparands are equal, < 0 if michael@0: the first is less than the second, and > 0 if the first is greater michael@0: than the second: michael@0: michael@0: mp_cmp_z(a) - compare a <=> 0 michael@0: mp_cmp_d(a, d) - compare a <=> d, d is a single digit michael@0: mp_cmp(a, b) - compare a <=> b michael@0: mp_cmp_mag(a, b) - compare |a| <=> |b| michael@0: mp_cmp_int(a, z) - compare a <=> z, z is a signed long integer michael@0: mp_isodd(a) - return nonzero if odd, zero otherwise michael@0: mp_iseven(a) - return nonzero if even, zero otherwise michael@0: michael@0: michael@0: Modular Arithmetic michael@0: ------------------ michael@0: michael@0: Modular variations of the basic arithmetic functions are also michael@0: supported. These are available if the MP_MODARITH parameter in michael@0: mpi-config.h is turned on (it is by default). The modular arithmetic michael@0: functions are: michael@0: michael@0: mp_mod(a, m, c) - compute c = a (mod m), 0 <= c < m michael@0: mp_mod_d(a, d, c) - compute c = a (mod d), 0 <= c < d (see below) michael@0: mp_addmod(a, b, m, c) - compute c = (a + b) mod m michael@0: mp_submod(a, b, m, c) - compute c = (a - b) mod m michael@0: mp_mulmod(a, b, m, c) - compute c = (a * b) mod m michael@0: mp_sqrmod(a, m, c) - compute c = (a * a) mod m michael@0: mp_exptmod(a, b, m, c) - compute c = (a ** b) mod m michael@0: mp_exptmod_d(a, d, m, c)- compute c = (a ** d) mod m michael@0: michael@0: The mp_sqr() function squares its input argument. A call to mp_sqr(a, michael@0: c) is identical in meaning to mp_mul(a, a, c); however, if the michael@0: MP_SQUARE variable is set true in mpi-config.h (see below), then it michael@0: will be implemented with a different algorithm, that is supposed to michael@0: take advantage of the redundant computation that takes place during michael@0: squaring. Unfortunately, some compilers result in worse performance michael@0: on this code, so you can change the behaviour at will. There is a michael@0: utility program "mulsqr.c" that lets you test which does better on michael@0: your system. michael@0: michael@0: The mp_sqrmod() function is analogous to the mp_sqr() function; it michael@0: uses the mp_sqr() function rather than mp_mul(), and then performs the michael@0: modular reduction. This probably won't help much unless you are doing michael@0: a lot of them. michael@0: michael@0: See the file 'square.txt' for a synopsis of the algorithm used. michael@0: michael@0: Note: The mp_mod_d() function computes a modular reduction around michael@0: ---- a single digit d. The result is a single digit c. michael@0: michael@0: Because an inverse is defined for a (mod m) if and only if (a, m) = 1 michael@0: (that is, if a and m are relatively prime), mp_invmod() may not be michael@0: able to compute an inverse for the arguments. In this case, it michael@0: returns the value MP_UNDEF, and does not modify c. If an inverse is michael@0: defined, however, it returns MP_OKAY, and sets c to the value of the michael@0: inverse (mod m). michael@0: michael@0: See the file 'redux.txt' for a description of the modular reduction michael@0: algorithm used by mp_exptmod(). michael@0: michael@0: michael@0: Greatest Common Divisor michael@0: ----------------------- michael@0: michael@0: If The greates common divisor of two values can be found using one of the michael@0: following functions: michael@0: michael@0: mp_gcd(a, b, c) - compute c = (a, b) using binary algorithm michael@0: mp_lcm(a, b, c) - compute c = [a, b] = ab / (a, b) michael@0: mp_xgcd(a, b, g, x, y) - compute g, x, y so that ax + by = g = (a, b) michael@0: michael@0: Also provided is a function to compute modular inverses, if they michael@0: exist: michael@0: michael@0: mp_invmod(a, m, c) - compute c = a^-1 (mod m), if it exists michael@0: michael@0: The function mp_xgcd() computes the greatest common divisor, and also michael@0: returns values of x and y satisfying Bezout's identity. This is used michael@0: by mp_invmod() to find modular inverses. However, if you do not need michael@0: these values, you will find that mp_gcd() is MUCH more efficient, michael@0: since it doesn't need all the intermediate values that mp_xgcd() michael@0: requires in order to compute x and y. michael@0: michael@0: The mp_gcd() (and mp_xgcd()) functions use the binary (extended) GCD michael@0: algorithm due to Josef Stein. michael@0: michael@0: michael@0: Input & Output Functions michael@0: ------------------------ michael@0: michael@0: The following basic I/O routines are provided. These are present at michael@0: all times: michael@0: michael@0: mp_read_radix(mp, str, r) - convert a string in radix r to an mp_int michael@0: mp_read_raw(mp, s, len) - convert a string of bytes to an mp_int michael@0: mp_radix_size(mp, r) - return length of buffer needed by mp_toradix() michael@0: mp_raw_size(mp) - return length of buffer needed by mp_toraw() michael@0: mp_toradix(mp, str, r) - convert an mp_int to a string of radix r michael@0: digits michael@0: mp_toraw(mp, str) - convert an mp_int to a string of bytes michael@0: mp_tovalue(ch, r) - convert ch to its value when taken as michael@0: a radix r digit, or -1 if invalid michael@0: mp_strerror(err) - get a string describing mp_err value 'err' michael@0: michael@0: If you compile the MPI library with MP_IOFUNC defined, you will also michael@0: have access to the following additional I/O function: michael@0: michael@0: mp_print(mp, ofp) - print an mp_int as text to output stream ofp michael@0: michael@0: Note that mp_radix_size() returns a size in bytes guaranteed to be AT michael@0: LEAST big enough for the digits output by mp_toradix(). Because it michael@0: uses an approximation technique to figure out how many digits will be michael@0: needed, it may return a figure which is larger than necessary. Thus, michael@0: the caller should not rely on the value to determine how many bytes michael@0: will actually be written by mp_toradix(). The string mp_toradix() michael@0: creates will be NUL terminated, so the standard C library function michael@0: strlen() should be able to ascertain this for you, if you need it. michael@0: michael@0: The mp_read_radix() and mp_toradix() functions support bases from 2 to michael@0: 64 inclusive. If you require more general radix conversion facilities michael@0: than this, you will need to write them yourself (that's why mp_div_d() michael@0: is provided, after all). michael@0: michael@0: Note: mp_read_radix() will accept as digits either capital or michael@0: ---- lower-case letters. However, the current implementation of michael@0: mp_toradix() only outputs upper-case letters, when writing michael@0: bases betwee 10 and 36. The underlying code supports using michael@0: lower-case letters, but the interface stub does not have a michael@0: selector for it. You can add one yourself if you think it michael@0: is worthwhile -- I do not. Bases from 36 to 64 use lower- michael@0: case letters as distinct from upper-case. Bases 63 and michael@0: 64 use the characters '+' and '/' as digits. michael@0: michael@0: Note also that compiling with MP_IOFUNC defined will cause michael@0: inclusion of , so if you are trying to write code michael@0: which does not depend on the standard C library, you will michael@0: probably want to avoid this option. This is needed because michael@0: the mp_print() function takes a standard library FILE * as michael@0: one of its parameters, and uses the fprintf() function. michael@0: michael@0: The mp_toraw() function converts the integer to a sequence of bytes, michael@0: in big-endian ordering (most-significant byte first). Assuming your michael@0: bytes are 8 bits wide, this corresponds to base 256. The sign is michael@0: encoded as a single leading byte, whose value is 0 for zero or michael@0: positive values, or 1 for negative values. The mp_read_raw() function michael@0: reverses this process -- it takes a buffer of bytes, interprets the michael@0: first as a sign indicator (0 = zero/positive, nonzero = negative), and michael@0: the rest as a sequence of 1-byte digits in big-endian ordering. michael@0: michael@0: The mp_raw_size() function returns the exact number of bytes required michael@0: to store the given integer in "raw" format (as described in the michael@0: previous paragraph). Zero is returned in case of error; a valid michael@0: integer will require at least three bytes of storage. michael@0: michael@0: In previous versions of the MPI library, an "external representation michael@0: format" was supported. This was removed, however, because I found I michael@0: was never using it, it was not as portable as I would have liked, and michael@0: I decided it was a waste of space. michael@0: michael@0: michael@0: Other Functions michael@0: --------------- michael@0: michael@0: The files 'mpprime.h' and 'mpprime.c' define some routines which are michael@0: useful for divisibility testing and probabilistic primality testing. michael@0: The routines defined are: michael@0: michael@0: mpp_divis(a, b) - is a divisible by b? michael@0: mpp_divis_d(a, d) - is a divisible by digit d? michael@0: mpp_random(a) - set a to random value at current precision michael@0: mpp_random_size(a, prec) - set a to random value at given precision michael@0: michael@0: Note: The mpp_random() and mpp_random_size() functions use the C michael@0: ---- library's rand() function to generate random values. It is michael@0: up to the caller to seed this generator before it is called. michael@0: These functions are not suitable for generating quantities michael@0: requiring cryptographic-quality randomness; they are intended michael@0: primarily for use in primality testing. michael@0: michael@0: Note too that the MPI library does not call srand(), so your michael@0: application should do this, if you ever want the sequence michael@0: to change. michael@0: michael@0: mpp_divis_vector(a, v, s, w) - is a divisible by any of the s digits michael@0: in v? If so, let w be the index of michael@0: that digit michael@0: michael@0: mpp_divis_primes(a, np) - is a divisible by any of the first np michael@0: primes? If so, set np to the prime michael@0: which divided a. michael@0: michael@0: mpp_fermat(a, d) - test if w^a = w (mod a). If so, michael@0: returns MP_YES, otherwise MP_NO. michael@0: michael@0: mpp_pprime(a, nt) - perform nt iterations of the Rabin- michael@0: Miller probabilistic primality test michael@0: on a. Returns MP_YES if all tests michael@0: passed, or MP_NO if any test fails. michael@0: michael@0: The mpp_fermat() function works based on Fermat's little theorem, a michael@0: consequence of which is that if p is a prime, and (w, p) = 1, then: michael@0: michael@0: w^p = w (mod p) michael@0: michael@0: Put another way, if w^p != w (mod p), then p is not prime. The test michael@0: is expensive to compute, but it helps to quickly eliminate an enormous michael@0: class of composite numbers prior to Rabin-Miller testing. michael@0: michael@0: Building the Library michael@0: -------------------- michael@0: michael@0: The MPI library is designed to be as self-contained as possible. You michael@0: should be able to compile it with your favourite ANSI C compiler, and michael@0: link it into your program directly. If you are on a Unix system using michael@0: the GNU C compiler (gcc), the following should work: michael@0: michael@0: % gcc -ansi -pedantic -Wall -O2 -c mpi.c michael@0: michael@0: The file 'mpi-config.h' defines several configurable parameters for michael@0: the library, which you can adjust to suit your application. At the michael@0: time of this writing, the available options are: michael@0: michael@0: MP_IOFUNC - Define true to include the mp_print() function, michael@0: which is moderately useful for debugging. This michael@0: implicitly includes . michael@0: michael@0: MP_MODARITH - Define true to include the modular arithmetic michael@0: functions. If you don't need modular arithmetic michael@0: in your application, you can set this to zero to michael@0: leave out all the modular routines. michael@0: michael@0: MP_NUMTH - Define true to include number theoretic functions michael@0: such as mp_gcd(), mp_lcm(), and mp_invmod(). michael@0: michael@0: MP_LOGTAB - If true, the file "logtab.h" is included, which michael@0: is basically a static table of base 2 logarithms. michael@0: These are used to compute how big the buffers for michael@0: radix conversion need to be. If you set this false, michael@0: the library includes and uses log(). This michael@0: typically forces you to link against math libraries. michael@0: michael@0: MP_MEMSET - If true, use memset() to zero buffers. If you run michael@0: into weird alignment related bugs, set this to zero michael@0: and an explicit loop will be used. michael@0: michael@0: MP_MEMCPY - If true, use memcpy() to copy buffers. If you run michael@0: into weird alignment bugs, set this to zero and an michael@0: explicit loop will be used. michael@0: michael@0: MP_CRYPTO - If true, whenever arrays of digits are free'd, they michael@0: are zeroed first. This is useful if you're using michael@0: the library in a cryptographic environment; however, michael@0: it does add overhead to each free operation. For michael@0: performance, if you don't care about zeroing your michael@0: buffers, set this to false. michael@0: michael@0: MP_ARGCHK - Set to 0, 1, or 2. This defines how the argument michael@0: checking macro, ARGCHK(), gets expanded. If this michael@0: is set to zero, ARGCHK() expands to nothing; no michael@0: argument checks are performed. If this is 1, the michael@0: ARGCHK() macro expands to code that returns MP_BADARG michael@0: or similar at runtime. If it is 2, ARGCHK() expands michael@0: to an assert() call that aborts the program on a michael@0: bad input. michael@0: michael@0: MP_DEBUG - Turns on debugging output. This is probably not at michael@0: all useful unless you are debugging the library. It michael@0: tends to spit out a LOT of output. michael@0: michael@0: MP_DEFPREC - The default precision of a newly-created mp_int, in michael@0: digits. The precision can be changed at runtime by michael@0: the mp_set_prec() function, but this is its initial michael@0: value. michael@0: michael@0: MP_SQUARE - If this is set to a nonzero value, the mp_sqr() michael@0: function will use an alternate algorithm that takes michael@0: advantage of the redundant inner product computation michael@0: when both multiplicands are identical. Unfortunately, michael@0: with some compilers this is actually SLOWER than just michael@0: calling mp_mul() with the same argument twice. So michael@0: if you set MP_SQUARE to zero, mp_sqr() will be expan- michael@0: ded into a call to mp_mul(). This applies to all michael@0: the uses of mp_sqr(), including mp_sqrmod() and the michael@0: internal calls to s_mp_sqr() inside mpi.c michael@0: michael@0: The program 'mulsqr' (mulsqr.c) can be used to test michael@0: which works best for your configuration. Set up the michael@0: CC and CFLAGS variables in the Makefile, then type: michael@0: michael@0: make mulsqr michael@0: michael@0: Invoke it with arguments similar to the following: michael@0: michael@0: mulsqr 25000 1024 michael@0: michael@0: That is, 25000 products computed on 1024-bit values. michael@0: The output will compare the two timings, and recommend michael@0: a setting for MP_SQUARE. It is off by default. michael@0: michael@0: If you would like to use the mp_print() function (see above), be sure michael@0: to define MP_IOFUNC in mpi-config.h. Many of the test drivers in the michael@0: 'tests' subdirectory expect this to be defined (although the test michael@0: driver 'mpi-test' doesn't need it) michael@0: michael@0: The Makefile which comes with the library should take care of building michael@0: the library for you, if you have set the CC and CFLAGS variables at michael@0: the top of the file appropriately. By default, they are set up to michael@0: use the GNU C compiler: michael@0: michael@0: CC=gcc michael@0: CFLAGS=-ansi -pedantic -Wall -O2 michael@0: michael@0: If all goes well, the library should compile without warnings using michael@0: this combination. You should, of course, make whatever adjustments michael@0: you find necessary. michael@0: michael@0: The MPI library distribution comes with several additional programs michael@0: which are intended to demonstrate the use of the library, and provide michael@0: a framework for testing it. There are a handful of test driver michael@0: programs, in the files named 'mptest-X.c', where X is a digit. Also, michael@0: there are some simple command-line utilities (in the 'utils' michael@0: directory) for manipulating large numbers. These include: michael@0: michael@0: basecvt.c A radix-conversion program, supporting bases from michael@0: 2 to 64 inclusive. michael@0: michael@0: bbsrand.c A BBS (quadratic residue) pseudo-random number michael@0: generator. The file 'bbsrand.c' is just the driver michael@0: for the program; the real code lives in the files michael@0: 'bbs_rand.h' and 'bbs_rand.c' michael@0: michael@0: dec2hex.c Converts decimal to hexadecimal michael@0: michael@0: gcd.c Computes the greatest common divisor of two values. michael@0: If invoked as 'xgcd', also computes constants x and michael@0: y such that (a, b) = ax + by, in accordance with michael@0: Bezout's identity. michael@0: michael@0: hex2dec.c Converts hexadecimal to decimal michael@0: michael@0: invmod.c Computes modular inverses michael@0: michael@0: isprime.c Performs the Rabin-Miller probabilistic primality michael@0: test on a number. Values which fail this test are michael@0: definitely composite, and those which pass are very michael@0: likely to be prime (although there are no guarantees) michael@0: michael@0: lap.c Computes the order (least annihilating power) of michael@0: a value v modulo m. Very dumb algorithm. michael@0: michael@0: primegen.c Generates large (probable) primes. michael@0: michael@0: prng.c A pseudo-random number generator based on the michael@0: BBS generator code in 'bbs_rand.c' michael@0: michael@0: sieve.c Implements the Sieve of Eratosthenes, using a big michael@0: bitmap, to generate a list of prime numbers. michael@0: michael@0: fact.c Computes the factorial of an arbitrary precision michael@0: integer (iterative). michael@0: michael@0: exptmod.c Computes arbitrary precision modular exponentiation michael@0: from the command line (exptmod a b m -> a^b (mod m)) michael@0: michael@0: Most of these can be built from the Makefile that comes with the michael@0: library. Try 'make tools', if your environment supports it. michael@0: michael@0: michael@0: Testing the Library michael@0: ------------------- michael@0: michael@0: Automatic test vectors are included, in the form of a program called michael@0: 'mpi-test'. To build this program and run all the tests, simply michael@0: invoke the shell script 'all-tests'. If all the tests pass, you michael@0: should see a message: michael@0: michael@0: All tests passed michael@0: michael@0: If something went wrong, you'll get: michael@0: michael@0: One or more tests failed. michael@0: michael@0: If this happens, scan back through the preceding lines, to see which michael@0: test failed. Any failure indicates a bug in the library, which needs michael@0: to be fixed before it will give accurate results. If you get any such michael@0: thing, please let me know, and I'll try to fix it. Please let me know michael@0: what platform and compiler you were using, as well as which test michael@0: failed. If a reason for failure was given, please send me that text michael@0: as well. michael@0: michael@0: If you're on a system where the standard Unix build tools don't work, michael@0: you can build the 'mpi-test' program manually, and run it by hand. michael@0: This is tedious and obnoxious, sorry. michael@0: michael@0: Further manual testing can be performed by building the manual testing michael@0: programs, whose source is found in the 'tests' subdirectory. Each michael@0: test is in a source file called 'mptest-X.c'. The Makefile contains a michael@0: target to build all of them at once: michael@0: michael@0: make tests michael@0: michael@0: Read the comments at the top of each source file to see what the michael@0: driver is supposed to test. You probably don't need to do this; these michael@0: programs were only written to help me as I was developing the library. michael@0: michael@0: The relevant files are: michael@0: michael@0: mpi-test.c The source for the test driver michael@0: michael@0: make-test-arrays A Perl script to generate some of the internal michael@0: data structures used by mpi-test.c michael@0: michael@0: test-arrays.txt The source file for make-test-arrays michael@0: michael@0: all-tests A Bourne shell script which runs all the michael@0: tests in the mpi-test suite michael@0: michael@0: Running 'make mpi-test' should build the mpi-test program. If you michael@0: cannot use make, here is what needs to be done: michael@0: michael@0: (1) Use 'make-test-arrays' to generate the file 'test-info.c' from michael@0: the 'test-arrays.txt' file. Since Perl can be found everywhere, michael@0: this should be no trouble. Under Unix, this looks like: michael@0: michael@0: make-test-arrays test-arrays.txt > test-info.c michael@0: michael@0: (2) Build the MPI library: michael@0: michael@0: gcc -ansi -pedantic -Wall -c mpi.c michael@0: michael@0: (3) Build the mpi-test program: michael@0: michael@0: gcc -ansi -pedantic -Wall -o mpi-test mpi.o mpi-test.c michael@0: michael@0: When you've got mpi-test, you can use 'all-tests' to run all the tests michael@0: made available by mpi-test. If any of them fail, there should be a michael@0: diagnostic indicating what went wrong. These are fairly high-level michael@0: diagnostics, and won't really help you debug the problem; they're michael@0: simply intended to help you isolate which function caused the problem. michael@0: If you encounter a problem of this sort, feel free to e-mail me, and I michael@0: will certainly attempt to help you debug it. michael@0: michael@0: Note: Several of the tests hard-wired into 'mpi-test' operate under michael@0: ---- the assumption that you are using at least a 16-bit mp_digit michael@0: type. If that is not true, several tests might fail, because michael@0: of range problems with the maximum digit value. michael@0: michael@0: If you are using an 8-bit digit, you will also need to michael@0: modify the code for mp_read_raw(), which assumes that michael@0: multiplication by 256 can be done with mp_mul_d(), a michael@0: fact that fails when DIGIT_MAX is 255. You can replace michael@0: the call with s_mp_lshd(), which will give you the same michael@0: effect, and without doing as much work. :) michael@0: michael@0: Acknowledgements: michael@0: ---------------- michael@0: michael@0: The algorithms used in this library were drawn primarily from Volume michael@0: 2 of Donald Knuth's magnum opus, _The Art of Computer Programming_, michael@0: "Semi-Numerical Methods". Barrett's algorithm for modular reduction michael@0: came from Menezes, Oorschot, and Vanstone's _Handbook of Applied michael@0: Cryptography_, Chapter 14. michael@0: michael@0: Thanks are due to Tom St. Denis, for finding an obnoxious sign-related michael@0: bug in mp_read_raw() that made things break on platforms which use michael@0: signed chars. 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 michael@0: michael@0: Last updated: 16-Jan-2000