modulop.h File Reference

#include "misc/auxiliary.h"
#include "factory/factory.h"
#include <NTL/config.h>

Go to the source code of this file.

Macros
#define	NV_OPS
#define	NV_MAX_PRIME   32749
#define	FACTORY_MAX_PRIME   536870909
#define	npEqualM(A, B, r)   ((A)==(B))

Functions
BOOLEAN	npInitChar (coeffs r, void *p)
static number	npMultM (number a, number b, const coeffs r)
static void	npInpMultM (number &a, number b, const coeffs r)
static number	npAddM (number a, number b, const coeffs r)
static void	npInpAddM (number &a, number b, const coeffs r)
static number	npSubM (number a, number b, const coeffs r)
static number	npNegM (number a, const coeffs r)
static BOOLEAN	npIsOne (number a, const coeffs)
static long	npInvMod (long a, const coeffs R)
static number	npInversM (number c, const coeffs r)
long	npInt (number &n, const coeffs r)

Macro Definition Documentation

FACTORY_MAX_PRIME

#define FACTORY_MAX_PRIME   536870909

Definition at line 38 of file modulop.h.

npEqualM

#define npEqualM	(		A,
			B,
			r
	)		((A)==(B))

Definition at line 259 of file modulop.h.

NV_MAX_PRIME

#define NV_MAX_PRIME   32749

Definition at line 37 of file modulop.h.

NV_OPS

#define NV_OPS

Definition at line 36 of file modulop.h.

Function Documentation

npAddM()

static number npAddM ( number  a, number  b, const coeffs  r  )

inlinestatic

Definition at line 124 of file modulop.h.

{
  unsigned long R = (unsigned long)a + (unsigned long)b;
  return (number)(R >= (unsigned long)r->ch ? R - (unsigned long)r->ch : R);
}

npInitChar()

BOOLEAN npInitChar	(	coeffs	r,
		void *	p
	)

Definition at line 338 of file modulop.cc.

{
  assume( getCoeffType(r) == n_Zp );
  const int c = (int) (long) p;
 
  assume( c > 0 );
 
  int i, w;
 
  r->is_field=TRUE;
  r->is_domain=TRUE;
  r->rep=n_rep_int;
 
  r->ch = c;
  r->npPminus1M = c /*r->ch*/ - 1;
 
  //r->cfInitChar=npInitChar;
  r->cfKillChar=npKillChar;
  r->nCoeffIsEqual=npCoeffsEqual;
  r->cfCoeffName=npCoeffName;
 
  r->cfMult  = npMult;
  r->cfInpMult  = npInpMult;
  r->cfSub   = npSubM;
  r->cfAdd   = npAddM;
  r->cfInpAdd   = npInpAddM;
  r->cfDiv   = npDiv;
  r->cfInit = npInit;
  //r->cfSize  = ndSize;
  r->cfInt  = npInt;
  r->cfInitMPZ = npInitMPZ;
  #ifdef HAVE_RINGS
  //r->cfDivComp = NULL; // only for ring stuff
  //r->cfIsUnit = NULL; // only for ring stuff
  //r->cfGetUnit = NULL; // only for ring stuff
  //r->cfExtGcd = NULL; // only for ring stuff
  // r->cfDivBy = NULL; // only for ring stuff
  #endif
  r->cfInpNeg   = npNeg;
  r->cfInvers= npInvers;
  //r->cfCopy  = ndCopy;
  //r->cfRePart = ndCopy;
  //r->cfImPart = ndReturn0;
  r->cfWriteLong = npWrite;
  r->cfRead = npRead;
  //r->cfNormalize=ndNormalize;
  r->cfGreater = npGreater;
  r->cfEqual = npEqual;
  r->cfIsZero = npIsZero;
  r->cfIsOne = npIsOne;
  r->cfIsMOne = npIsMOne;
  r->cfGreaterZero = npGreaterZero;
  //r->cfPower = npPower;
  //r->cfGetDenom = ndGetDenom;
  //r->cfGetNumerator = ndGetNumerator;
  //r->cfGcd  = ndGcd;
  //r->cfLcm  = ndGcd;
  //r->cfDelete= ndDelete;
  r->cfSetMap = npSetMap;
  //r->cfName = ndName;
  //r->cfInpMult=ndInpMult;
  r->convSingNFactoryN=npConvSingNFactoryN;
  r->convFactoryNSingN=npConvFactoryNSingN;
  r->cfRandom=npRandom;
#ifdef LDEBUG
  // debug stuff
  r->cfDBTest=npDBTest;
#endif
 
  // io via ssi
  r->cfWriteFd=npWriteFd;
  r->cfReadFd=npReadFd;
 
  // the variables:
  r->type = n_Zp;
  r->has_simple_Alloc=TRUE;
  r->has_simple_Inverse=TRUE;
 
  // the tables
#ifdef NV_OPS
  if (r->ch <=NV_MAX_PRIME)
#endif
  {
#ifdef HAVE_INVTABLE
    r->npInvTable=(unsigned short*)omAlloc0( r->ch*sizeof(unsigned short) );
#endif
#ifndef HAVE_GENERIC_MULT
    r->cfParameter=npPar; /* Singular.jl */
    r->npExpTable=(unsigned short *)omAlloc0( r->ch*sizeof(unsigned short) );
    r->npLogTable=(unsigned short *)omAlloc0( r->ch*sizeof(unsigned short) );
    r->npExpTable[0] = 1;
    r->npLogTable[0] = 0;
    if (r->ch > 2)
    {
      w = 1;
      loop
      {
        r->npLogTable[1] = 0;
        w++;
        i = 0;
        loop
        {
          i++;
          r->npExpTable[i] =(int)(((long)w * (long)r->npExpTable[i-1]) % r->ch);
          r->npLogTable[r->npExpTable[i]] = i;
          if /*(i == r->ch - 1 ) ||*/ (/*(*/ r->npExpTable[i] == 1 /*)*/)
            break;
        }
        if (i == r->ch - 1)
          break;
      }
    }
    else
    {
      r->npExpTable[1] = 1;
      r->npLogTable[1] = 0;
    }
#endif
  }
#ifdef NV_OPS
  else /*if (c>NV_MAX_PRIME)*/
  {
    r->cfMult  = nvMult;
    r->cfDiv   = nvDiv;
    r->cfExactDiv = nvDiv;
    r->cfInvers  = nvInvers;
    r->cfInpMult = nvInpMult;
    //r->cfPower= nvPower;
    //if (c>FACTORY_MAX_PRIME) // factory will catch this error
    //{
    //  r->convSingNFactoryN=ndConvSingNFactoryN;
    //}
  }
#endif
  return FALSE;
}

