lip.h

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

	*
        * a must be >= 0 if n even, n >= 0 if a = 0,
        *
        * possible error message:
        *   dth root with d=0 in zroot
        *   dth root with even d of negative number in zroot
        *   dth root with d<0 of zero in zroot
        * result undefined if error occurs
        \******************************************************************/


long zispower( verylong a, verylong *f);
        /******************************************************************\
	* if (a== x^k)
	*	*f = x, return k
	* else
	*	return 0
	*
        * assumes a>1
        * 
        \******************************************************************/


/******************************************************************************\
*  Modular arithmetic 
*  
*  Addition, subtraction, multiplication, squaring division, inversion,
*  and exponentiation modulo a positive modulus n, where all operands
*  (except for the exponent in exponentiation) and results are in the
*  range [0, n-1]. For heavy computations modulo a fixed modulus it
*  might be better to use Montgomery arithmetic.
\******************************************************************************/

    void zaddmod(verylong a, verylong b, verylong n, verylong *c);
        /******************************************************************\
        * *c = (a + b) % n;
        * 
        * with 0 <= a,b,c < n (and n positive)
        *
        * possible error message:
        *   modulus zero in zaddmod
        * result undefined if error occurs
        \******************************************************************/

    void zsubmod(verylong a, verylong b, verylong n, verylong *c);
        /******************************************************************\
        * *c = (a - b) % n;
        * 
        * with 0 <= a,b,c < n (and n positive)
        *
        * possible error message:
        *   modulus zero in zsubmod
        * result undefined if error occurs
        \******************************************************************/

    long zmulmods(long a, long b, long n);
        /******************************************************************\
        * return ((a * b) % n);
        \******************************************************************/

    long zmulmod26(long a, long b, long n, double bninv);
        /******************************************************************\
        * return ((a * b) % n);
        * where bninv = (double)b/(double)n
	* only for 0<=a,b,n<2^26
        \******************************************************************/

    void zsmulmod(verylong a, long b, verylong n, verylong *c);
        /******************************************************************\
        * *c = (a * b) % n;
        * 
        * with 0 <= a,b,c < n (and n positive)
        *
        * possible error message:
        *   modulus zero in zsmulmod
        * result undefined if error occurs
        \******************************************************************/

    void zmulmod(verylong a, verylong b, verylong n, verylong *c);
        /******************************************************************\
        * *c = (a * b) % n;
        * 
        * with 0 <= a,b,c < n (and n positive)
        *
        * possible error message:
        *   modulus zero in zmulmod
        * result undefined if error occurs
        \******************************************************************/

    void zmulinmod(verylong a, verylong *b, verylong n);
        /******************************************************************\
        * *b = (a * b) % n;
        * 
        * with 0 <= a,b < n (and n positive)
        *
        * possible error message:
        *   modulus zero in zmulinmod
        * result undefined if error occurs
        \******************************************************************/

    void zsqmod(verylong a, verylong n, verylong *c);
        /******************************************************************\
        * *c = (a ^ 2) % n;
        * 
        * with 0 <= a,c < n (and n positive)
        *
        * possible error message:
        *   modulus zero in zsqmod
        * result undefined if error occurs
        \******************************************************************/

    void zsqrtmod(verylong a, verylong p, verylong *s);
        /******************************************************************\
        * computes x so that x^2 == a mod p for prime p, and puts x in *s.
	* if no such x exists or if p is not prime, then sets *s=0.
        \******************************************************************/


    void zsqinmod(verylong *a, verylong n);
        /******************************************************************\
        * *a = (a ^ 2) % n;
        * 
        * with 0 <= a < n (and n positive)
        *
        * possible error message:
        *   modulus zero in zsqinmod
        * result undefined if error occurs
        \******************************************************************/

    void zdivmod(verylong a, verylong b, verylong n, verylong *c);
        /******************************************************************\
        * *c = (a / b) % n;
        * 
        * with 0 <= a,b,c < n (and n positive),
        *
        * possible error message:
        *   modulus zero in zdivmod
        *   division by zero in zdivmod
        *   undefined quotient in zdivmod
        * result undefined if error occurs, except if the quotient
        * is undefined, in which case a factor of n will be returned in c
        * (of course, only if the -DNO_HALT flag is used)
        \******************************************************************/

    void zinvmod(verylong a, verylong n, verylong *c);
        /******************************************************************\
        * *c = (1 / a) % n;
        * 
        * with 0 <= a,c < n (and n positive),
        *
        * possible error message:
        *   modulus zero in zinvmod
        *   division by zero in zinvmod
        *   undefined inverse in zinvmod
        * result undefined if error occurs, except if the inverse
        * is undefined, in which case a factor of n will be returned in c
        * (of course, only if the -DNO_HALT flag is used)
        \******************************************************************/

    long zexpmods(long a, long e, long n);
        /******************************************************************\
        * return ((a ^ |e|) % n);
        * 
        \******************************************************************/

    void zsexpmod(verylong a, long e, verylong n, verylong *b);
        /******************************************************************\
        * *b = (a ^ e) % n;
        * 
        * arguments cannot be the same (but a and b can be the same)
        * (a^(-e)) and n coprime if e negative
        \******************************************************************/

    void z2expmod(verylong e, verylong n, verylong *b);
        /******************************************************************\
        * *b = (2 ^ e) % n;
        * 
        * arguments cannot be the same,
        * (2^(-e)) and n coprime if e negative
        *
        * possible error message:
        *   modulus zero in z2expmod
        *   undefined quotient in z2expmod      (caused by negative exponent)
        * result undefined if error occurs, except if the quotient
        * is undefined, in which case a factor of n will be returned in b
        * (of course, only if the -DNO_HALT flag is used)
        \******************************************************************/

    void zexpmod(verylong a, verylong e, verylong n, verylong *b);
        /******************************************************************\
        * *b = (a ^ e) % n;
        * 
        * a and b can be the same, but both unequal
        * to e and n, (a^(-e)) and n coprime if e negative
        *
        * possible error message:
        *   modulus zero in zexpmod
        *   undefined quotient in zexpmod       (caused by negative exponent)
        * result undefined if error occurs, except if the quotient
        * is undefined, in which case a factor of n will be returned in b
        * (of course, only if the -DNO_HALT flag is used)
        \******************************************************************/

    void zexpmod_m_ary(verylong a, verylong e, verylong n, verylong *b, long m);
        /******************************************************************\
        * b = (a ^ e) % n;
        * 
        * using m-ary method which is faster than
        * zexpmod if a is not small, a and b can be the same, but both
        * unequal to e and n, (a^(-e)) and n coprime if e negative,
        * if m <= 1, default m will be used for m-ary method, if
        * m >= NBITS, NBITS-1 will be used
        *
        * possible error message:
        *   modulus zero in zexpmod_m_ary
        *   undefined quotient in zexpmod_m_ary    (caused by negative exponent)
        * result undefined if error occurs, except if the quotient
        * is undefined, in which case a factor of n will be returned in b
        * (of course, only if the -DNO_HALT flag is used)
        \******************************************************************/

    long zdefault_m(long l);
        /******************************************************************\
        * return (default m for m-ary exponentiation);
        \******************************************************************/

    void zexpmod_doub1(verylong x1, verylong e1, verylong x2, verylong e2,
                       verylong n, verylong *b);
        /******************************************************************\
        * b = ( x1 ^ e1) * (x2 ^ e2) % n;
        *
        * uses Shamir`s method, i.e., does the exponentiations simultaneously
        * after precomputation of (x1*x2)%n, only for e1 and e2 non-negative,
        * use if e1 and e2 approximately same size and small
        *
        * possible error message:
        *  modulus zero in zexpmod_doub1
        *  negative exponent in zexpmod_doub1     (if e1 or e2 negative)
        * result undefined if error occurs
        \******************************************************************/

    void zexpmod_doub2(verylong x1, verylong e1, verylong x2, verylong e2,
                       verylong n, verylong *b);
        /******************************************************************\
        * b = ( x1 ^ e1) * (x2 ^ e2) % n;
        *
        * uses Shamir`s method with sliding window of size 2 on exponents
        * after precomputation of table of products (xi^i1)*(x2^i2)%n with
        * 0<=i1,i2<=3 and i1 and i2 not both even, only for e1 and e2
        * non-negative, use if e1 and e2 approximately same size and up to
        * approximately 270 bits
        *
        * possible error message:
        *  modulus zero in zexpmod_doub2
        *  negative exponent in zexpmod_doub2     (if e1 or e2 negative)
        * result undefined if error occurs
        \******************************************************************/

    void zexpmod_doub3(verylong x1, verylong e1, verylong x2, verylong e2,
                       verylong n, verylong *b);
        /******************************************************************\
        * b = ( x1 ^ e1) * (x2 ^ e2) % n;
        *
        * uses Shamir`s method with sliding window of size 3 on exponents
        * after precomputation of table of products (xi^i1)*(x2^i2)%n with
        * 0<=i1,i2<=7 and i1 and i2 not both even, only for e1 and e2
        * non-negative, use if e1 and e2 approximately same size and 
        * larger than approximately 270 bits
        *
        * possible error message:
        *  modulus zero in zexpmod_doub3
        *  negative exponent in zexpmod_doub3     (if e1 or e2 negative)
        * result undefined if error occurs
        \******************************************************************/

    void zexpmod_doub(verylong x1, verylong e1, verylong x2, verylong e2,
                       verylong n, verylong *b);
        /******************************************************************\
        * b = ( x1 ^ e1) * (x2 ^ e2) % n;
        *
        * uses Shamir`s method with sliding window of size depending on
        * maximal size of e1 or e2, using zexpmod_doub1, zexpmod_doub2,
        * or zexpmod_doub3, only for e1 and e2 non-negative, use if e1
        * and e2 approximately same size
        *
        * possible error message:
        *  modulus zero in zexpmod_doub
        *  negative exponent in zexpmod_doub     (if e1 or e2 negative)
        * result undefined if error occurs
        \******************************************************************/


