     Arithmetic(3)                                                 Arithmetic(3)
                                    11 March 1990

     NAME
          arithmetic, Zadd, Zsub, Zminus, Zmult, Zdivalg, Zgcd, Zeq, Zlessoreq,
          Collect, Showme, Shcopy, Size, Constant, Initial - arithmetic with
          arbitrary length integers or polynomials

     SYNOPSIS
          #include integer.h
          #include polynomial.h
          #include Ztools.h
          unsigned short *Zadd(a, b)
          unsigned short *a, *b;
          unsigned short *Zsub(a, b)
          unsigned short *a, *b;
          unsigned short *Zminus(a)
          unsigned short *a;
          unsigned short *Zmult(a, b)
          unsigned short *a, *b;
          unsigned short *Zdivalg(a, b, r)
          unsigned short *a, *b, *r;
          void Zgcd(a, b, g, aa, bb)
          unsigned short *a, *b, *g;
          unsigned short *aa, *bb;
          char Zeq(a, b)
          unsigned short *a, *b;
          char Zlessoreq(a, b)
          unsigned short *a, *b;
          void Initial(m)
          unsigned short m;
          char Collect(msg, a)
          char *msg;
          unsigned short *a;
          void Showme(msg, a)
          char *msg;
          unsigned short *a;
          void Fshowme(fp, msg, a)
          FILE *fp;
          char *msg;
          unsigned short *a;
          unsigned short *Constant(a)
          long a;
          void Shcopy(a, b)
          unsigned short *a, *b;
          unsigned short Size(a)
          unsigned short *a;
          void bailout(msg)
          char *msg;

     DESCRIPTION
          These routines provide a uniform interface for computations involving
          either arbitrary precision integers or polynomials over finite fields.
          Both integers and polynomials are stored in little-endian order as an

                                        - 1 -          Formatted:  July 11, 2000

     Arithmetic(3)                                                 Arithmetic(3)
                                    11 March 1990

          array of unsigned shorts. The value of the first short in the array is
          the offset of the most significant digit; in the case of polynomials,
          this is the highest degree coefficient, in the case of integers, it is
          a signbit.  These routines use the storage management package called
          "warehouse", consisting of the routines release(), capture(), and
          makeWH() to have enough storage available for their computations.
          Thus, any program which uses these routines must begin with a call to
          Initial() which makes available some prlminary scratch computation
          areas. In the case of polynomials, the parameter to Initial() is the
          modulus of the finite field over which the polynomials are to be
          computed.  Zadd(), Zsub(), and Zmult() return a pointer to a very long
          integer or polynomial which is the sum, difference, or product,
          respectively, of their arguments. Zminus() returns the negative of its
          argument.  Zdivalg() computes the quotient of the dividend a by the
          divisor b and returns it. If the value of ptr is not NULL, then the
          remainder is stored at that location. The conventions used by
          Zdivalg() are: in the case of integers, the remainder always has the
          same sign as the dividend, and in the case of polynomials, the
          quotient is always monic.  In both cases, the relation a = b q + r
          holds.  Zgcd() computes the greatest common divisor of a and b and
          stores it in the location pointed to by g. The values of a/g and b/g,
          are stored in aa and bb, respectively.  Zeq() returns a non-zero value
          if its arguments are equal, and zero otherwise.  Zlessoreq() returns a
          non-zero value if its first argument is less than or equal to its
          second argument, and zero otherwise.  Some additional utilities are
          supplied to make common treatment of integers and polynomials easier.
          Collect() is an input routine which prints its message msg on standard
          output and then reads an integer or polynomial and stores it at the
          location pointed to by a. Both integers and polynomials are entered in
          big-endian order. Different coefficients of polynomials are separated
          by whitespace (which means, in this case, any non-digit characters)
          and are reduced modulo m before being stored. Integers are entered in
          digits written to the base 2^16 = 65536 which are also separated by
          whitespace; they may be preceeded an optional sign. Note that, at this
          time, decimal input is not supported except for numbers whose size is
          less than 65536. Lines may be continued by using the ampersand
          character (&) at the end of a line.  Showme() is an output routine
          which writes its message to standard output and follows it by an
          integer or polynomial written with the same conventions as used by
          Collect(). Fshowme() is to Showme() as fprintf() is to printf().
          Constant() returns a properly formatted very long integer or
          polynomial with the value represented by its argument. The argument
          must have absolute value bounded by 2^16 = 65536. In general, the
          value of Constant() should be copied to a safe location, since it re-
          uses the same storage space.  Shcopy() copies the array of its first
          argument int the location pointed to by its second argument. It
          assumes that there is enough room at the second location; it is the
          programmer's responsibility to ensure that this is, in fact, the case.
          Note, for example, that the integer constant 1 takes up three memory
          locations: one for a description of how many digits it needs, one for
          the value, and one for the signbit.

                                        - 2 -          Formatted:  July 11, 2000

     Arithmetic(3)                                                 Arithmetic(3)
                                    11 March 1990

     LIBRARIES
          These routines are implemented in one of two ways. Those which are
          fundamentally different for integers and polynomials are written as
          separate functions, and compiled as separate libraries. Those which
          could conveniently be written as one function are compiled in yet a
          third library; the interface is handled via macro definitions in the
          header files. The standard way to write a routine which will work with
          either integers or polynomials is to put
          #ifdef INTEGERS
          #include integer.h
          #elif defined POLYNOMIALS
          #include polynomial.h
          #else
          some line to make the compiler complain
          #endif
          at the top of the relevant files, and then to have two separate
          compiliations cc -DINTEGERS ... -lZ -lU cc -DPOLYNOMIALS ... -lP -lU

     DIAGNOSTICS
          Illegal operations detected by these routines result in a call to a
          routine called bailout() which prints a message and then exits.

     FILES
          integer.h
          polynomial.h
          utility.h
          Ztools.h
          libP.a
          libZ.a
          libU.a

     SEE ALSO
          warehouse(3), rational(3), quadratic(3)

                                        - 3 -          Formatted:  July 11, 2000