c_lip.h

密码大家Shoup写的数论算法c语言实现

/********************************************************************

   Conversion

*********************************************************************/
        
    void _ntl_zzero(_ntl_verylong *a);
       /* *a = 0;  space is allocated */

    void _ntl_zzero1(_ntl_verylong *a);
       /* *a = 0;  space not necessarily allocated */

    void _ntl_zone(_ntl_verylong *a);
       /* *a = 1 */

    void _ntl_zintoz(long d, _ntl_verylong *a);
       /* *a = d;  space is allocated  */

    void _ntl_zintoz1(long d, _ntl_verylong *a);
       /* *a = d;  space not necessarily allocated  */

    void _ntl_zuintoz(unsigned long d, _ntl_verylong *a);
       /* *a = d;  space is allocated  */

    long _ntl_ztoint(_ntl_verylong a);
       /* converts a to a long;  overflow results in value
          mod 2^{NTL_BITS_PER_LONG}. */

    unsigned long _ntl_ztouint(_ntl_verylong a);
       /* converts a to a long;  overflow results in value
          mod 2^{NTL_BITS_PER_LONG}. */


    double _ntl_zdoub(_ntl_verylong n);
       /* converts a to a double;  no overflow check */

    long _ntl_zround_correction(_ntl_verylong a, long k, long residual);
       /* k >= 1, |a| >= 2^k, and residual is 0, 1, or -1.
          The result is what we should add to (a >> k) to round
          x = a/2^k to the nearest integer using IEEE-like rounding rules
          (i.e., round to nearest, and round to even to break ties).
          The result is either 0 or sign(a).
          If residual is not zero, it is as if x were replaced by
          x' = x + residual*2^{-(k+1)}.
          This can be used to break ties when x is exactly
          half way between two integers. */

    double _ntl_zlog(_ntl_verylong a);
       /* computes log(a), protecting against overflow */
      

    void _ntl_zdoubtoz(double a, _ntl_verylong *x);
       /* x = floor(a); */  
    



/************************************************************************

   Square roots

*************************************************************************/


    long _ntl_zsqrts(long n);
       /* return floor(sqrt(n));  error raised in n < 0 */

    void _ntl_zsqrt(_ntl_verylong n, _ntl_verylong *r);
       /* *r =  floor(sqrt(n));  error raised in n < 0 */

/*********************************************************************
 
    Exponentiation
 
**********************************************************************/

   void _ntl_zexp(_ntl_verylong a, long e, _ntl_verylong *b);
       /* *b = a^e;  error raised if e < 0 */

   void _ntl_zexps(long a, long e, _ntl_verylong *b);
       /* *b = a^e;  error raised if e < 0 */
       

/*********************************************************************

   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].   

   ALIAS RESTRICTION:  output parameters should not alias n

***********************************************************************/

    void _ntl_zaddmod(_ntl_verylong a, _ntl_verylong b, _ntl_verylong n, _ntl_verylong *c);
       /* *c = (a + b) % n */

    void _ntl_zsubmod(_ntl_verylong a, _ntl_verylong b, _ntl_verylong n, _ntl_verylong *c);
       /* *c = (a - b) % n */

    void _ntl_zsmulmod(_ntl_verylong a, long b, _ntl_verylong n, _ntl_verylong *c);
       /* *c = (a * b) % n */

    void _ntl_zmulmod(_ntl_verylong a, _ntl_verylong b, _ntl_verylong n, _ntl_verylong *c);
       /* *c = (a * b) % n */

    void _ntl_zsqmod(_ntl_verylong a, _ntl_verylong n, _ntl_verylong *c);
       /* *c = (a ^ 2) % n */

    void _ntl_zinvmod(_ntl_verylong a, _ntl_verylong n, _ntl_verylong *c);
       /* *c = (1 / a) % n; error raised if gcd(b, n) != 1 */

    void _ntl_zpowermod(_ntl_verylong g, _ntl_verylong e, _ntl_verylong F,
                        _ntl_verylong *h);

       /* *b = (a ^ e) % n;  */



