c_lip.h

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

typedef long * _ntl_verylong;

#if (defined(NTL_SINGLE_MUL))

#if (defined(NTL_AVOID_FLOAT) || defined(NTL_LONG_LONG))
#error "at most one of -DNTL_SINGLE_MUL -DNTL_AVOID_FLOAT -DNTL_LONG_LONG allowed"
#endif

#elif (defined(NTL_AVOID_FLOAT) && defined(NTL_LONG_LONG))
#error "at most one of -DNTL_SINGLE_MUL -DNTL_AVOID_FLOAT -DNTL_LONG_LONG allowed"
#endif

#if (defined(NTL_SINGLE_MUL))

#if (!NTL_SINGLE_MUL_OK)
#error "NTL_SINGLE_MUL not supported on this platform"
#endif

#define NTL_NBITS (26)

#else

#define NTL_NBITS NTL_NBITS_MAX

#endif


#define NTL_RADIX           (1L<<NTL_NBITS)
#define NTL_NBITSH          (NTL_NBITS>>1)
#define NTL_RADIXM          (NTL_RADIX-1)
#define NTL_RADIXROOT       (1L<<NTL_NBITSH)
#define NTL_RADIXROOTM      (NTL_RADIXROOT-1)

#define NTL_FRADIX ((double) NTL_RADIX)
#define NTL_FRADIX_INV  (((double) 1.0)/((double) NTL_RADIX))



#define NTL_ZZ_NBITS NTL_NBITS
#define NTL_ZZ_FRADIX ((double) (1L << NTL_NBITS))

#define NTL_SP_NBITS NTL_NBITS
#define NTL_SP_BOUND (1L << NTL_SP_NBITS)
#define NTL_SP_FBOUND ((double) NTL_SP_BOUND)

#define NTL_WSP_NBITS NTL_ZZ_NBITS
#define NTL_WSP_BOUND (1L << NTL_WSP_NBITS)



#if (defined(NTL_SINGLE_MUL) && !NTL_SINGLE_MUL_OK)
#undef NTL_SINGLE_MUL
#endif

#if (defined(NTL_SINGLE_MUL))


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

The following macros extract the two words of a double,
getting around the type system.
This is only used in the NTL_SINGLE_MUL strategy.

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

#if (NTL_DOUBLES_LOW_HIGH)
#define NTL_LO_WD 0
#define NTL_HI_WD 1
#else
#define NTL_LO_WD 1
#define NTL_HI_WD 0
#endif


typedef union { double d; unsigned long rep[2]; } _ntl_d_or_rep;

#define NTL_FetchHiLo(hi,lo,x) \
do { \
   _ntl_d_or_rep ll_xx; \
   ll_xx.d = (x); \
   hi = ll_xx.rep[NTL_HI_WD]; \
   lo = ll_xx.rep[NTL_LO_WD]; \
} while (0)


#define NTL_FetchLo(lo,x)  \
do {  \
   _ntl_d_or_rep ll_xx;  \
   ll_xx.d = x;  \
   lo = ll_xx.rep[NTL_LO_WD];  \
} while (0) 

#endif


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

   A multiprecision integer is represented as a pointer to long.
   Let x be such a pointer.
   x = 0 represents 0.
   Otherwise, let n = abs(x[0]) and s = sign(x[0]);
   the integer represented is then:

      s*(x[1] + x[2]*NTL_RADIX + ... + x[n]*NTL_RADIX^{n-1}),

   where x[n] != 0, unless n = s = 1.
   Notice that the number zero can be represented in precisely 2 ways,
   either as a null pointer, or as x[0] = 1 and x[1] = 0.

   Storage is generally managed via _ntl_zsetlength and _ntl_zfree.
   x[-1] = (k << 1) | b, where k is the maximum value of n allocated,
   and b is a bit that is set is the space is managed by some
   mechanism other than _ntl_zsetlength and _ntl_zfree.

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



