PGP's library is quite portable, working on both big- and little-endian machines, as well as machines with both 16- and 32-bit integers. It can be compiled in a mode which relies only on C code, or it can be linked with an assembly language module customized for the particular target machine to provide higher speed. Assembly language modules ship with PGP for a variety of targets.

The library uses fixed-size buffers for its calculations. This means there is a ceiling on the size of the numbers which can be used. This ceiling is determined at compile time, though, so special applications can build the library with large ceilings if desired.

PGP's library and its source code in general is not public domain; it is copyrighted by Philip Zimmermann, reachable at < prz@acm.org> . PGP is released under licensing terms which, I believe, allow use of the source code for non-commercial purposes. It would be a good idea to talk to Phil before using the code in any product destined for widespread release.

Any module which will use the mp functions should also include mpilib.h. All of these modules will also have to be compiled with the -D flag(s) used by mpilib.c.

If you have one of these targets, add a -D flag for the symbol from the above list to your compile command line. For example, on an MS-DOS machine, add -DMSDOS to the command line. (Actually, in most cases these symbols will be automatically defined by the target's compiler or pre-processor. But it doesn't hurt to define them explicitly.) Then you should also assemble the corresponding assembly language file. For MS-DOS it is 8086.asm; the proper choice for the other targets should be obvious from the filenames. Link the assembly language object module along with mpilib's object module into your application.

If you don't have one of these targets, mpilib.c can be built in a "portable" mode which will implement all functions in C. To do this, define -DPORTABLE and -DMPORTABLE on the command line. In addition, if you are on a big-endian machine (such as a sparc or 68000-based machine), you must define -DHIGHFIRST as well. Little-endian machines don't need an explicit define for endianness.

In portable mode, PGP will default to 16-bit units. If your target has 32-bit ints, you can define -DUNIT32 to get considerably more efficient code.

Remember that these defines must be added to all modules which include mpilib.h, in addition to mpilib.c. (Note: in the PGP makefile you may also see other defines, -DDYN_ALLOC and -DSMALL_MEM. These are not relevant to the mp library and are not necessary for this application.)

A better choice is UPTON for the purposes of a general-purpose library. You should edit mpilib.h to have it define UPTON instead of SMITH for your particular target architecture if you are using one of the pre-defined targets. If you are building with -DPORTABLE, you can either edit mpilib.h to change the default choice, or you can define -DUPTON on the command line.

set_precision (MAX_UNIT_PRECISION);To use the mp library, include mpilib.h in your module. Multi-precision variables should be declared as follows:

unit temp[MAX_UNIT_PRECISION];This declares a variable "temp" suitable for holding a multi-precision value. I like to do:

typedef unit unitarr[MAX_UNIT_PRECISION]; unitarr temp;which has the same effect.

MP variables may either be declared locally or as global variables as with other types of C variables.

PGP's mp library functions need to be called with the address of a mp variable. Since mp variables are declared as arrays in C, this means you can just pass the variable name. For example, to add x2 to x1, you could do:

unitarr x1, x2; mp_add (x1, x2);mpilib.h defines unitptr as a pointer to a unit. If you write functions which take MP values as parameters these should be declared as unitptr's. For example, a function to add three numbers and return a result might be:

void mp_add3 (unitptr rslt, unitptr arg1, unitptr arg2, unitptr arg3) { mp_move (rslt, arg1); mp_add (rslt, arg2); mp_add (rslt, arg3); }Make sure you don't make the mistake of declaring a local and global variables as unitptrs and passing them to mp functions. You need to allocate space for them by declaring them as unit arrays.

unitarr rslt, arg1, arg2, m; stage_modulus (m); mp_modmult(rslt, arg1, arg2);If you are doing a series of multiplications with the same modulus you can call stage_modulus just once and then call mp_modmult repeatedly. Be aware that mp_modexp calls stage_modulus internally so that function will overwrite the saved modulus value.

PGP is missing a few functions that you would expect. It does not have modular addition and subtraction. These should basically do A+B and then test for the range 0..(M-1), and if out of range add or subtract M once to bring it back into range. Perhaps these will be added to a future version of PGP.

Some mp functions have parameters that are both inputs and outputs (e.g. mp_inc(r) increments r). In other cases, though, the inputs are separate from the outputs. In those cases you should not pass the same variable as both an input and an output parameter. For example, you should not do mp_mult (a, a, b) to get a *= b, because a is being used as both an input and an output parameter. Instead, you should do mp_mult (temp, a, b) and then mp_move (a, temp).

Here are some useful PGP mpilib functions and what they do. The MP numbers are r, r1, r2, etc; non-MP integers are i, j, etc.

- mp_move(r1,r2)
- r1 = r2
- mp_add(r1,r2)
- r1 += r2
- mp_sub(r1,r2)
- r1 -= r2
- mp_compare(r1,r2)
- -1,0,or 1 depending on (r1< r2),(r1=r2),(r1> r2)
- mp_mult(r1,r2,r3)
- r1 = r2 * r3;
- mp_udiv(rem,rquot,rdend,rdor)
- unsigned rdend/rdor;rem=remainder,rquot=quotient
- mp_div(rem,rquot,rdend,rdor)
- signed rdend/rdor; rem=remainder, rquot=quotient
- mp_mod(rem,rdend,rdor)
- rem = rdend % rdor (unsigned)
- mp_abs(r)
- r = absolute value of r
- mp_inc(r)
- r += 1
- mp_dec(r)
- r -= 1
- mp_neg(r)
- r = -r
- mp_square(r1,r2)
- r1 = r2 * r2
- msub(r,r1)
- if (r> =r1) r -= r1

- stage_modulus(rm)
- set rm as modulus for mp_modmult
- mp_modmult(rslt,r1,r2)
- rslt = r1 * r2 mod stage_modulus value
- mp_modsquare(r1,r2)
- r1 = r2 * r2 mod stage_modulus value
- mp_modexp(rslt,r1,r2,rm)
- rslt = (r1 to the power r2) mod rm

To get access to the more general I/O functions in mpiio.c you must compile it with -DDEBUG. This will allow you to call:

- str2reg(r,str)
- Convert string str to mp value r

- display_in_base(str,r,irad)
- Display string r in base irad, preceded by str

- mp_display(str,r)
- Display string r in hex, preceded by str

One function which is lacking is something to convert an mp value to a string in memory. display_in_base and mp_display always write to standard output. These routines can be fairly easily modified to output to an incrementing pointer (*bp++) to get this effect if necessary.

- mp_gcd(rslt,r1,r2)
- rslt = greatest common divisor of r1 and r2
- mp_inv(rslt,r1,r2)
- Compute rslt such that rslt*r1 mod r2 is 1
- nextprime(r)
- Finds the next prime above r, returns in r
- slowtest(r)
- True if r is a probable prime
- primetest(r)
- Sieve then slowtest r, true if probable prime

There are also some other calls in mpilib.c which I did not document above. They are somewhat lower-level, mostly, but they might be useful for some purposes. A little study of the code will reveal these routines.

Hal Finney

hal@rain.org

Hal Finney Home Page