lip.h

Implementation Of ELGAMAL Public key encryption in C . it can use very long key os size 2007 decimal

        * *b = a ^ e;
        * 
        * arguments cannot be the same,
        * e must be >= 0 if abs(a) != 1,
        * better be sure that you know what you`re 
        * doing before you call this
        *
        * possible error message:
        *   negative exponent in zexp
        * result undefined if error occurs
        \******************************************************************/

    long zsqrts(long n);
        /******************************************************************\
        * if (n > 0)
        *     return ([sqrt(n)]);
        * else
        *     return (0);
        \******************************************************************/

    long zsqrt(verylong n, verylong *r, verylong *dif);
        /******************************************************************\
        * *r = [sqrt(n)];
        * *dif = n - r ^ 2;
        * if (n perfect square)
        *     return (1)
        * else
        *     return (0)
        * 
        * n must be >= 0
        *
        * possible error message:
        *   negative argument in zsqrt
        * result undefined if error occurs
        \******************************************************************/

    long zroot(verylong a, long n, verylong *b);
        /******************************************************************\
        * *b = nth root of a;
        * 
	* if (a perfect nth root)
	*	return 1
	* else if (no nth root)
	*	return -1
	* else
	*	return 0
	*
        * a must be >= 0 if n even, n >= 0 if a = 0,
        *
        * possible error message:
        *   nth root with n=0 in zroot
        *   nth root with even n of negative number in zroot
        *   nth root with n<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 approximate