#if (defined(__cplusplus) && !defined(NTL_CXX_ONLY))
extern "C" {
#endif


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

   Basic Functions

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


    void _ntl_zsadd(_ntl_verylong a, long d, _ntl_verylong *b);
       /* *b = a + d */

    void _ntl_zadd(_ntl_verylong a, _ntl_verylong b, _ntl_verylong *c);
       /*  *c = a + b */

    void _ntl_zsub(_ntl_verylong a, _ntl_verylong b, _ntl_verylong *c);
       /* *c = a - b */

    void _ntl_zsubpos(_ntl_verylong a, _ntl_verylong b, _ntl_verylong *c);
       /* *c = a - b; assumes a >= b >= 0 */

    void _ntl_zsmul(_ntl_verylong a, long d, _ntl_verylong *b);
       /* *b = d * a */

    void _ntl_zmul(_ntl_verylong a, _ntl_verylong b, _ntl_verylong *c);
       /* *c = a * b */

    void _ntl_zsq(_ntl_verylong a, _ntl_verylong *c);
       /* *c = a * a */

    long _ntl_zsdiv(_ntl_verylong a, long b, _ntl_verylong *q);
       /* (*q) = floor(a/b) and a - floor(a/b)*(*q) is returned;
          error is raised if b == 0;
          if b does not divide a, then sign(*q) == sign(b) */

    void _ntl_zdiv(_ntl_verylong a, _ntl_verylong b, _ntl_verylong *q, _ntl_verylong *r);
       /* (*q) = floor(a/b) and (*r) = a - floor(a/b)*(*q);
          error is raised if b == 0;
          if b does not divide a, then sign(*q) == sign(b) */

    void _ntl_zmultirem(_ntl_verylong a, long n, long* dd, long* rr);
    void _ntl_zmultirem2(_ntl_verylong a, long n, long* dd, double **tbl, long* rr);
       /* rr[i] = a % dd[i], i = 0..n-1;
          assumes a >= 0, 0 < dd[i] < NTL_RADIX
          _ntl_zmultirem2 takes an extra argument, tbl, which contains
          pre-computed residues of powers of RADIX */
    void _ntl_zmultirem3(_ntl_verylong a, long n, long* dd, long **tbl, long* rr);
       /* same as above, but tbl has different type */

    long _ntl_zsfastrem(_ntl_verylong a, long d);
       /* return a % d;
          assumes a >= 0, 0 < d < NTL_RADIX */
        

    void _ntl_zmod(_ntl_verylong a, _ntl_verylong b, _ntl_verylong *r);
       /* same as _ntl_zdiv, but only remainder is computed */

    long _ntl_zsmod(_ntl_verylong a, long d);
       /* same as _ntl_zsdiv, but only remainder is computed */

    void _ntl_zquickmod(_ntl_verylong *r, _ntl_verylong b);
       /* *r = *r % b;
	  assumes b > 0 and *r >= 0;
	  The division is performed in place (but may sometimes
          cause *r to grow by one digit) */

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

   Shifting and bit manipulation

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

    void _ntl_z2mul(_ntl_verylong n, _ntl_verylong *a);
       /* *a = 2 * n */

    long _ntl_z2div(_ntl_verylong n, _ntl_verylong *a);
       /* *a = sign(n) * (|n|/2) */ 

    void _ntl_zlshift(_ntl_verylong n, long k, _ntl_verylong *a);
       /* *a = sign(n) * (|n| << k);
          shift is in reverse direction for negative k */

    void _ntl_zrshift(_ntl_verylong n, long k, _ntl_verylong *a);
       /* *a = sign(n) * (|n| >> k);
          shift is in reverse direction for negative k */
    
    long _ntl_zmakeodd(_ntl_verylong *n);
       /*
          if (n != 0)
              *n = m;
              return (k such that n == 2 ^ k * m with m odd);
          else
              return (0); 
        */

    long _ntl_znumtwos(_ntl_verylong n);
        /* return largest e such that 2^e divides n, or zero if n is zero */



    long _ntl_zodd(_ntl_verylong a);
       /* returns 1 if n is odd and 0 if it is even */

    long _ntl_zbit(_ntl_verylong a, long p);
       /* returns p-th bit of a, where the low order bit is indexed by 0;
          p out of range returns 0 */

    long _ntl_zsetbit(_ntl_verylong *a, long p);
       /* returns original value of p-th bit of |a|, and replaces
          p-th bit of a by 1 if it was zero;
          error if p < 0 */

    long _ntl_zswitchbit(_ntl_verylong *a, long p);
       /* returns original value of p-th bit of |a|, and switches
          the value of p-th bit of a;
          p starts counting at 0;
          error if p < 0 */


     void _ntl_zlowbits(_ntl_verylong a, long k, _ntl_verylong *b);
        /* places k low order bits of |a| in b */ 

     long _ntl_zslowbits(_ntl_verylong a, long k);
        /* returns k low order bits of |a| */

    long _ntl_zweights(long a);
        /* returns Hamming weight of |a| */

    long _ntl_zweight(_ntl_verylong a);
        /* returns Hamming weight of |a| */

    void _ntl_zand(_ntl_verylong a, _ntl_verylong b, _ntl_verylong *c);
        /* c gets bit pattern `bits of |a|` and `bits of |b|` */

    void _ntl_zor(_ntl_verylong a, _ntl_verylong b, _ntl_verylong *c);
        /* c gets bit pattern `bits of |a|` inclusive or `bits of |b|` */

    void _ntl_zxor(_ntl_verylong a, _ntl_verylong b, _ntl_verylong *c);
        /* c gets bit pattern `bits of |a|` exclusive or `bits of |b|` */




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

   Comparison

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

    long _ntl_zcompare(_ntl_verylong a, _ntl_verylong b);
       /*
          if (a > b)
              return (1);
          if (a == b)
              return (0);
          if (a < b)
              return (-1);
         */

    long _ntl_zscompare(_ntl_verylong a, long b);
       /* single-precision version of the above */

    long _ntl_ziszero (_ntl_verylong a);
       /* test for 0 */


    long _ntl_zsign(_ntl_verylong a);
       /* 
          if (a > 0)
              return (1);
          if (a == 0)
              return (0);
          if (a < 0)
              return (-1);
        */

    void _ntl_zabs(_ntl_verylong *a);
       /* *a = |a| */

    void _ntl_znegate(_ntl_verylong *a);
       /* *a = -a */

    void _ntl_zcopy(_ntl_verylong a, _ntl_verylong *b);
       /* *b = a;  space is allocated  */

    void _ntl_zcopy1(_ntl_verylong a, _ntl_verylong *b);
       /* *b = a;  space not necessarily allocated  */

    void _ntl_zswap(_ntl_verylong *a, _ntl_verylong *b);
       /* swap a and b (by swaping pointers) */

    long _ntl_z2log(_ntl_verylong a);
       /* number of bits in |a|; returns 0 if a = 0 */

    long _ntl_z2logs(long a);
        /* single-precision version of the above */