1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/README Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,791 @@
1.4 +***** BEGIN LICENSE BLOCK *****
1.5 +Version: MPL 1.1/GPL 2.0/LGPL 2.1
1.6 +
1.7 +The contents of this file are subject to the Mozilla Public License Version
1.8 +1.1 (the "License"); you may not use this file except in compliance with
1.9 +the License. You may obtain a copy of the License at
1.10 +http://www.mozilla.org/MPL/
1.11 +
1.12 +Software distributed under the License is distributed on an "AS IS" basis,
1.13 +WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
1.14 +for the specific language governing rights and limitations under the
1.15 +License.
1.16 +
1.17 +The Original Code is the MPI Arbitrary Precision Integer Arithmetic
1.18 +library.
1.19 +
1.20 +The Initial Developer of the Original Code is
1.21 +Michael J. Fromberger <sting@linguist.dartmouth.edu>
1.22 +Portions created by the Initial Developer are Copyright (C) 1997-2000
1.23 +the Initial Developer. All Rights Reserved.
1.24 +
1.25 +Contributor(s):
1.26 +
1.27 +Alternatively, the contents of this file may be used under the terms of
1.28 +either the GNU General Public License Version 2 or later (the "GPL"), or
1.29 +the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
1.30 +in which case the provisions of the GPL or the LGPL are applicable instead
1.31 +of those above. If you wish to allow use of your version of this file only
1.32 +under the terms of either the GPL or the LGPL, and not to allow others to
1.33 +use your version of this file under the terms of the MPL, indicate your
1.34 +decision by deleting the provisions above and replace them with the notice
1.35 +and other provisions required by the GPL or the LGPL. If you do not delete
1.36 +the provisions above, a recipient may use your version of this file under
1.37 +the terms of any one of the MPL, the GPL or the LGPL.
1.38 +
1.39 +***** END LICENSE BLOCK *****
1.40 +
1.41 +About the MPI Library
1.42 +---------------------
1.43 +
1.44 +The files 'mpi.h' and 'mpi.c' define a simple, arbitrary precision
1.45 +signed integer arithmetic package. The implementation is not the most
1.46 +efficient possible, but the code is small and should be fairly easily
1.47 +portable to just about any machine that supports an ANSI C compiler,
1.48 +as long as it is capable of at least 16-bit arithmetic (but also see
1.49 +below for more on this).
1.50 +
1.51 +This library was written with an eye to cryptographic applications;
1.52 +thus, some care is taken to make sure that temporary values are not
1.53 +left lying around in memory when they are no longer in use. This adds
1.54 +some overhead for zeroing buffers before they are released back into
1.55 +the free pool; however, it gives you the assurance that there is only
1.56 +one copy of your important values residing in your process's address
1.57 +space at a time. Obviously, it is difficult to guarantee anything, in
1.58 +a pre-emptive multitasking environment, but this at least helps you
1.59 +keep a lid on the more obvious ways your data can get spread around in
1.60 +memory.
1.61 +
1.62 +
1.63 +Using the Library
1.64 +-----------------
1.65 +
1.66 +To use the MPI library in your program, you must include the header:
1.67 +
1.68 +#include "mpi.h"
1.69 +
1.70 +This header provides all the type and function declarations you'll
1.71 +need to use the library. Almost all the names defined by the library
1.72 +begin with the prefix 'mp_', so it should be easy to keep them from
1.73 +clashing with your program's namespace (he says, glibly, knowing full
1.74 +well there are always pathological cases).
1.75 +
1.76 +There are a few things you may want to configure about the library.
1.77 +By default, the MPI library uses an unsigned short for its digit type,
1.78 +and an unsigned int for its word type. The word type must be big
1.79 +enough to contain at least two digits, for the primitive arithmetic to
1.80 +work out. On my machine, a short is 2 bytes and an int is 4 bytes --
1.81 +but if you have 64-bit ints, you might want to use a 4-byte digit and
1.82 +an 8-byte word. I have tested the library using 1-byte digits and
1.83 +2-byte words, as well. Whatever you choose to do, the things you need
1.84 +to change are:
1.85 +
1.86 +(1) The type definitions for mp_digit and mp_word.
1.87 +
1.88 +(2) The macro DIGIT_FMT which tells mp_print() how to display a
1.89 + single digit. This is just a printf() format string, so you
1.90 + can adjust it appropriately.
1.91 +
1.92 +(3) The macros DIGIT_MAX and MP_WORD_MAX, which specify the
1.93 + largest value expressible in an mp_digit and an mp_word,
1.94 + respectively.
1.95 +
1.96 +Both the mp_digit and mp_word should be UNSIGNED integer types. The
1.97 +code relies on having the full positive precision of the type used for
1.98 +digits and words.
1.99 +
1.100 +The remaining type definitions should be left alone, for the most
1.101 +part. The code in the library does not make any significant
1.102 +assumptions about the sizes of things, but there is little if any
1.103 +reason to change the other parameters, so I would recommend you leave
1.104 +them as you found them.
1.105 +
1.106 +The library comes with a Perl script, 'types.pl', which will scan your
1.107 +current Makefile settings, and attempt to find good definitions for
1.108 +these types. It relies on a Unix sort of build environment, so it
1.109 +probably won't work under MacOS or Windows, but it can be convenient
1.110 +if you're porting to a new flavour of Unix. Just run 'types.pl' at
1.111 +the command line, and it will spit out its results to the standard
1.112 +output.
1.113 +
1.114 +
1.115 +Conventions
1.116 +-----------
1.117 +
1.118 +Most functions in the library return a value of type mp_err. This
1.119 +permits the library to communicate success or various kinds of failure
1.120 +to the calling program. The return values currently defined are:
1.121 +
1.122 + MP_OKAY - okay, operation succeeded, all's well
1.123 + MP_YES - okay, the answer is yes (same as MP_OKAY)
1.124 + MP_NO - okay, but answer is no (not MP_OKAY)
1.125 + MP_MEM - operation ran out of memory
1.126 + MP_RANGE - input parameter was out of range
1.127 + MP_BADARG - an invalid input parameter was provided
1.128 + MP_UNDEF - no output value is defined for this input
1.129 +
1.130 +The only function which currently uses MP_UNDEF is mp_invmod().
1.131 +Division by zero is undefined, but the division functions will return
1.132 +MP_RANGE for a zero divisor. MP_BADARG usually means you passed a
1.133 +bogus mp_int structure to the function. MP_YES and MP_NO are not used
1.134 +by the library itself; they're defined so you can use them in your own
1.135 +extensions.
1.136 +
1.137 +If you need a readable interpretation of these error codes in your
1.138 +program, you may also use the mp_strerror() function. This function
1.139 +takes an mp_err as input, and returns a pointer to a human-readable
1.140 +string describing the meaning of the error. These strings are stored
1.141 +as constants within the library, so the caller should not attempt to
1.142 +modify or free the memory associated with these strings.
1.143 +
1.144 +The library represents values in signed-magnitude format. Values
1.145 +strictly less than zero are negative, all others are considered
1.146 +positive (zero is positive by fiat). You can access the 'sign' member
1.147 +of the mp_int structure directly, but better is to use the mp_cmp_z()
1.148 +function, to find out which side of zero the value lies on.
1.149 +
1.150 +Most arithmetic functions have a single-digit variant, as well as the
1.151 +full arbitrary-precision. An mp_digit is an unsigned value between 0
1.152 +and DIGIT_MAX inclusive. The radix is available as RADIX. The number
1.153 +of bits in a given digit is given as DIGIT_BIT.
1.154 +
1.155 +Generally, input parameters are given before output parameters.
1.156 +Unless otherwise specified, any input parameter can be re-used as an
1.157 +output parameter, without confusing anything.
1.158 +
1.159 +The basic numeric type defined by the library is an mp_int. Virtually
1.160 +all the functions in the library take a pointer to an mp_int as one of
1.161 +their parameters. An explanation of how to create and use these
1.162 +structures follows. And so, without further ado...
1.163 +
1.164 +
1.165 +Initialization and Cleanup
1.166 +--------------------------
1.167 +
1.168 +The basic numeric type defined by the library is an 'mp_int'.
1.169 +However, it is not sufficient to simply declare a variable of type
1.170 +mp_int in your program. These variables also need to be initialized
1.171 +before they can be used, to allocate the internal storage they require
1.172 +for computation.
1.173 +
1.174 +This is done using one of the following functions:
1.175 +
1.176 + mp_init(mp_int *mp);
1.177 + mp_init_copy(mp_int *mp, mp_int *from);
1.178 + mp_init_size(mp_int *mp, mp_size p);
1.179 +
1.180 +Each of these requires a pointer to a structure of type mp_int. The
1.181 +basic mp_init() simply initializes the mp_int to a default size, and
1.182 +sets its value to zero. If you would like to initialize a copy of an
1.183 +existing mp_int, use mp_init_copy(), where the 'from' parameter is the
1.184 +mp_int you'd like to make a copy of. The third function,
1.185 +mp_init_size(), permits you to specify how many digits of precision
1.186 +should be preallocated for your mp_int. This can help the library
1.187 +avoid unnecessary re-allocations later on.
1.188 +
1.189 +The default precision used by mp_init() can be retrieved using:
1.190 +
1.191 + precision = mp_get_prec();
1.192 +
1.193 +This returns the number of digits that will be allocated. You can
1.194 +change this value by using:
1.195 +
1.196 + mp_set_prec(unsigned int prec);
1.197 +
1.198 +Any positive value is acceptable -- if you pass zero, the default
1.199 +precision will be re-set to the compiled-in library default (this is
1.200 +specified in the header file 'mpi-config.h', and typically defaults to
1.201 +8 or 16).
1.202 +
1.203 +Just as you must allocate an mp_int before you can use it, you must
1.204 +clean up the structure when you are done with it. This is performed
1.205 +using the mp_clear() function. Remember that any mp_int that you
1.206 +create as a local variable in a function must be mp_clear()'d before
1.207 +that function exits, or else the memory allocated to that mp_int will
1.208 +be orphaned and unrecoverable.
1.209 +
1.210 +To set an mp_int to a given value, the following functions are given:
1.211 +
1.212 + mp_set(mp_int *mp, mp_digit d);
1.213 + mp_set_int(mp_int *mp, long z);
1.214 +
1.215 +The mp_set() function sets the mp_int to a single digit value, while
1.216 +mp_set_int() sets the mp_int to a signed long integer value.
1.217 +
1.218 +To set an mp_int to zero, use:
1.219 +
1.220 + mp_zero(mp_int *mp);
1.221 +
1.222 +
1.223 +Copying and Moving
1.224 +------------------
1.225 +
1.226 +If you have two initialized mp_int's, and you want to copy the value
1.227 +of one into the other, use:
1.228 +
1.229 + mp_copy(from, to)
1.230 +
1.231 +This takes care of clearing the old value of 'to', and copies the new
1.232 +value into it. If 'to' is not yet initialized, use mp_init_copy()
1.233 +instead (see above).
1.234 +
1.235 +Note: The library tries, whenever possible, to avoid allocating
1.236 +---- new memory. Thus, mp_copy() tries first to satisfy the needs
1.237 + of the copy by re-using the memory already allocated to 'to'.
1.238 + Only if this proves insufficient will mp_copy() actually
1.239 + allocate new memory.
1.240 +
1.241 + For this reason, if you know a priori that 'to' has enough
1.242 + available space to hold 'from', you don't need to check the
1.243 + return value of mp_copy() for memory failure. The USED()
1.244 + macro tells you how many digits are used by an mp_int, and
1.245 + the ALLOC() macro tells you how many are allocated.
1.246 +
1.247 +If you have two initialized mp_int's, and you want to exchange their
1.248 +values, use:
1.249 +
1.250 + mp_exch(a, b)
1.251 +
1.252 +This is better than using mp_copy() with a temporary, since it will
1.253 +not (ever) touch the memory allocator -- it just swaps the exact
1.254 +contents of the two structures. The mp_exch() function cannot fail;
1.255 +if you pass it an invalid structure, it just ignores it, and does
1.256 +nothing.
1.257 +
1.258 +
1.259 +Basic Arithmetic
1.260 +----------------
1.261 +
1.262 +Once you have initialized your integers, you can operate on them. The
1.263 +basic arithmetic functions on full mp_int values are:
1.264 +
1.265 +mp_add(a, b, c) - computes c = a + b
1.266 +mp_sub(a, b, c) - computes c = a - b
1.267 +mp_mul(a, b, c) - computes c = a * b
1.268 +mp_sqr(a, b) - computes b = a * a
1.269 +mp_div(a, b, q, r) - computes q, r such that a = bq + r
1.270 +mp_div_2d(a, d, q, r) - computes q = a / 2^d, r = a % 2^d
1.271 +mp_expt(a, b, c) - computes c = a ** b
1.272 +mp_2expt(a, k) - computes a = 2^k
1.273 +mp_sqrt(a, c) - computes c = floor(sqrt(a))
1.274 +
1.275 +The mp_div_2d() function efficiently computes division by powers of
1.276 +two. Either the q or r parameter may be NULL, in which case that
1.277 +portion of the computation will be discarded.
1.278 +
1.279 +The algorithms used for some of the computations here are described in
1.280 +the following files which are included with this distribution:
1.281 +
1.282 +mul.txt Describes the multiplication algorithm
1.283 +div.txt Describes the division algorithm
1.284 +expt.txt Describes the exponentiation algorithm
1.285 +sqrt.txt Describes the square-root algorithm
1.286 +square.txt Describes the squaring algorithm
1.287 +
1.288 +There are single-digit versions of most of these routines, as well.
1.289 +In the following prototypes, 'd' is a single mp_digit:
1.290 +
1.291 +mp_add_d(a, d, c) - computes c = a + d
1.292 +mp_sub_d(a, d, c) - computes c = a - d
1.293 +mp_mul_d(a, d, c) - computes c = a * d
1.294 +mp_mul_2(a, c) - computes c = a * 2
1.295 +mp_div_d(a, d, q, r) - computes q, r such that a = bq + r
1.296 +mp_div_2(a, c) - computes c = a / 2
1.297 +mp_expt_d(a, d, c) - computes c = a ** d
1.298 +
1.299 +The mp_mul_2() and mp_div_2() functions take advantage of the internal
1.300 +representation of an mp_int to do multiplication by two more quickly
1.301 +than mp_mul_d() would. Other basic functions of an arithmetic variety
1.302 +include:
1.303 +
1.304 +mp_zero(a) - assign 0 to a
1.305 +mp_neg(a, c) - negate a: c = -a
1.306 +mp_abs(a, c) - absolute value: c = |a|
1.307 +
1.308 +
1.309 +Comparisons
1.310 +-----------
1.311 +
1.312 +Several comparison functions are provided. Each of these, unless
1.313 +otherwise specified, returns zero if the comparands are equal, < 0 if
1.314 +the first is less than the second, and > 0 if the first is greater
1.315 +than the second:
1.316 +
1.317 +mp_cmp_z(a) - compare a <=> 0
1.318 +mp_cmp_d(a, d) - compare a <=> d, d is a single digit
1.319 +mp_cmp(a, b) - compare a <=> b
1.320 +mp_cmp_mag(a, b) - compare |a| <=> |b|
1.321 +mp_cmp_int(a, z) - compare a <=> z, z is a signed long integer
1.322 +mp_isodd(a) - return nonzero if odd, zero otherwise
1.323 +mp_iseven(a) - return nonzero if even, zero otherwise
1.324 +
1.325 +
1.326 +Modular Arithmetic
1.327 +------------------
1.328 +
1.329 +Modular variations of the basic arithmetic functions are also
1.330 +supported. These are available if the MP_MODARITH parameter in
1.331 +mpi-config.h is turned on (it is by default). The modular arithmetic
1.332 +functions are:
1.333 +
1.334 +mp_mod(a, m, c) - compute c = a (mod m), 0 <= c < m
1.335 +mp_mod_d(a, d, c) - compute c = a (mod d), 0 <= c < d (see below)
1.336 +mp_addmod(a, b, m, c) - compute c = (a + b) mod m
1.337 +mp_submod(a, b, m, c) - compute c = (a - b) mod m
1.338 +mp_mulmod(a, b, m, c) - compute c = (a * b) mod m
1.339 +mp_sqrmod(a, m, c) - compute c = (a * a) mod m
1.340 +mp_exptmod(a, b, m, c) - compute c = (a ** b) mod m
1.341 +mp_exptmod_d(a, d, m, c)- compute c = (a ** d) mod m
1.342 +
1.343 +The mp_sqr() function squares its input argument. A call to mp_sqr(a,
1.344 +c) is identical in meaning to mp_mul(a, a, c); however, if the
1.345 +MP_SQUARE variable is set true in mpi-config.h (see below), then it
1.346 +will be implemented with a different algorithm, that is supposed to
1.347 +take advantage of the redundant computation that takes place during
1.348 +squaring. Unfortunately, some compilers result in worse performance
1.349 +on this code, so you can change the behaviour at will. There is a
1.350 +utility program "mulsqr.c" that lets you test which does better on
1.351 +your system.
1.352 +
1.353 +The mp_sqrmod() function is analogous to the mp_sqr() function; it
1.354 +uses the mp_sqr() function rather than mp_mul(), and then performs the
1.355 +modular reduction. This probably won't help much unless you are doing
1.356 +a lot of them.
1.357 +
1.358 +See the file 'square.txt' for a synopsis of the algorithm used.
1.359 +
1.360 +Note: The mp_mod_d() function computes a modular reduction around
1.361 +---- a single digit d. The result is a single digit c.
1.362 +
1.363 +Because an inverse is defined for a (mod m) if and only if (a, m) = 1
1.364 +(that is, if a and m are relatively prime), mp_invmod() may not be
1.365 +able to compute an inverse for the arguments. In this case, it
1.366 +returns the value MP_UNDEF, and does not modify c. If an inverse is
1.367 +defined, however, it returns MP_OKAY, and sets c to the value of the
1.368 +inverse (mod m).
1.369 +
1.370 +See the file 'redux.txt' for a description of the modular reduction
1.371 +algorithm used by mp_exptmod().
1.372 +
1.373 +
1.374 +Greatest Common Divisor
1.375 +-----------------------
1.376 +
1.377 +If The greates common divisor of two values can be found using one of the
1.378 +following functions:
1.379 +
1.380 +mp_gcd(a, b, c) - compute c = (a, b) using binary algorithm
1.381 +mp_lcm(a, b, c) - compute c = [a, b] = ab / (a, b)
1.382 +mp_xgcd(a, b, g, x, y) - compute g, x, y so that ax + by = g = (a, b)
1.383 +
1.384 +Also provided is a function to compute modular inverses, if they
1.385 +exist:
1.386 +
1.387 +mp_invmod(a, m, c) - compute c = a^-1 (mod m), if it exists
1.388 +
1.389 +The function mp_xgcd() computes the greatest common divisor, and also
1.390 +returns values of x and y satisfying Bezout's identity. This is used
1.391 +by mp_invmod() to find modular inverses. However, if you do not need
1.392 +these values, you will find that mp_gcd() is MUCH more efficient,
1.393 +since it doesn't need all the intermediate values that mp_xgcd()
1.394 +requires in order to compute x and y.
1.395 +
1.396 +The mp_gcd() (and mp_xgcd()) functions use the binary (extended) GCD
1.397 +algorithm due to Josef Stein.
1.398 +
1.399 +
1.400 +Input & Output Functions
1.401 +------------------------
1.402 +
1.403 +The following basic I/O routines are provided. These are present at
1.404 +all times:
1.405 +
1.406 +mp_read_radix(mp, str, r) - convert a string in radix r to an mp_int
1.407 +mp_read_raw(mp, s, len) - convert a string of bytes to an mp_int
1.408 +mp_radix_size(mp, r) - return length of buffer needed by mp_toradix()
1.409 +mp_raw_size(mp) - return length of buffer needed by mp_toraw()
1.410 +mp_toradix(mp, str, r) - convert an mp_int to a string of radix r
1.411 + digits
1.412 +mp_toraw(mp, str) - convert an mp_int to a string of bytes
1.413 +mp_tovalue(ch, r) - convert ch to its value when taken as
1.414 + a radix r digit, or -1 if invalid
1.415 +mp_strerror(err) - get a string describing mp_err value 'err'
1.416 +
1.417 +If you compile the MPI library with MP_IOFUNC defined, you will also
1.418 +have access to the following additional I/O function:
1.419 +
1.420 +mp_print(mp, ofp) - print an mp_int as text to output stream ofp
1.421 +
1.422 +Note that mp_radix_size() returns a size in bytes guaranteed to be AT
1.423 +LEAST big enough for the digits output by mp_toradix(). Because it
1.424 +uses an approximation technique to figure out how many digits will be
1.425 +needed, it may return a figure which is larger than necessary. Thus,
1.426 +the caller should not rely on the value to determine how many bytes
1.427 +will actually be written by mp_toradix(). The string mp_toradix()
1.428 +creates will be NUL terminated, so the standard C library function
1.429 +strlen() should be able to ascertain this for you, if you need it.
1.430 +
1.431 +The mp_read_radix() and mp_toradix() functions support bases from 2 to
1.432 +64 inclusive. If you require more general radix conversion facilities
1.433 +than this, you will need to write them yourself (that's why mp_div_d()
1.434 +is provided, after all).
1.435 +
1.436 +Note: mp_read_radix() will accept as digits either capital or
1.437 +---- lower-case letters. However, the current implementation of
1.438 + mp_toradix() only outputs upper-case letters, when writing
1.439 + bases betwee 10 and 36. The underlying code supports using
1.440 + lower-case letters, but the interface stub does not have a
1.441 + selector for it. You can add one yourself if you think it
1.442 + is worthwhile -- I do not. Bases from 36 to 64 use lower-
1.443 + case letters as distinct from upper-case. Bases 63 and
1.444 + 64 use the characters '+' and '/' as digits.
1.445 +
1.446 + Note also that compiling with MP_IOFUNC defined will cause
1.447 + inclusion of <stdio.h>, so if you are trying to write code
1.448 + which does not depend on the standard C library, you will
1.449 + probably want to avoid this option. This is needed because
1.450 + the mp_print() function takes a standard library FILE * as
1.451 + one of its parameters, and uses the fprintf() function.
1.452 +
1.453 +The mp_toraw() function converts the integer to a sequence of bytes,
1.454 +in big-endian ordering (most-significant byte first). Assuming your
1.455 +bytes are 8 bits wide, this corresponds to base 256. The sign is
1.456 +encoded as a single leading byte, whose value is 0 for zero or
1.457 +positive values, or 1 for negative values. The mp_read_raw() function
1.458 +reverses this process -- it takes a buffer of bytes, interprets the
1.459 +first as a sign indicator (0 = zero/positive, nonzero = negative), and
1.460 +the rest as a sequence of 1-byte digits in big-endian ordering.
1.461 +
1.462 +The mp_raw_size() function returns the exact number of bytes required
1.463 +to store the given integer in "raw" format (as described in the
1.464 +previous paragraph). Zero is returned in case of error; a valid
1.465 +integer will require at least three bytes of storage.
1.466 +
1.467 +In previous versions of the MPI library, an "external representation
1.468 +format" was supported. This was removed, however, because I found I
1.469 +was never using it, it was not as portable as I would have liked, and
1.470 +I decided it was a waste of space.
1.471 +
1.472 +
1.473 +Other Functions
1.474 +---------------
1.475 +
1.476 +The files 'mpprime.h' and 'mpprime.c' define some routines which are
1.477 +useful for divisibility testing and probabilistic primality testing.
1.478 +The routines defined are:
1.479 +
1.480 +mpp_divis(a, b) - is a divisible by b?
1.481 +mpp_divis_d(a, d) - is a divisible by digit d?
1.482 +mpp_random(a) - set a to random value at current precision
1.483 +mpp_random_size(a, prec) - set a to random value at given precision
1.484 +
1.485 +Note: The mpp_random() and mpp_random_size() functions use the C
1.486 +---- library's rand() function to generate random values. It is
1.487 + up to the caller to seed this generator before it is called.
1.488 + These functions are not suitable for generating quantities
1.489 + requiring cryptographic-quality randomness; they are intended
1.490 + primarily for use in primality testing.
1.491 +
1.492 + Note too that the MPI library does not call srand(), so your
1.493 + application should do this, if you ever want the sequence
1.494 + to change.
1.495 +
1.496 +mpp_divis_vector(a, v, s, w) - is a divisible by any of the s digits
1.497 + in v? If so, let w be the index of
1.498 + that digit
1.499 +
1.500 +mpp_divis_primes(a, np) - is a divisible by any of the first np
1.501 + primes? If so, set np to the prime
1.502 + which divided a.
1.503 +
1.504 +mpp_fermat(a, d) - test if w^a = w (mod a). If so,
1.505 + returns MP_YES, otherwise MP_NO.
1.506 +
1.507 +mpp_pprime(a, nt) - perform nt iterations of the Rabin-
1.508 + Miller probabilistic primality test
1.509 + on a. Returns MP_YES if all tests
1.510 + passed, or MP_NO if any test fails.
1.511 +
1.512 +The mpp_fermat() function works based on Fermat's little theorem, a
1.513 +consequence of which is that if p is a prime, and (w, p) = 1, then:
1.514 +
1.515 + w^p = w (mod p)
1.516 +
1.517 +Put another way, if w^p != w (mod p), then p is not prime. The test
1.518 +is expensive to compute, but it helps to quickly eliminate an enormous
1.519 +class of composite numbers prior to Rabin-Miller testing.
1.520 +
1.521 +Building the Library
1.522 +--------------------
1.523 +
1.524 +The MPI library is designed to be as self-contained as possible. You
1.525 +should be able to compile it with your favourite ANSI C compiler, and
1.526 +link it into your program directly. If you are on a Unix system using
1.527 +the GNU C compiler (gcc), the following should work:
1.528 +
1.529 +% gcc -ansi -pedantic -Wall -O2 -c mpi.c
1.530 +
1.531 +The file 'mpi-config.h' defines several configurable parameters for
1.532 +the library, which you can adjust to suit your application. At the
1.533 +time of this writing, the available options are:
1.534 +
1.535 +MP_IOFUNC - Define true to include the mp_print() function,
1.536 + which is moderately useful for debugging. This
1.537 + implicitly includes <stdio.h>.
1.538 +
1.539 +MP_MODARITH - Define true to include the modular arithmetic
1.540 + functions. If you don't need modular arithmetic
1.541 + in your application, you can set this to zero to
1.542 + leave out all the modular routines.
1.543 +
1.544 +MP_NUMTH - Define true to include number theoretic functions
1.545 + such as mp_gcd(), mp_lcm(), and mp_invmod().
1.546 +
1.547 +MP_LOGTAB - If true, the file "logtab.h" is included, which
1.548 + is basically a static table of base 2 logarithms.
1.549 + These are used to compute how big the buffers for
1.550 + radix conversion need to be. If you set this false,
1.551 + the library includes <math.h> and uses log(). This
1.552 + typically forces you to link against math libraries.
1.553 +
1.554 +MP_MEMSET - If true, use memset() to zero buffers. If you run
1.555 + into weird alignment related bugs, set this to zero
1.556 + and an explicit loop will be used.
1.557 +
1.558 +MP_MEMCPY - If true, use memcpy() to copy buffers. If you run
1.559 + into weird alignment bugs, set this to zero and an
1.560 + explicit loop will be used.
1.561 +
1.562 +MP_CRYPTO - If true, whenever arrays of digits are free'd, they
1.563 + are zeroed first. This is useful if you're using
1.564 + the library in a cryptographic environment; however,
1.565 + it does add overhead to each free operation. For
1.566 + performance, if you don't care about zeroing your
1.567 + buffers, set this to false.
1.568 +
1.569 +MP_ARGCHK - Set to 0, 1, or 2. This defines how the argument
1.570 + checking macro, ARGCHK(), gets expanded. If this
1.571 + is set to zero, ARGCHK() expands to nothing; no
1.572 + argument checks are performed. If this is 1, the
1.573 + ARGCHK() macro expands to code that returns MP_BADARG
1.574 + or similar at runtime. If it is 2, ARGCHK() expands
1.575 + to an assert() call that aborts the program on a
1.576 + bad input.
1.577 +
1.578 +MP_DEBUG - Turns on debugging output. This is probably not at
1.579 + all useful unless you are debugging the library. It
1.580 + tends to spit out a LOT of output.
1.581 +
1.582 +MP_DEFPREC - The default precision of a newly-created mp_int, in
1.583 + digits. The precision can be changed at runtime by
1.584 + the mp_set_prec() function, but this is its initial
1.585 + value.
1.586 +
1.587 +MP_SQUARE - If this is set to a nonzero value, the mp_sqr()
1.588 + function will use an alternate algorithm that takes
1.589 + advantage of the redundant inner product computation
1.590 + when both multiplicands are identical. Unfortunately,
1.591 + with some compilers this is actually SLOWER than just
1.592 + calling mp_mul() with the same argument twice. So
1.593 + if you set MP_SQUARE to zero, mp_sqr() will be expan-
1.594 + ded into a call to mp_mul(). This applies to all
1.595 + the uses of mp_sqr(), including mp_sqrmod() and the
1.596 + internal calls to s_mp_sqr() inside mpi.c
1.597 +
1.598 + The program 'mulsqr' (mulsqr.c) can be used to test
1.599 + which works best for your configuration. Set up the
1.600 + CC and CFLAGS variables in the Makefile, then type:
1.601 +
1.602 + make mulsqr
1.603 +
1.604 + Invoke it with arguments similar to the following:
1.605 +
1.606 + mulsqr 25000 1024
1.607 +
1.608 + That is, 25000 products computed on 1024-bit values.
1.609 + The output will compare the two timings, and recommend
1.610 + a setting for MP_SQUARE. It is off by default.
1.611 +
1.612 +If you would like to use the mp_print() function (see above), be sure
1.613 +to define MP_IOFUNC in mpi-config.h. Many of the test drivers in the
1.614 +'tests' subdirectory expect this to be defined (although the test
1.615 +driver 'mpi-test' doesn't need it)
1.616 +
1.617 +The Makefile which comes with the library should take care of building
1.618 +the library for you, if you have set the CC and CFLAGS variables at
1.619 +the top of the file appropriately. By default, they are set up to
1.620 +use the GNU C compiler:
1.621 +
1.622 +CC=gcc
1.623 +CFLAGS=-ansi -pedantic -Wall -O2
1.624 +
1.625 +If all goes well, the library should compile without warnings using
1.626 +this combination. You should, of course, make whatever adjustments
1.627 +you find necessary.
1.628 +
1.629 +The MPI library distribution comes with several additional programs
1.630 +which are intended to demonstrate the use of the library, and provide
1.631 +a framework for testing it. There are a handful of test driver
1.632 +programs, in the files named 'mptest-X.c', where X is a digit. Also,
1.633 +there are some simple command-line utilities (in the 'utils'
1.634 +directory) for manipulating large numbers. These include:
1.635 +
1.636 +basecvt.c A radix-conversion program, supporting bases from
1.637 + 2 to 64 inclusive.
1.638 +
1.639 +bbsrand.c A BBS (quadratic residue) pseudo-random number
1.640 + generator. The file 'bbsrand.c' is just the driver
1.641 + for the program; the real code lives in the files
1.642 + 'bbs_rand.h' and 'bbs_rand.c'
1.643 +
1.644 +dec2hex.c Converts decimal to hexadecimal
1.645 +
1.646 +gcd.c Computes the greatest common divisor of two values.
1.647 + If invoked as 'xgcd', also computes constants x and
1.648 + y such that (a, b) = ax + by, in accordance with
1.649 + Bezout's identity.
1.650 +
1.651 +hex2dec.c Converts hexadecimal to decimal
1.652 +
1.653 +invmod.c Computes modular inverses
1.654 +
1.655 +isprime.c Performs the Rabin-Miller probabilistic primality
1.656 + test on a number. Values which fail this test are
1.657 + definitely composite, and those which pass are very
1.658 + likely to be prime (although there are no guarantees)
1.659 +
1.660 +lap.c Computes the order (least annihilating power) of
1.661 + a value v modulo m. Very dumb algorithm.
1.662 +
1.663 +primegen.c Generates large (probable) primes.
1.664 +
1.665 +prng.c A pseudo-random number generator based on the
1.666 + BBS generator code in 'bbs_rand.c'
1.667 +
1.668 +sieve.c Implements the Sieve of Eratosthenes, using a big
1.669 + bitmap, to generate a list of prime numbers.
1.670 +
1.671 +fact.c Computes the factorial of an arbitrary precision
1.672 + integer (iterative).
1.673 +
1.674 +exptmod.c Computes arbitrary precision modular exponentiation
1.675 + from the command line (exptmod a b m -> a^b (mod m))
1.676 +
1.677 +Most of these can be built from the Makefile that comes with the
1.678 +library. Try 'make tools', if your environment supports it.
1.679 +
1.680 +
1.681 +Testing the Library
1.682 +-------------------
1.683 +
1.684 +Automatic test vectors are included, in the form of a program called
1.685 +'mpi-test'. To build this program and run all the tests, simply
1.686 +invoke the shell script 'all-tests'. If all the tests pass, you
1.687 +should see a message:
1.688 +
1.689 + All tests passed
1.690 +
1.691 +If something went wrong, you'll get:
1.692 +
1.693 + One or more tests failed.
1.694 +
1.695 +If this happens, scan back through the preceding lines, to see which
1.696 +test failed. Any failure indicates a bug in the library, which needs
1.697 +to be fixed before it will give accurate results. If you get any such
1.698 +thing, please let me know, and I'll try to fix it. Please let me know
1.699 +what platform and compiler you were using, as well as which test
1.700 +failed. If a reason for failure was given, please send me that text
1.701 +as well.
1.702 +
1.703 +If you're on a system where the standard Unix build tools don't work,
1.704 +you can build the 'mpi-test' program manually, and run it by hand.
1.705 +This is tedious and obnoxious, sorry.
1.706 +
1.707 +Further manual testing can be performed by building the manual testing
1.708 +programs, whose source is found in the 'tests' subdirectory. Each
1.709 +test is in a source file called 'mptest-X.c'. The Makefile contains a
1.710 +target to build all of them at once:
1.711 +
1.712 + make tests
1.713 +
1.714 +Read the comments at the top of each source file to see what the
1.715 +driver is supposed to test. You probably don't need to do this; these
1.716 +programs were only written to help me as I was developing the library.
1.717 +
1.718 +The relevant files are:
1.719 +
1.720 +mpi-test.c The source for the test driver
1.721 +
1.722 +make-test-arrays A Perl script to generate some of the internal
1.723 + data structures used by mpi-test.c
1.724 +
1.725 +test-arrays.txt The source file for make-test-arrays
1.726 +
1.727 +all-tests A Bourne shell script which runs all the
1.728 + tests in the mpi-test suite
1.729 +
1.730 +Running 'make mpi-test' should build the mpi-test program. If you
1.731 +cannot use make, here is what needs to be done:
1.732 +
1.733 +(1) Use 'make-test-arrays' to generate the file 'test-info.c' from
1.734 + the 'test-arrays.txt' file. Since Perl can be found everywhere,
1.735 + this should be no trouble. Under Unix, this looks like:
1.736 +
1.737 + make-test-arrays test-arrays.txt > test-info.c
1.738 +
1.739 +(2) Build the MPI library:
1.740 +
1.741 + gcc -ansi -pedantic -Wall -c mpi.c
1.742 +
1.743 +(3) Build the mpi-test program:
1.744 +
1.745 + gcc -ansi -pedantic -Wall -o mpi-test mpi.o mpi-test.c
1.746 +
1.747 +When you've got mpi-test, you can use 'all-tests' to run all the tests
1.748 +made available by mpi-test. If any of them fail, there should be a
1.749 +diagnostic indicating what went wrong. These are fairly high-level
1.750 +diagnostics, and won't really help you debug the problem; they're
1.751 +simply intended to help you isolate which function caused the problem.
1.752 +If you encounter a problem of this sort, feel free to e-mail me, and I
1.753 +will certainly attempt to help you debug it.
1.754 +
1.755 +Note: Several of the tests hard-wired into 'mpi-test' operate under
1.756 +---- the assumption that you are using at least a 16-bit mp_digit
1.757 + type. If that is not true, several tests might fail, because
1.758 + of range problems with the maximum digit value.
1.759 +
1.760 + If you are using an 8-bit digit, you will also need to
1.761 + modify the code for mp_read_raw(), which assumes that
1.762 + multiplication by 256 can be done with mp_mul_d(), a
1.763 + fact that fails when DIGIT_MAX is 255. You can replace
1.764 + the call with s_mp_lshd(), which will give you the same
1.765 + effect, and without doing as much work. :)
1.766 +
1.767 +Acknowledgements:
1.768 +----------------
1.769 +
1.770 +The algorithms used in this library were drawn primarily from Volume
1.771 +2 of Donald Knuth's magnum opus, _The Art of Computer Programming_,
1.772 +"Semi-Numerical Methods". Barrett's algorithm for modular reduction
1.773 +came from Menezes, Oorschot, and Vanstone's _Handbook of Applied
1.774 +Cryptography_, Chapter 14.
1.775 +
1.776 +Thanks are due to Tom St. Denis, for finding an obnoxious sign-related
1.777 +bug in mp_read_raw() that made things break on platforms which use
1.778 +signed chars.
1.779 +
1.780 +About the Author
1.781 +----------------
1.782 +
1.783 +This software was written by Michael J. Fromberger. You can contact
1.784 +the author as follows:
1.785 +
1.786 +E-mail: <sting@linguist.dartmouth.edu>
1.787 +
1.788 +Postal: 8000 Cummings Hall, Thayer School of Engineering
1.789 + Dartmouth College, Hanover, New Hampshire, USA
1.790 +
1.791 +PGP key: http://linguist.dartmouth.edu/~sting/keys/mjf.html
1.792 + 9736 188B 5AFA 23D6 D6AA BE0D 5856 4525 289D 9907
1.793 +
1.794 +Last updated: 16-Jan-2000
