1This Source Code Form is subject to the terms of the Mozilla Public
2License, v. 2.0. If a copy of the MPL was not distributed with this
3file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5About the MPI Library
6---------------------
7
8The files 'mpi.h' and 'mpi.c' define a simple, arbitrary precision
9signed integer arithmetic package. The implementation is not the most
10efficient possible, but the code is small and should be fairly easily
11portable to just about any machine that supports an ANSI C compiler,
12as long as it is capable of at least 16-bit arithmetic (but also see
13below for more on this).
14
15This library was written with an eye to cryptographic applications;
16thus, some care is taken to make sure that temporary values are not
17left lying around in memory when they are no longer in use. This adds
18some overhead for zeroing buffers before they are released back into
19the free pool; however, it gives you the assurance that there is only
20one copy of your important values residing in your process's address
21space at a time. Obviously, it is difficult to guarantee anything, in
22a pre-emptive multitasking environment, but this at least helps you
23keep a lid on the more obvious ways your data can get spread around in
24memory.
25
26
27Using the Library
28-----------------
29
30To use the MPI library in your program, you must include the header:
31
32#include "mpi.h"
33
34This header provides all the type and function declarations you'll
35need to use the library. Almost all the names defined by the library
36begin with the prefix 'mp_', so it should be easy to keep them from
37clashing with your program's namespace (he says, glibly, knowing full
38well there are always pathological cases).
39
40There are a few things you may want to configure about the library.
41By default, the MPI library uses an unsigned short for its digit type,
42and an unsigned int for its word type. The word type must be big
43enough to contain at least two digits, for the primitive arithmetic to
44work out. On my machine, a short is 2 bytes and an int is 4 bytes --
45but if you have 64-bit ints, you might want to use a 4-byte digit and
46an 8-byte word. I have tested the library using 1-byte digits and
472-byte words, as well. Whatever you choose to do, the things you need
48to change are:
49
50(1) The type definitions for mp_digit and mp_word.
51
52(2) The macro DIGIT_FMT which tells mp_print() how to display a
53 single digit. This is just a printf() format string, so you
54 can adjust it appropriately.
55
56(3) The macros DIGIT_MAX and MP_WORD_MAX, which specify the
57 largest value expressible in an mp_digit and an mp_word,
58 respectively.
59
60Both the mp_digit and mp_word should be UNSIGNED integer types. The
61code relies on having the full positive precision of the type used for
62digits and words.
63
64The remaining type definitions should be left alone, for the most
65part. The code in the library does not make any significant
66assumptions about the sizes of things, but there is little if any
67reason to change the other parameters, so I would recommend you leave
68them as you found them.
69
70The library comes with a Perl script, 'types.pl', which will scan your
71current Makefile settings, and attempt to find good definitions for
72these types. It relies on a Unix sort of build environment, so it
73probably won't work under MacOS or Windows, but it can be convenient
74if you're porting to a new flavour of Unix. Just run 'types.pl' at
75the command line, and it will spit out its results to the standard
76output.
77
78
79Conventions
80-----------
81
82Most functions in the library return a value of type mp_err. This
83permits the library to communicate success or various kinds of failure
84to the calling program. The return values currently defined are:
85
86 MP_OKAY - okay, operation succeeded, all's well
87 MP_YES - okay, the answer is yes (same as MP_OKAY)
88 MP_NO - okay, but answer is no (not MP_OKAY)
89 MP_MEM - operation ran out of memory
90 MP_RANGE - input parameter was out of range
91 MP_BADARG - an invalid input parameter was provided
92 MP_UNDEF - no output value is defined for this input
93
94The only function which currently uses MP_UNDEF is mp_invmod().
95Division by zero is undefined, but the division functions will return
96MP_RANGE for a zero divisor. MP_BADARG usually means you passed a
97bogus mp_int structure to the function. MP_YES and MP_NO are not used
98by the library itself; they're defined so you can use them in your own
99extensions.
100
101If you need a readable interpretation of these error codes in your
102program, you may also use the mp_strerror() function. This function
103takes an mp_err as input, and returns a pointer to a human-readable
104string describing the meaning of the error. These strings are stored
105as constants within the library, so the caller should not attempt to
106modify or free the memory associated with these strings.
107
108The library represents values in signed-magnitude format. Values
109strictly less than zero are negative, all others are considered
110positive (zero is positive by fiat). You can access the 'sign' member
111of the mp_int structure directly, but better is to use the mp_cmp_z()
112function, to find out which side of zero the value lies on.
113
114Most arithmetic functions have a single-digit variant, as well as the
115full arbitrary-precision. An mp_digit is an unsigned value between 0
116and DIGIT_MAX inclusive. The radix is available as RADIX. The number
117of bits in a given digit is given as DIGIT_BIT.
118
119Generally, input parameters are given before output parameters.
120Unless otherwise specified, any input parameter can be re-used as an
121output parameter, without confusing anything.
122
123The basic numeric type defined by the library is an mp_int. Virtually
124all the functions in the library take a pointer to an mp_int as one of
125their parameters. An explanation of how to create and use these
126structures follows. And so, without further ado...
127
128
129Initialization and Cleanup
130--------------------------
131
132The basic numeric type defined by the library is an 'mp_int'.
133However, it is not sufficient to simply declare a variable of type
134mp_int in your program. These variables also need to be initialized
135before they can be used, to allocate the internal storage they require
136for computation.
137
138This is done using one of the following functions:
139
140 mp_init(mp_int *mp);
141 mp_init_copy(mp_int *mp, mp_int *from);
142 mp_init_size(mp_int *mp, mp_size p);
143
144Each of these requires a pointer to a structure of type mp_int. The
145basic mp_init() simply initializes the mp_int to a default size, and
146sets its value to zero. If you would like to initialize a copy of an
147existing mp_int, use mp_init_copy(), where the 'from' parameter is the
148mp_int you'd like to make a copy of. The third function,
149mp_init_size(), permits you to specify how many digits of precision
150should be preallocated for your mp_int. This can help the library
151avoid unnecessary re-allocations later on.
152
153The default precision used by mp_init() can be retrieved using:
154
155 precision = mp_get_prec();
156
157This returns the number of digits that will be allocated. You can
158change this value by using:
159
160 mp_set_prec(unsigned int prec);
161
162Any positive value is acceptable -- if you pass zero, the default
163precision will be re-set to the compiled-in library default (this is
164specified in the header file 'mpi-config.h', and typically defaults to
1658 or 16).
166
167Just as you must allocate an mp_int before you can use it, you must
168clean up the structure when you are done with it. This is performed
169using the mp_clear() function. Remember that any mp_int that you
170create as a local variable in a function must be mp_clear()'d before
171that function exits, or else the memory allocated to that mp_int will
172be orphaned and unrecoverable.
173
174To set an mp_int to a given value, the following functions are given:
175
176 mp_set(mp_int *mp, mp_digit d);
177 mp_set_int(mp_int *mp, long z);
178
179The mp_set() function sets the mp_int to a single digit value, while
180mp_set_int() sets the mp_int to a signed long integer value.
181
182To set an mp_int to zero, use:
183
184 mp_zero(mp_int *mp);
185
186
187Copying and Moving
188------------------
189
190If you have two initialized mp_int's, and you want to copy the value
191of one into the other, use:
192
193 mp_copy(from, to)
194
195This takes care of clearing the old value of 'to', and copies the new
196value into it. If 'to' is not yet initialized, use mp_init_copy()
197instead (see above).
198
199Note: The library tries, whenever possible, to avoid allocating
200---- new memory. Thus, mp_copy() tries first to satisfy the needs
201 of the copy by re-using the memory already allocated to 'to'.
202 Only if this proves insufficient will mp_copy() actually
203 allocate new memory.
204
205 For this reason, if you know a priori that 'to' has enough
206 available space to hold 'from', you don't need to check the
207 return value of mp_copy() for memory failure. The USED()
208 macro tells you how many digits are used by an mp_int, and
209 the ALLOC() macro tells you how many are allocated.
210
211If you have two initialized mp_int's, and you want to exchange their
212values, use:
213
214 mp_exch(a, b)
215
216This is better than using mp_copy() with a temporary, since it will
217not (ever) touch the memory allocator -- it just swaps the exact
218contents of the two structures. The mp_exch() function cannot fail;
219if you pass it an invalid structure, it just ignores it, and does
220nothing.
221
222
223Basic Arithmetic
224----------------
225
226Once you have initialized your integers, you can operate on them. The
227basic arithmetic functions on full mp_int values are:
228
229mp_add(a, b, c) - computes c = a + b
230mp_sub(a, b, c) - computes c = a - b
231mp_mul(a, b, c) - computes c = a * b
232mp_sqr(a, b) - computes b = a * a
233mp_div(a, b, q, r) - computes q, r such that a = bq + r
234mp_div_2d(a, d, q, r) - computes q = a / 2^d, r = a % 2^d
235mp_expt(a, b, c) - computes c = a ** b
236mp_2expt(a, k) - computes a = 2^k
237
238The mp_div_2d() function efficiently computes division by powers of
239two. Either the q or r parameter may be NULL, in which case that
240portion of the computation will be discarded.
241
242The algorithms used for some of the computations here are described in
243the following files which are included with this distribution:
244
245mul.txt Describes the multiplication algorithm
246div.txt Describes the division algorithm
247expt.txt Describes the exponentiation algorithm
248sqrt.txt Describes the square-root algorithm
249square.txt Describes the squaring algorithm
250
251There are single-digit versions of most of these routines, as well.
252In the following prototypes, 'd' is a single mp_digit:
253
254mp_add_d(a, d, c) - computes c = a + d
255mp_sub_d(a, d, c) - computes c = a - d
256mp_mul_d(a, d, c) - computes c = a * d
257mp_mul_2(a, c) - computes c = a * 2
258mp_div_d(a, d, q, r) - computes q, r such that a = bq + r
259mp_div_2(a, c) - computes c = a / 2
260mp_expt_d(a, d, c) - computes c = a ** d
261
262The mp_mul_2() and mp_div_2() functions take advantage of the internal
263representation of an mp_int to do multiplication by two more quickly
264than mp_mul_d() would. Other basic functions of an arithmetic variety
265include:
266
267mp_zero(a) - assign 0 to a
268mp_neg(a, c) - negate a: c = -a
269mp_abs(a, c) - absolute value: c = |a|
270
271
272Comparisons
273-----------
274
275Several comparison functions are provided. Each of these, unless
276otherwise specified, returns zero if the comparands are equal, < 0 if
277the first is less than the second, and > 0 if the first is greater
278than the second:
279
280mp_cmp_z(a) - compare a <=> 0
281mp_cmp_d(a, d) - compare a <=> d, d is a single digit
282mp_cmp(a, b) - compare a <=> b
283mp_cmp_mag(a, b) - compare |a| <=> |b|
284mp_isodd(a) - return nonzero if odd, zero otherwise
285mp_iseven(a) - return nonzero if even, zero otherwise
286
287
288Modular Arithmetic
289------------------
290
291Modular variations of the basic arithmetic functions are also
292supported. These are available if the MP_MODARITH parameter in
293mpi-config.h is turned on (it is by default). The modular arithmetic
294functions are:
295
296mp_mod(a, m, c) - compute c = a (mod m), 0 <= c < m
297mp_mod_d(a, d, c) - compute c = a (mod d), 0 <= c < d (see below)
298mp_addmod(a, b, m, c) - compute c = (a + b) mod m
299mp_submod(a, b, m, c) - compute c = (a - b) mod m
300mp_mulmod(a, b, m, c) - compute c = (a * b) mod m
301mp_sqrmod(a, m, c) - compute c = (a * a) mod m
302mp_exptmod(a, b, m, c) - compute c = (a ** b) mod m
303mp_exptmod_d(a, d, m, c)- compute c = (a ** d) mod m
304
305The mp_sqr() function squares its input argument. A call to mp_sqr(a,
306c) is identical in meaning to mp_mul(a, a, c); however, if the
307MP_SQUARE variable is set true in mpi-config.h (see below), then it
308will be implemented with a different algorithm, that is supposed to
309take advantage of the redundant computation that takes place during
310squaring. Unfortunately, some compilers result in worse performance
311on this code, so you can change the behaviour at will. There is a
312utility program "mulsqr.c" that lets you test which does better on
313your system.
314
315The mp_sqrmod() function is analogous to the mp_sqr() function; it
316uses the mp_sqr() function rather than mp_mul(), and then performs the
317modular reduction. This probably won't help much unless you are doing
318a lot of them.
319
320See the file 'square.txt' for a synopsis of the algorithm used.
321
322Note: The mp_mod_d() function computes a modular reduction around
323---- a single digit d. The result is a single digit c.
324
325Because an inverse is defined for a (mod m) if and only if (a, m) = 1
326(that is, if a and m are relatively prime), mp_invmod() may not be
327able to compute an inverse for the arguments. In this case, it
328returns the value MP_UNDEF, and does not modify c. If an inverse is
329defined, however, it returns MP_OKAY, and sets c to the value of the
330inverse (mod m).
331
332See the file 'redux.txt' for a description of the modular reduction
333algorithm used by mp_exptmod().
334
335
336Greatest Common Divisor
337-----------------------
338
339If The greates common divisor of two values can be found using one of the
340following functions:
341
342mp_gcd(a, b, c) - compute c = (a, b) using binary algorithm
343mp_lcm(a, b, c) - compute c = [a, b] = ab / (a, b)
344mp_xgcd(a, b, g, x, y) - compute g, x, y so that ax + by = g = (a, b)
345
346Also provided is a function to compute modular inverses, if they
347exist:
348
349mp_invmod(a, m, c) - compute c = a^-1 (mod m), if it exists
350
351The function mp_xgcd() computes the greatest common divisor, and also
352returns values of x and y satisfying Bezout's identity. This is used
353by mp_invmod() to find modular inverses. However, if you do not need
354these values, you will find that mp_gcd() is MUCH more efficient,
355since it doesn't need all the intermediate values that mp_xgcd()
356requires in order to compute x and y.
357
358The mp_gcd() (and mp_xgcd()) functions use the binary (extended) GCD
359algorithm due to Josef Stein.
360
361
362Input & Output Functions
363------------------------
364
365The following basic I/O routines are provided. These are present at
366all times:
367
368mp_read_radix(mp, str, r) - convert a string in radix r to an mp_int
369mp_read_raw(mp, s, len) - convert a string of bytes to an mp_int
370mp_radix_size(mp, r) - return length of buffer needed by mp_toradix()
371mp_raw_size(mp) - return length of buffer needed by mp_toraw()
372mp_toradix(mp, str, r) - convert an mp_int to a string of radix r
373 digits
374mp_toraw(mp, str) - convert an mp_int to a string of bytes
375mp_tovalue(ch, r) - convert ch to its value when taken as
376 a radix r digit, or -1 if invalid
377mp_strerror(err) - get a string describing mp_err value 'err'
378
379If you compile the MPI library with MP_IOFUNC defined, you will also
380have access to the following additional I/O function:
381
382mp_print(mp, ofp) - print an mp_int as text to output stream ofp
383
384Note that mp_radix_size() returns a size in bytes guaranteed to be AT
385LEAST big enough for the digits output by mp_toradix(). Because it
386uses an approximation technique to figure out how many digits will be
387needed, it may return a figure which is larger than necessary. Thus,
388the caller should not rely on the value to determine how many bytes
389will actually be written by mp_toradix(). The string mp_toradix()
390creates will be NUL terminated, so the standard C library function
391strlen() should be able to ascertain this for you, if you need it.
392
393The mp_read_radix() and mp_toradix() functions support bases from 2 to
39464 inclusive. If you require more general radix conversion facilities
395than this, you will need to write them yourself (that's why mp_div_d()
396is provided, after all).
397
398Note: mp_read_radix() will accept as digits either capital or
399---- lower-case letters. However, the current implementation of
400 mp_toradix() only outputs upper-case letters, when writing
401 bases betwee 10 and 36. The underlying code supports using
402 lower-case letters, but the interface stub does not have a
403 selector for it. You can add one yourself if you think it
404 is worthwhile -- I do not. Bases from 36 to 64 use lower-
405 case letters as distinct from upper-case. Bases 63 and
406 64 use the characters '+' and '/' as digits.
407
408 Note also that compiling with MP_IOFUNC defined will cause
409 inclusion of <stdio.h>, so if you are trying to write code
410 which does not depend on the standard C library, you will
411 probably want to avoid this option. This is needed because
412 the mp_print() function takes a standard library FILE * as
413 one of its parameters, and uses the fprintf() function.
414
415The mp_toraw() function converts the integer to a sequence of bytes,
416in big-endian ordering (most-significant byte first). Assuming your
417bytes are 8 bits wide, this corresponds to base 256. The sign is
418encoded as a single leading byte, whose value is 0 for zero or
419positive values, or 1 for negative values. The mp_read_raw() function
420reverses this process -- it takes a buffer of bytes, interprets the
421first as a sign indicator (0 = zero/positive, nonzero = negative), and
422the rest as a sequence of 1-byte digits in big-endian ordering.
423
424The mp_raw_size() function returns the exact number of bytes required
425to store the given integer in "raw" format (as described in the
426previous paragraph). Zero is returned in case of error; a valid
427integer will require at least three bytes of storage.
428
429In previous versions of the MPI library, an "external representation
430format" was supported. This was removed, however, because I found I
431was never using it, it was not as portable as I would have liked, and
432I decided it was a waste of space.
433
434
435Other Functions
436---------------
437
438The files 'mpprime.h' and 'mpprime.c' define some routines which are
439useful for divisibility testing and probabilistic primality testing.
440The routines defined are:
441
442mpp_divis(a, b) - is a divisible by b?
443mpp_divis_d(a, d) - is a divisible by digit d?
444mpp_random(a) - set a to random value at current precision
445mpp_random_size(a, prec) - set a to random value at given precision
446
447Note: The mpp_random() and mpp_random_size() functions use the C
448---- library's rand() function to generate random values. It is
449 up to the caller to seed this generator before it is called.
450 These functions are not suitable for generating quantities
451 requiring cryptographic-quality randomness; they are intended
452 primarily for use in primality testing.
453
454 Note too that the MPI library does not call srand(), so your
455 application should do this, if you ever want the sequence
456 to change.
457
458mpp_divis_vector(a, v, s, w) - is a divisible by any of the s digits
459 in v? If so, let w be the index of
460 that digit
461
462mpp_divis_primes(a, np) - is a divisible by any of the first np
463 primes? If so, set np to the prime
464 which divided a.
465
466mpp_fermat(a, d) - test if w^a = w (mod a). If so,
467 returns MP_YES, otherwise MP_NO.
468
469mpp_pprime(a, nt) - perform nt iterations of the Rabin-
470 Miller probabilistic primality test
471 on a. Returns MP_YES if all tests
472 passed, or MP_NO if any test fails.
473
474The mpp_fermat() function works based on Fermat's little theorem, a
475consequence of which is that if p is a prime, and (w, p) = 1, then:
476
477 w^p = w (mod p)
478
479Put another way, if w^p != w (mod p), then p is not prime. The test
480is expensive to compute, but it helps to quickly eliminate an enormous
481class of composite numbers prior to Rabin-Miller testing.
482
483Building the Library
484--------------------
485
486The MPI library is designed to be as self-contained as possible. You
487should be able to compile it with your favourite ANSI C compiler, and
488link it into your program directly. If you are on a Unix system using
489the GNU C compiler (gcc), the following should work:
490
491% gcc -ansi -pedantic -Wall -O2 -c mpi.c
492
493The file 'mpi-config.h' defines several configurable parameters for
494the library, which you can adjust to suit your application. At the
495time of this writing, the available options are:
496
497MP_IOFUNC - Define true to include the mp_print() function,
498 which is moderately useful for debugging. This
499 implicitly includes <stdio.h>.
500
501MP_MODARITH - Define true to include the modular arithmetic
502 functions. If you don't need modular arithmetic
503 in your application, you can set this to zero to
504 leave out all the modular routines.
505
506MP_NUMTH - Define true to include number theoretic functions
507 such as mp_gcd(), mp_lcm(), and mp_invmod().
508
509MP_LOGTAB - If true, the file "logtab.h" is included, which
510 is basically a static table of base 2 logarithms.
511 These are used to compute how big the buffers for
512 radix conversion need to be. If you set this false,
513 the library includes <math.h> and uses log(). This
514 typically forces you to link against math libraries.
515
516MP_MEMSET - If true, use memset() to zero buffers. If you run
517 into weird alignment related bugs, set this to zero
518 and an explicit loop will be used.
519
520MP_MEMCPY - If true, use memcpy() to copy buffers. If you run
521 into weird alignment bugs, set this to zero and an
522 explicit loop will be used.
523
524MP_ARGCHK - Set to 0, 1, or 2. This defines how the argument
525 checking macro, ARGCHK(), gets expanded. If this
526 is set to zero, ARGCHK() expands to nothing; no
527 argument checks are performed. If this is 1, the
528 ARGCHK() macro expands to code that returns MP_BADARG
529 or similar at runtime. If it is 2, ARGCHK() expands
530 to an assert() call that aborts the program on a
531 bad input.
532
533MP_DEBUG - Turns on debugging output. This is probably not at
534 all useful unless you are debugging the library. It
535 tends to spit out a LOT of output.
536
537MP_DEFPREC - The default precision of a newly-created mp_int, in
538 digits. The precision can be changed at runtime by
539 the mp_set_prec() function, but this is its initial
540 value.
541
542MP_SQUARE - If this is set to a nonzero value, the mp_sqr()
543 function will use an alternate algorithm that takes
544 advantage of the redundant inner product computation
545 when both multiplicands are identical. Unfortunately,
546 with some compilers this is actually SLOWER than just
547 calling mp_mul() with the same argument twice. So
548 if you set MP_SQUARE to zero, mp_sqr() will be expan-
549 ded into a call to mp_mul(). This applies to all
550 the uses of mp_sqr(), including mp_sqrmod() and the
551 internal calls to s_mp_sqr() inside mpi.c
552
553 The program 'mulsqr' (mulsqr.c) can be used to test
554 which works best for your configuration. Set up the
555 CC and CFLAGS variables in the Makefile, then type:
556
557 make mulsqr
558
559 Invoke it with arguments similar to the following:
560
561 mulsqr 25000 1024
562
563 That is, 25000 products computed on 1024-bit values.
564 The output will compare the two timings, and recommend
565 a setting for MP_SQUARE. It is off by default.
566
567If you would like to use the mp_print() function (see above), be sure
568to define MP_IOFUNC in mpi-config.h. Many of the test drivers in the
569'tests' subdirectory expect this to be defined (although the test
570driver 'mpi-test' doesn't need it)
571
572The Makefile which comes with the library should take care of building
573the library for you, if you have set the CC and CFLAGS variables at
574the top of the file appropriately. By default, they are set up to
575use the GNU C compiler:
576
577CC=gcc
578CFLAGS=-ansi -pedantic -Wall -O2
579
580If all goes well, the library should compile without warnings using
581this combination. You should, of course, make whatever adjustments
582you find necessary.
583
584The MPI library distribution comes with several additional programs
585which are intended to demonstrate the use of the library, and provide
586a framework for testing it. There are a handful of test driver
587programs, in the files named 'mptest-X.c', where X is a digit. Also,
588there are some simple command-line utilities (in the 'utils'
589directory) for manipulating large numbers. These include:
590
591basecvt.c A radix-conversion program, supporting bases from
592 2 to 64 inclusive.
593
594bbsrand.c A BBS (quadratic residue) pseudo-random number
595 generator. The file 'bbsrand.c' is just the driver
596 for the program; the real code lives in the files
597 'bbs_rand.h' and 'bbs_rand.c'
598
599dec2hex.c Converts decimal to hexadecimal
600
601gcd.c Computes the greatest common divisor of two values.
602 If invoked as 'xgcd', also computes constants x and
603 y such that (a, b) = ax + by, in accordance with
604 Bezout's identity.
605
606hex2dec.c Converts hexadecimal to decimal
607
608invmod.c Computes modular inverses
609
610isprime.c Performs the Rabin-Miller probabilistic primality
611 test on a number. Values which fail this test are
612 definitely composite, and those which pass are very
613 likely to be prime (although there are no guarantees)
614
615lap.c Computes the order (least annihilating power) of
616 a value v modulo m. Very dumb algorithm.
617
618primegen.c Generates large (probable) primes.
619
620prng.c A pseudo-random number generator based on the
621 BBS generator code in 'bbs_rand.c'
622
623sieve.c Implements the Sieve of Eratosthenes, using a big
624 bitmap, to generate a list of prime numbers.
625
626fact.c Computes the factorial of an arbitrary precision
627 integer (iterative).
628
629exptmod.c Computes arbitrary precision modular exponentiation
630 from the command line (exptmod a b m -> a^b (mod m))
631
632Most of these can be built from the Makefile that comes with the
633library. Try 'make tools', if your environment supports it.
634
635
636Testing the Library
637-------------------
638
639Automatic test vectors are included, in the form of a program called
640'mpi-test'. To build this program and run all the tests, simply
641invoke the shell script 'all-tests'. If all the tests pass, you
642should see a message:
643
644 All tests passed
645
646If something went wrong, you'll get:
647
648 One or more tests failed.
649
650If this happens, scan back through the preceding lines, to see which
651test failed. Any failure indicates a bug in the library, which needs
652to be fixed before it will give accurate results. If you get any such
653thing, please let me know, and I'll try to fix it. Please let me know
654what platform and compiler you were using, as well as which test
655failed. If a reason for failure was given, please send me that text
656as well.
657
658If you're on a system where the standard Unix build tools don't work,
659you can build the 'mpi-test' program manually, and run it by hand.
660This is tedious and obnoxious, sorry.
661
662Further manual testing can be performed by building the manual testing
663programs, whose source is found in the 'tests' subdirectory. Each
664test is in a source file called 'mptest-X.c'. The Makefile contains a
665target to build all of them at once:
666
667 make tests
668
669Read the comments at the top of each source file to see what the
670driver is supposed to test. You probably don't need to do this; these
671programs were only written to help me as I was developing the library.
672
673The relevant files are:
674
675mpi-test.c The source for the test driver
676
677make-test-arrays A Perl script to generate some of the internal
678 data structures used by mpi-test.c
679
680test-arrays.txt The source file for make-test-arrays
681
682all-tests A Bourne shell script which runs all the
683 tests in the mpi-test suite
684
685Running 'make mpi-test' should build the mpi-test program. If you
686cannot use make, here is what needs to be done:
687
688(1) Use 'make-test-arrays' to generate the file 'test-info.c' from
689 the 'test-arrays.txt' file. Since Perl can be found everywhere,
690 this should be no trouble. Under Unix, this looks like:
691
692 make-test-arrays test-arrays.txt > test-info.c
693
694(2) Build the MPI library:
695
696 gcc -ansi -pedantic -Wall -c mpi.c
697
698(3) Build the mpi-test program:
699
700 gcc -ansi -pedantic -Wall -o mpi-test mpi.o mpi-test.c
701
702When you've got mpi-test, you can use 'all-tests' to run all the tests
703made available by mpi-test. If any of them fail, there should be a
704diagnostic indicating what went wrong. These are fairly high-level
705diagnostics, and won't really help you debug the problem; they're
706simply intended to help you isolate which function caused the problem.
707If you encounter a problem of this sort, feel free to e-mail me, and I
708will certainly attempt to help you debug it.
709
710Note: Several of the tests hard-wired into 'mpi-test' operate under
711---- the assumption that you are using at least a 16-bit mp_digit
712 type. If that is not true, several tests might fail, because
713 of range problems with the maximum digit value.
714
715 If you are using an 8-bit digit, you will also need to
716 modify the code for mp_read_raw(), which assumes that
717 multiplication by 256 can be done with mp_mul_d(), a
718 fact that fails when DIGIT_MAX is 255. You can replace
719 the call with s_mp_lshd(), which will give you the same
720 effect, and without doing as much work. :)
721
722Acknowledgements:
723----------------
724
725The algorithms used in this library were drawn primarily from Volume
7262 of Donald Knuth's magnum opus, _The Art of Computer Programming_,
727"Semi-Numerical Methods". Barrett's algorithm for modular reduction
728came from Menezes, Oorschot, and Vanstone's _Handbook of Applied
729Cryptography_, Chapter 14.
730
731Thanks are due to Tom St. Denis, for finding an obnoxious sign-related
732bug in mp_read_raw() that made things break on platforms which use
733signed chars.
734
735About the Author
736----------------
737
738This software was written by Michael J. Fromberger. You can contact
739the author as follows:
740
741E-mail: <sting@linguist.dartmouth.edu>
742
743Postal: 8000 Cummings Hall, Thayer School of Engineering
744 Dartmouth College, Hanover, New Hampshire, USA
745
746PGP key: http://linguist.dartmouth.edu/~sting/keys/mjf.html
747 9736 188B 5AFA 23D6 D6AA BE0D 5856 4525 289D 9907
748
749Last updated: 16-Jan-2000
750