npInpAddM()

static void npInpAddM ( number &  a, number  b, const coeffs  r  )

inlinestatic

Definition at line 129 of file modulop.h.

{
  unsigned long R = (unsigned long)a + (unsigned long)b;
  a=(number)(R >= (unsigned long)r->ch ? R - (unsigned long)r->ch : R);
}

npInpMultM()

static void npInpMultM ( number &  a, number  b, const coeffs  r  )

inlinestatic

Definition at line 86 of file modulop.h.

{
  long x = (long)r->npLogTable[(long)a]+ r->npLogTable[(long)b];
  #ifdef HAVE_GENERIC_ADD
    if (x>=r->npPminus1M) x-=r->npPminus1M;
  #else
    x-=r->npPminus1M;
    #if SIZEOF_LONG == 8
      x += (x >> 63) & r->npPminus1M;
    #else
      x += (x >> 31) & r->npPminus1M;
    #endif
  #endif
  a=(number)(long)r->npExpTable[x];
}

npInt()

long npInt	(	number &	n,
		const coeffs	r
	)

Definition at line 83 of file modulop.cc.

{
  n_Test(n, r);
 
  if ((long)n > (((long)r->ch) >>1)) return ((long)n -((long)r->ch));
  else                               return ((long)n);
}

npInversM()

static number npInversM ( number  c, const coeffs  r  )

inlinestatic

Definition at line 223 of file modulop.h.

{
  n_Test(c, r);
#ifndef HAVE_GENERIC_MULT
  #ifndef HAVE_INVTABLE
  number d = (number)(long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
  #else
  long inv=(long)r->npInvTable[(long)c];
  if (inv==0)
  {
    inv = (long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
    r->npInvTable[(long)c]=inv;
  }
  number d = (number)inv;
  #endif
#else
  #ifdef HAVE_INVTABLE
  long inv=(long)r->npInvTable[(long)c];
  if (inv==0)
  {
    inv=npInvMod((long)c,r);
    r->npInvTable[(long)c]=inv;
  }
  #else
  long  inv=npInvMod((long)c,r);
  #endif
  number d = (number)inv;
#endif
  n_Test(d, r);
  return d;
}

npInvMod()

static long npInvMod ( long  a, const coeffs  R  )

inlinestatic

Definition at line 184 of file modulop.h.

{
   long s;
 
   long  u, v, u0, u1, u2, q, r;
 
   assume(a>0);
   u1=1; u2=0;
   u = a; v = R->ch;
 
   do
   {
      q = u / v;
      //r = u % v;
      r = u - q*v;
      u = v;
      v = r;
      u0 = u2;
      u2 = u1 - q*u2;
      u1 = u0;
   } while (v != 0);
 
   assume(u==1);
   s = u1;
#ifdef HAVE_GENERIC_ADD
   if (s < 0)
      return s + R->ch;
   else
      return s;
#else
  #if SIZEOF_LONG == 8
  s += (s >> 63) & R->ch;
  #else
  s += (s >> 31) & R->ch;
  #endif
  return s;
#endif
}

npIsOne()

static BOOLEAN npIsOne ( number  a, const  coeffs  )

inlinestatic

Definition at line 179 of file modulop.h.

{
  return 1 == (long)a;
}

npMultM()

static number npMultM ( number  a, number  b, const coeffs  r  )

inlinestatic

Definition at line 71 of file modulop.h.

{
  long x = (long)r->npLogTable[(long)a]+ r->npLogTable[(long)b];
  #ifdef HAVE_GENERIC_ADD
    if (x>=r->npPminus1M) x-=r->npPminus1M;
  #else
    x-=r->npPminus1M;
    #if SIZEOF_LONG == 8
      x += (x >> 63) & r->npPminus1M;
    #else
      x += (x >> 31) & r->npPminus1M;
    #endif
  #endif
  return (number)(long)r->npExpTable[x];
}

npNegM()

static number npNegM ( number  a, const coeffs  r  )

inlinestatic

Definition at line 174 of file modulop.h.

{
  return (number)((long)(r->ch)-(long)(a));
}

npSubM()

static number npSubM ( number  a, number  b, const coeffs  r  )

inlinestatic

Definition at line 134 of file modulop.h.

{
  return (number)((long)a<(long)b ?
                       r->ch-(long)b+(long)a : (long)a-(long)b);
}