/**************************************************************************

   Euclidean Algorithms

***************************************************************************/
    void _ntl_zgcd(_ntl_verylong m1, _ntl_verylong m2, _ntl_verylong *r);
       /* *r = greatest common divisor of m1 and m2; 
          uses binary gcd algorithm */


    void _ntl_zexteucl(_ntl_verylong a, _ntl_verylong *xa,
                 _ntl_verylong b, _ntl_verylong *xb,
                 _ntl_verylong *d);
       /*
          *d = a * *xa + b * *xb = gcd(a, b);
          sets *d, *xa and *xb given a and b;
          uses Lehmer`s trick
        */


    long _ntl_zinv(_ntl_verylong a, _ntl_verylong b, _ntl_verylong *c);
       /*
          if (a and b coprime)
          {
              *c = inv; 
              return(0);
          }
          else
          {
              *c = gcd(a, b);
              return(1);
          }
          
          where inv is such that (inv * a)  == 1 mod b;
          error raised if b <= 1 or a < 0 or a >= b
        */

     long _ntl_zxxratrecon(_ntl_verylong x, _ntl_verylong m,  
                      _ntl_verylong a_bound, _ntl_verylong b_bound,
                      _ntl_verylong *a, _ntl_verylong *b);

        /* rational reconstruction: see doc in ZZ.txt */


        
/**********************************************************************

    Storage Allocation

    These routines use malloc and free.

***********************************************************************/


    void _ntl_zsetlength(_ntl_verylong *v, long len);
       /* Allocates enough space to hold a len-digit number,
          where each digit has NTL_NBITS bits.
          If space must be allocated, space for one extra digit
          is always allocated. */

    void _ntl_zfree(_ntl_verylong *x);
       /* Free's space held by x, and sets x back to 0. */


/*******************************************************************

    Special routines

********************************************************************/



long _ntl_zsize(_ntl_verylong n);
long _ntl_zisone(_ntl_verylong n);
long _ntl_zdigit(_ntl_verylong a, long i);

long _ntl_zsptest(_ntl_verylong a);
long _ntl_zwsptest(_ntl_verylong a);

long _ntl_zcrtinrange(_ntl_verylong g, _ntl_verylong a);

void _ntl_zfrombytes(_ntl_verylong *x, const unsigned char *p, long n);
void _ntl_zbytesfromz(unsigned char *p, _ntl_verylong a, long nn);

long _ntl_zblock_construct_alloc(_ntl_verylong *x, long d, long n);
void _ntl_zblock_construct_set(_ntl_verylong x, _ntl_verylong *y, long i);
long _ntl_zblock_destroy(_ntl_verylong x);
long _ntl_zblock_storage(long d);



void _ntl_crt_struct_init(void **crt_struct, long n, _ntl_verylong p,
                          const long *primes);
void _ntl_crt_struct_insert(void *crt_struct, long i, _ntl_verylong m);
void _ntl_crt_struct_free(void *crt_struct);
void _ntl_crt_struct_eval(void *crt_struct, _ntl_verylong *t, const long *a);
long _ntl_crt_struct_special(void *crt_struct);

void _ntl_rem_struct_init(void **rem_struct, long n, _ntl_verylong p, 
                          const long *primes);
void _ntl_rem_struct_free(void *rem_struct);
void _ntl_rem_struct_eval(void *rem_struct, long *x, _ntl_verylong a);



#if (defined(__cplusplus) && !defined(NTL_CXX_ONLY))
}
#endif


extern int _ntl_gmp_hack;