/******************************************************************************\
*  Montgomery modular arithmetic
*
*  Modular multiplications can be done division free and therefore
*  somewhat faster (about 20%), if the Montgomery representation is
*  used. Converting to and from Montgomery representation takes one
*  Montgomery multiplication each, so it only pays to use Montgomery
*  representation if many multiplications have to be carried out
*  modulo a fixed odd modulus.
*
*  To use Montgomery arithmetic, first initialize the modulus zn (use
*  zmstart), and convert all operands to their Montgomery representation
*  (ztom), but do Not convert exponents. Use the addition, subtraction,
*  multiplication, squaring, division, inversion, and exponentiation
*  functions (zmontxxx) below on the converted operands, just as you
*  would use the ordinary modular functions (zxxxmod). The results can
*  be converted back from Montgomery representation to ordinary numbers
*  modulo zn using zmtoz. zmfree makes current Montgomery modulus undefined;
*  this has no effect except that some routines that use Montgomery
*  arithmetic (with a possibly different modulus) get slightly faster.
*
*  Once you have figured out how this works, you might want to try
*  `mixed arithmetic` by using ordinary modular functions for operations
*  on (non-converted) small constants and Montgomery numbers; zsmontmul
*  might be helpful. See the source code of zmcomposite for an example.
*
*  For how it works, see P.L. Montgomery, Modular multiplication without
*  trial division, Math. Comp, 44 (1985), 519--521.
\******************************************************************************/

    void zmstart(verylong n);
        /******************************************************************\
        * zn = n;
        * 
        * initializes the Montgomery modulus zn as n,
        * only for odd positive n
        *
        * possible error message:
        *   zero, or even, or negative modulus in zmstart
        * result undefined if error occurs
        \******************************************************************/

    void zmfree();
        /******************************************************************\
        * Allows internal arithmetic to overwrite the current Montgomery
        * modulus without restoring it
        \********************************