lip.h

应用密码学这本书的源代码

#if 0
{
Copyright Arjen K. Lenstra, 1989-1997

			      free  L I P

                 l o n g   i n t e g e r   p a c k a g e

                            Arjen K. Lenstra

                               version 1.1

Introduction
============
This very long int package is supposed to be easy to use, portable, and
not too slow.  It should also not be hard to make it fast by converting
a few macros to your favorite assembly code.

This version has an include file lip.h that defines all functions
and their arguments for ANSI C and contains:

typedef long * verylong;

Older programs need not be changed to use this type.  It is added for
enhancing program readability.

As an example, the following program reads the decimal representation
of two arbitrary length signed integers a and b from stdin, computes
their product in c, and prints c in decimal on stdout, followed by a
newline:

        #include "lip.h"
        main()
        {
        /* declare verylong ints a, b, c */
                verylong a = 0;
                verylong b = 0;
                verylong c = 0;
        /*********************************\
        *   or declare them by
        *       long *a = 0, *b = 0, *c = 0
        \*********************************/
                zread(&a);      /* read a from stdin */
                zread(&b);      /* read b from stdin */
                zmul(a, b, &c); /* multiply a anb b, put result in c */
                zwriteln(c);    /* print c, followed by a newline */
        }

Sample input:

        7419043440758059956596 -60967068778579064460287972

with output:

        -452317331723962514217511611516823866219980863312

(To run this example, first produce lip.o:

	gcc -O -c lip.c

 where gcc is assumed to be your ansi-C compiler, and next

	gcc -O -o example1 example1.c lip.o -lm

 to get the executable example1.)

As you can see, very long ints a, b, and c are declared simply by

        verylong a = 0;
        verylong b = 0;
        verylong c = 0;

If a very long int is input to a function (like a and b in zmul(a, b, &c)),
just give its name as argument. Long ints that get new values in
a function (like a in zread(&a), b in zread(&b), c in zmul(a, b, &c))
are given by their address, which means that they are preceded by a &
in the function call.

As a slightly more challenging example, the following program starts
the random generator with a seed read from stdin, and attempts to
generate and print 5 probable primes of binary lengths 64, 80, 96, 112,
128:

        #include "lip.h"
        main()
        {
                verylong seed = 0;
                long  bl;
                verylong p = 0;

                zread(&seed);   /* get seed from stdin */
                zrstart(seed);  /* start the random generator */
                for (bl = 64; bl <= 128; bl += 16)
                {
                /* find prime of bl bits */
                        if (zrandomprime(bl, 5, &p, zrandomb))
                        {
                        /* refer to description below for the 5 */
                                printf("%3d bits: ", bl);
                                zwriteln(p);
                        }
                        else
                                printf("couldn`t find a %3d bit prime\n", bl);
                }
        }

Sample input:

        742434390077967024401578982882

with output:

	 64 bits: 10513989034112217947
	 80 bits: 775541835531627786320957
	 96 bits: 58185536691780358241291462137
	112 bits: 3464241483388970526627866839605371
	128 bits: 198790427312192931901507582677867621703



WARNING  for old users: some names have been changed.
=======  If zxxx is a function operating on very long ints, then there
         may be two variants of zxxx: zsxxx where one op the operands
         is an ordinary long, and zxxxs where all operands are ordinary
         longs. Compared to the previous version, the following
         functions are affected (with some other name changes as well):

                Old name        New name
                --------        --------
                ztimes2         z2mul
                zdivide2        z2div
                zsmulmod        zmulmods (there`s a new zsmulmod)
                zsinv           zinvs
                zsexp           zexpmods (there`s a new zsexp)
                zexps           zsexp
                zexpsmod        zsexpmod
                zexp2mod        z2expmod
                zssqrt          zsqrts
                zsodinv         zinvodds
                zsjacobi        zjacobis
                zrstart         zrstarts (there`s a new zrstart)
                zmont           zmontmul
                zmexp           zmontexp
                zmexp_m_ary     zmontexp_m_ary


         Some arguments of some functions have changed:
                zmulin          switched order
                zmakeodd        *verylong (**long) instead of verylong (*long)
                znegate         *verylong (**long) instead of verylong (*long)
                zcomposite      *verylong (**long) instead of verylong (*long)


Overview of available functions
===============================

  Basic arithmetic
  ----------------
        zstart, zsadd, zadd, zsub, zsubpos,
        zsmul, zmul, zmulin, zmul_plain, zsq, zsqin, zsq_plain,
        zsdiv, zdiv, zsmod, zmod

  Shifting and bit manipulation
  -----------------------------
        z2mul, z2div, z2mod, zlshift, zrshift, zmakeodd,
        zodd, znot, zand, zor, zxor, zslowbits, zlowbits,
        zshighbits, zhighbits, zweights, zweight, zcat,
	zbit, zgetbits, zsetbit, zswitchbit, zreverses,
	zreverse

  Comparison, signs, copying, logarithms
  --------------------------------------
        zscompare, zcompare, ziszero, zsign, zabs, znegate, zcopy, zswap
        z2logs, z2log, zln, zslog, zlog, zdlog

  Conversion
  ----------
        zzero, zone, zintoz, zuintoz, zultoz, ztoint, ztouint, ztoul,
        sztrtozbas, zstrtoz, zdoub, zsbastoz, zbastoz, zstobas, ztobas,
	zstosymbas, ztosymbas

  Non-modular exponentiation
  --------------------------
        zsexp, zexp, zsqrts, zsqrt, zroot, zispower

  Modular arithmetic
  ------------------
        zaddmod, zsubmod, zmulmods, zsmulmod, zmulmod, zsqmod, zdivmod,
        zinvmod, zexpmods, z2expmod, zsexpmod, zexpmod, zexpmod_m_ary,
        zdefault_m, zexpmod_doub1, zexpmod_doub2, zexpmod_doub3, zexpmod_doub,
        zmulmod26

  Montgomery modular arithmetic
  -----------------------------
        zmstart, zmfree, ztom, zmtoz, zmontadd, zmontsub, zsmontmul, zmontmul,
        zmontsq, zmontdiv, zmontinv, zmontexp, zmontexp_m_ary,
        zmontexp_doub1, zmontexp_doub2, zmontexp_doub3, zmontexp_doub

  Euclidean algorithms
  --------------------
        zgcd, zgcdeucl, zexteucl, zinvs, zinvodds, zinv, zchirem,
        zjacobis, zjacobi

  Random number generation
  ------------------------
        zrstarts, zrstart, zrseed, zrandom, zrandomb, zrandoml,
        zrandomprime, zrandomqprime, zrandomfprime, zrandomgprime

  Small prime generation
  ----------------------
        zpstart, zpstart2, zpnext, zpnextb, zp

  Compositeness testing and factorization
  ---------------------------------------
        zcomposite, zmcomposite, zprime, zprobprime,
        ztridiv, zpollardrho, zecm_trial, zecm, zfecm, zsquf

  Allocation
  ----------
        zsetlength, zfree

  Timing
  ------
        gettime, getutime, getstime, starttime, printtime

  Input and output
  ----------------
          from       to        to      from     to      to       from    to
          file      file      file     stdin  stdout  stdout    string  string
       ------------------------------------------------------------------------
decimal| zfread   zfwrite   zfwriteln  zread  zwrite  zwriteln  zsread  zswrite
hex    | zhfread  zhfwrite  zhfwriteln zhread zhwrite zhwriteln
nits   | zbfread  zbfwrite
anybase| zfread_b zfwrite_b zfwriteln_b


Remarks
=======
- Unless stated otherwise, output can be input, but it`s not advised
  to make output arguments identical (if there are more output
  parameters).
- Very long integers are represented by arrays of longs, in blocks
  of NBITS bits (these blocks will be referred to as "nits").
  A very long int (declared as  verylong a=0 ) either satisfies a==0,
  in which case it is treated as zero, or it satisfies the following:

        - |a[0]| is the significant length, say n, with n>0,
          even for a with value zero.

        - a[1], a[2], ..., a[n] are the nits, most significant nit
          is a[n], with always 0<a[n]<RADIX and 0<=a[i]<RADIX for
          i=1,2,...,n-1; here RADIX is (1<<NBITS).
          Exception: a[n] can be zero if n=1, in which case a has
          value zero.

        - the sign of a[0] is the sign of a.

        - a[-1] gives the amount of space currently allocated
          for a. The functions check this location to see if
          reallocation is needed.

        - the values of a[n+1],...,a[a[-1]] are undefined, and
          cannot be assumed to be zero.

        - except a==0, the only other correct representation
          of an a with value zero is: a[0]==1, a[1]==0. Negative
          zero is not recognized.

  Unless you know what you`re doing, don`t play with any of the a[i].

- Because of the way verylongs are represented, local change (in
  a routine) of a verylong parameter can affect the global value
  of that parameter (and even destroy it entirely). As an example,
  consider the following program:

	#include "lip.h"

	change_verylong(
		verylong verylong_a
		)
	{
		zwriteln(verylong_a);
		zsadd(verylong_a,1,&verylong_a);
		zwriteln(verylong_a);
	}
	
	change_long(
		long long_a
		)
	{
		printf("%ld\n",long_a);
		long_a ++;
		printf("%ld\n",long_a);
	}
	
	main () {
		long a = 5;
		verylong b = 0;
		zintoz(5,&b);
		change_long(a);
		printf("%ld\n",a);
		change_verylong(b);
		zwriteln(b);
	}

  Ouput:
	5
	6
	5
	5
	6
	6

  Although the parameter long_a gets a new value in change_long, this does
  not affect the value of the argument a upon call: it is 5 before and after
  the call. In change_verylong, however, the change made to the parameter
  verylong_a affects the value of the argument b: it is 5 before, but 6
  after the call. More dramatic things might happen too, if for instance
  verylong_a gets reallocated in change_verylong and its original space
  gets freed up....  To avoid these possible side-effects, either make
  verylong_a a *verylong parameter (which should and does keep the local
  changes made to it), or copy verylong_a to a local variable, and work
  with the local variable:

	better_change_verylong(
                verylong verylong_a
                )
        {
		static local_verylong_a = 0;
		zcopy(verylong_a,&local_verylong_a);
                zwriteln(local_verylong_a);
                zsadd(local_verylong_a,1,&local_verylong_a);
                zwriteln(local_verylong_a);
        }


- For those who know what the sizes of input and output
  arguments are going to be, you can allocate variables by hand using
  zsetlength, and make things slightly faster by using the