#define NTL_crt_struct_eval _ntl_crt_struct_eval
#define NTL_crt_struct_free _ntl_crt_struct_free
#define NTL_crt_struct_init _ntl_crt_struct_init
#define NTL_crt_struct_insert _ntl_crt_struct_insert
#define NTL_crt_struct_special _ntl_crt_struct_special
#define NTL_rem_struct_eval _ntl_rem_struct_eval
#define NTL_rem_struct_free _ntl_rem_struct_free
#define NTL_rem_struct_init _ntl_rem_struct_init
#define NTL_verylong _ntl_verylong
#define NTL_z2log _ntl_z2log
#define NTL_zabs _ntl_zabs
#define NTL_zadd _ntl_zadd
#define NTL_zaddmod _ntl_zaddmod
#define NTL_zand _ntl_zand
#define NTL_zbit _ntl_zbit
#define NTL_zblock_construct_alloc _ntl_zblock_construct_alloc
#define NTL_zblock_construct_set _ntl_zblock_construct_set
#define NTL_zblock_destroy _ntl_zblock_destroy
#define NTL_zblock_storage _ntl_zblock_storage
#define NTL_zbytesfromz _ntl_zbytesfromz
#define NTL_zcompare _ntl_zcompare
#define NTL_zcopy _ntl_zcopy1
#define NTL_zcrtinrange _ntl_zcrtinrange
#define NTL_zdigit _ntl_zdigit
#define NTL_zdiv _ntl_zdiv
#define NTL_zdoub _ntl_zdoub
#define NTL_zdoubtoz _ntl_zdoubtoz
#define NTL_zexp _ntl_zexp
#define NTL_zexps _ntl_zexps
#define NTL_zexteucl _ntl_zexteucl
#define NTL_zfree _ntl_zfree
#define NTL_zfrombytes _ntl_zfrombytes
#define NTL_zgcd _ntl_zgcd
#define NTL_zintoz _ntl_zintoz1
#define NTL_zinv _ntl_zinv
#define NTL_zinvmod _ntl_zinvmod
#define NTL_zisone _ntl_zisone
#define NTL_ziszero _ntl_ziszero
#define NTL_zlog _ntl_zlog
#define NTL_zlowbits _ntl_zlowbits
#define NTL_zlshift _ntl_zlshift
#define NTL_zmakeodd _ntl_zmakeodd
#define NTL_zmod _ntl_zmod
#define NTL_zmul _ntl_zmul
#define NTL_zmulmod _ntl_zmulmod
#define NTL_znegate _ntl_znegate
#define NTL_znumtwos _ntl_znumtwos
#define NTL_zodd _ntl_zodd
#define NTL_zone _ntl_zone
#define NTL_zor _ntl_zor
#define NTL_zpowermod _ntl_zpowermod
#define NTL_zquickmod _ntl_zquickmod
#define NTL_zround_correction _ntl_zround_correction
#define NTL_zrshift _ntl_zrshift
#define NTL_zsadd _ntl_zsadd
#define NTL_zscompare _ntl_zscompare
#define NTL_zsdiv _ntl_zsdiv
#define NTL_zsetbit _ntl_zsetbit
#define NTL_zsetlength _ntl_zsetlength
#define NTL_zsign _ntl_zsign
#define NTL_zsize _ntl_zsize
#define NTL_zslowbits _ntl_zslowbits
#define NTL_zsmod _ntl_zsmod
#define NTL_zsmul _ntl_zsmul
#define NTL_zsmulmod _ntl_zsmulmod
#define NTL_zsptest _ntl_zsptest
#define NTL_zsq _ntl_zsq
#define NTL_zsqmod _ntl_zsqmod
#define NTL_zsqrt _ntl_zsqrt
#define NTL_zsqrts _ntl_zsqrts
#define NTL_zsub _ntl_zsub
#define NTL_zsubmod _ntl_zsubmod
#define NTL_zsubpos _ntl_zsubpos
#define NTL_zswap _ntl_zswap
#define NTL_zswitchbit _ntl_zswitchbit
#define NTL_ztoint _ntl_ztoint
#define NTL_ztouint _ntl_ztouint
#define NTL_zuintoz _ntl_zuintoz
#define NTL_zweight _ntl_zweight
#define NTL_zweights _ntl_zweights
#define NTL_zwsptest _ntl_zwsptest
#define NTL_zxor _ntl_zxor
#define NTL_zxxratrecon _ntl_zxxratrecon
#define NTL_zzero _ntl_zzero1