NTLconvert.cc File Reference

#include "config.h"
#include "cf_assert.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cf_iter.h"
#include "fac_sqrfree.h"
#include "cf_algorithm.h"
#include <factory/cf_gmp.h>
#include <stdio.h>
#include <string.h>
#include <NTL/ZZXFactoring.h>
#include <NTL/ZZ_pXFactoring.h>
#include <NTL/lzz_pXFactoring.h>
#include <NTL/GF2XFactoring.h>
#include <NTL/ZZ_pEXFactoring.h>
#include <NTL/lzz_pEXFactoring.h>
#include <NTL/GF2EXFactoring.h>
#include <NTL/tools.h>
#include <NTL/mat_ZZ.h>
#include "int_int.h"
#include <limits.h>
#include "NTLconvert.h"

Go to the source code of this file.

Macros
#define	Alloc(L)   malloc(L)
#define	Free(A, L)   free(A)

Functions
void	out_cf (const char *s1, const CanonicalForm &f, const char *s2)
	cf_algorithm.cc - simple mathematical algorithms. More...
ZZ_pX	convertFacCF2NTLZZpX (const CanonicalForm &f)
	NAME: convertFacCF2NTLZZpX. More...
zz_pX	convertFacCF2NTLzzpX (const CanonicalForm &f)
GF2X	convertFacCF2NTLGF2X (const CanonicalForm &f)
	NAME: convertFacCF2NTLGF2X. More...
CanonicalForm	convertNTLZZpX2CF (const ZZ_pX &poly, const Variable &x)
	NAME: convertNTLZZpX2CF. More...
CanonicalForm	convertNTLzzpX2CF (const zz_pX &poly, const Variable &x)
CanonicalForm	convertNTLZZX2CF (const ZZX &polynom, const Variable &x)
CanonicalForm	convertNTLGF2X2CF (const GF2X &poly, const Variable &x)
	NAME: convertNTLGF2X2CF. More...
CFFList	convertNTLvec_pair_ZZpX_long2FacCFFList (const vec_pair_ZZ_pX_long &e, const ZZ_p &multi, const Variable &x)
	NAME: convertNTLvec_pair_ZZpX_long2FacCFFList. More...
CFFList	convertNTLvec_pair_zzpX_long2FacCFFList (const vec_pair_zz_pX_long &e, const zz_p multi, const Variable &x)
CFFList	convertNTLvec_pair_GF2X_long2FacCFFList (const vec_pair_GF2X_long &e, GF2, const Variable &x)
	NAME: convertNTLvec_pair_GF2X_long2FacCFFList. More...
CanonicalForm	convertZZ2CF (const ZZ &a)
	NAME: convertZZ2CF. More...
ZZ	convertFacCF2NTLZZ (const CanonicalForm &f)
	NAME: convertFacCF2NTLZZX. More...
ZZX	convertFacCF2NTLZZX (const CanonicalForm &f)
CFFList	convertNTLvec_pair_ZZX_long2FacCFFList (const vec_pair_ZZX_long &e, const ZZ &multi, const Variable &x)
	NAME: convertNTLvec_pair_ZZX_long2FacCFFList. More...
CanonicalForm	convertNTLZZpE2CF (const ZZ_pE &coefficient, const Variable &x)
	NAME: convertNTLZZpX2CF. More...
CanonicalForm	convertNTLzzpE2CF (const zz_pE &coefficient, const Variable &x)
CFFList	convertNTLvec_pair_ZZpEX_long2FacCFFList (const vec_pair_ZZ_pEX_long &e, const ZZ_pE &multi, const Variable &x, const Variable &alpha)
	NAME: convertNTLvec_pair_ZZpEX_long2FacCFFList. More...
CFFList	convertNTLvec_pair_zzpEX_long2FacCFFList (const vec_pair_zz_pEX_long &e, const zz_pE &multi, const Variable &x, const Variable &alpha)
CanonicalForm	convertNTLGF2E2CF (const GF2E &coefficient, const Variable &x)
	NAME: convertNTLGF2E2CF. More...
CFFList	convertNTLvec_pair_GF2EX_long2FacCFFList (const vec_pair_GF2EX_long &e, const GF2E &multi, const Variable &x, const Variable &alpha)
	NAME: convertNTLvec_pair_GF2EX_long2FacCFFList. More...
GF2EX	convertFacCF2NTLGF2EX (const CanonicalForm &f, const GF2X &mipo)
	CanonicalForm in Z_2(a)[X] to NTL GF2EX. More...
ZZ_pEX	convertFacCF2NTLZZ_pEX (const CanonicalForm &f, const ZZ_pX &mipo)
	CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX. More...
zz_pEX	convertFacCF2NTLzz_pEX (const CanonicalForm &f, const zz_pX &mipo)
CanonicalForm	convertNTLzz_pEX2CF (const zz_pEX &f, const Variable &x, const Variable &alpha)
CanonicalForm	convertNTLZZ_pEX2CF (const ZZ_pEX &f, const Variable &x, const Variable &alpha)
mat_ZZ *	convertFacCFMatrix2NTLmat_ZZ (const CFMatrix &m)
CFMatrix *	convertNTLmat_ZZ2FacCFMatrix (const mat_ZZ &m)
mat_zz_p *	convertFacCFMatrix2NTLmat_zz_p (const CFMatrix &m)
CFMatrix *	convertNTLmat_zz_p2FacCFMatrix (const mat_zz_p &m)
mat_zz_pE *	convertFacCFMatrix2NTLmat_zz_pE (const CFMatrix &m)
CFMatrix *	convertNTLmat_zz_pE2FacCFMatrix (const mat_zz_pE &m, const Variable &alpha)

Variables
long	fac_NTL_char = -1
static unsigned char *	cf_stringtemp
static unsigned long	cf_stringtemp_l =0L

Macro Definition Documentation

#define Alloc

(

L

)

malloc(L)

Definition at line 37 of file NTLconvert.cc.

#define Free	(		A,
			L
	)		free(A)

Definition at line 38 of file NTLconvert.cc.

Function Documentation

GF2EX convertFacCF2NTLGF2EX	(	const CanonicalForm &	f,
		const GF2X &	mipo
	)

CanonicalForm in Z_2(a)[X] to NTL GF2EX.

Definition at line 1001 of file NTLconvert.cc.

{
  GF2E::init(mipo);
  GF2EX result;
  CFIterator i;
  i=f;

  int NTLcurrentExp=i.exp();
  int largestExp=i.exp();
  int k;

  result.SetMaxLength(largestExp+1);
  for(;i.hasTerms();i++)
  {
    for(k=NTLcurrentExp;k>i.exp();k--) SetCoeff(result,k,0);
    NTLcurrentExp=i.exp();
    CanonicalForm c=i.coeff();
    GF2X cc=convertFacCF2NTLGF2X(c);
    //ZZ_pE ccc;
    //conv(ccc,cc);
    SetCoeff(result,NTLcurrentExp,to_GF2E(cc));
    NTLcurrentExp--;
  }
  for(k=NTLcurrentExp;k>=0;k--) SetCoeff(result,k,0);
  result.normalize();
  return result;
}

GF2X convertFacCF2NTLGF2X

(

const CanonicalForm &

f

)

NAME: convertFacCF2NTLGF2X.

DESCRIPTION: Conversion routine for Factory-type canonicalform into GF2X of NTL, i.e. polynomials over F_2. As precondition for correct execution, the characteristic must equal two. This is a special case of the more general conversion routine for canonicalform to ZZpX. It is included because NTL provides additional support and faster algorithms over F_2, moreover the conversion code can be optimized, because certain steps are either completely obsolent (like normalizing the polynomial) or they can be made significantly faster (like building up the NTL-polynomial).

INPUT: A canonicalform f OUTPUT: The converted NTL-polynomial over F_2 of type GF2X

Definition at line 179 of file NTLconvert.cc.

{
  //printf("convertFacCF2NTLGF2X\n");
  GF2X ntl_poly;

  CFIterator i;
  i=f;

  int NTLcurrentExp=i.exp();
  int largestExp=i.exp();
  int k;

  //building the NTL-polynomial
  ntl_poly.SetMaxLength(largestExp+1);

  for (;i.hasTerms();i++)
  {

    for (k=NTLcurrentExp;k>i.exp();k--)
    {
      SetCoeff(ntl_poly,k,0);
    }
    NTLcurrentExp=i.exp();

    if (!i.coeff().isImm()) i.coeff()=i.coeff().mapinto();
    if (!i.coeff().isImm())
    {
      #ifndef NOSTREAMIO
      cout<<"convertFacCF2NTLGF2X: coefficient not immidiate! : " << f << "\n";
      #else
      //NTL_SNS
      printf("convertFacCF2NTLGF2X: coefficient not immidiate!");
      #endif
      NTL_SNS exit(1);
    }
    else
    {
      SetCoeff(ntl_poly,NTLcurrentExp,i.coeff().intval());
    }
    NTLcurrentExp--;
  }
  for (k=NTLcurrentExp;k>=0;k--)
  {
    SetCoeff(ntl_poly,k,0);
  }
  //normalization is not necessary of F_2

  return ntl_poly;
}

ZZ convertFacCF2NTLZZ

(

const CanonicalForm &

f

)

NAME: convertFacCF2NTLZZX.

DESCRIPTION: Routine for conversion of canonicalforms in Factory to polynomials of type ZZX of NTL. To guarantee the correct execution of the algorithm the characteristic has to equal zero.

INPUT: The canonicalform that has to be converted OUTPUT: The converted NTL-polynom of type ZZX

Definition at line 659 of file NTLconvert.cc.

{
  ZZ temp;
  if (f.isImm()) temp=f.intval();
  else
  {
    //Coefficient is a gmp-number
    mpz_t gmp_val;
    char* stringtemp;

    f.mpzval (gmp_val);
    int l=mpz_sizeinbase(gmp_val,10)+2;
    stringtemp=(char*)Alloc(l);
    stringtemp=mpz_get_str(stringtemp,10,gmp_val);
    mpz_clear(gmp_val);
    conv(temp,stringtemp);
    Free(stringtemp,l);
  }
  return temp;
}

ZZ_pEX convertFacCF2NTLZZ_pEX	(	const CanonicalForm &	f,
		const ZZ_pX &	mipo
	)

CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX.

Definition at line 1031 of file NTLconvert.cc.

{
  ZZ_pE::init(mipo);
  ZZ_pEX result;
  CFIterator i;
  i=f;

  int NTLcurrentExp=i.exp();
  int largestExp=i.exp();
  int k;

  result.SetMaxLength(largestExp+1);
  for(;i.hasTerms();i++)
  {
    for(k=NTLcurrentExp;k>i.exp();k--) SetCoeff(result,k,0);
    NTLcurrentExp=i.exp();
    CanonicalForm c=i.coeff();
    ZZ_pX cc=convertFacCF2NTLZZpX(c);
    //ZZ_pE ccc;
    //conv(ccc,cc);
    SetCoeff(result,NTLcurrentExp,to_ZZ_pE(cc));
    NTLcurrentExp--;
  }
  for(k=NTLcurrentExp;k>=0;k--) SetCoeff(result,k,0);
  result.normalize();
  return result;
}

zz_pEX convertFacCF2NTLzz_pEX	(	const CanonicalForm &	f,
		const zz_pX &	mipo
	)

Definition at line 1058 of file NTLconvert.cc.

{
  zz_pE::init(mipo);
  zz_pEX result;
  CFIterator i;
  i=f;

  int NTLcurrentExp=i.exp();
  int largestExp=i.exp();
  int k;

  result.SetMaxLength(largestExp+1);
  for(;i.hasTerms();i++)
  {
    for(k=NTLcurrentExp;k>i.exp();k--) SetCoeff(result,k,0);
    NTLcurrentExp=i.exp();
    CanonicalForm c=i.coeff();
    zz_pX cc=convertFacCF2NTLzzpX(c);
    //ZZ_pE ccc;
    //conv(ccc,cc);
    SetCoeff(result,NTLcurrentExp,to_zz_pE(cc));
    NTLcurrentExp--;
  }
  for(k=NTLcurrentExp;k>=0;k--) SetCoeff(result,k,0);
  result.normalize();
  return result;
}

ZZ_pX convertFacCF2NTLZZpX

(

const CanonicalForm &

f

)

NAME: convertFacCF2NTLZZpX.

DESCRIPTION: Conversion routine for Factory-type canonicalform into ZZpX of NTL, i.e. polynomials over F_p. As a precondition for correct execution, the characteristic has to a a prime number.

INPUT: A canonicalform f OUTPUT: The converted NTL-polynomial over F_p of type ZZpX

Definition at line 61 of file NTLconvert.cc.

{
  ZZ_pX ntl_poly;

  CFIterator i;
  i=f;

  int NTLcurrentExp=i.exp();
  int largestExp=i.exp();
  int k;

  // we now build up the NTL-polynomial
  ntl_poly.SetMaxLength(largestExp+1);

  for (;i.hasTerms();i++)
  {
    for (k=NTLcurrentExp;k>i.exp();k--)
    {
      SetCoeff(ntl_poly,k,0);
    }
    NTLcurrentExp=i.exp();

    SetCoeff(ntl_poly,NTLcurrentExp,to_ZZ_p (convertFacCF2NTLZZ (i.coeff())));
    NTLcurrentExp--;
  }

  //Set the remaining coefficients of ntl_poly to zero.
  // This is necessary, because NTL internally
  // also stores powers with zero coefficient,
  // whereas factory stores tuples of degree and coefficient
  //leaving out tuples if the coefficient equals zero
  for (k=NTLcurrentExp;k>=0;k--)
  {
    SetCoeff(ntl_poly,k,0);
  }

  //normalize the polynomial and return it
  ntl_poly.normalize();

  return ntl_poly;
}

zz_pX convertFacCF2NTLzzpX

(

const CanonicalForm &

f

)

Definition at line 102 of file NTLconvert.cc.

{
  zz_pX ntl_poly;

  CFIterator i;
  i=f;

  int NTLcurrentExp=i.exp();
  int largestExp=i.exp();
  int k;

  // we now build up the NTL-polynomial
  ntl_poly.SetMaxLength(largestExp+1);

  for (;i.hasTerms();i++)
  {
    for (k=NTLcurrentExp;k>i.exp();k--)
    {
      SetCoeff(ntl_poly,k,0);
    }
    NTLcurrentExp=i.exp();

    CanonicalForm c=i.coeff();
    if (!c.isImm()) c=c.mapinto(); //c%= getCharacteristic();
    if (!c.isImm())
    {  //This case will never happen if the characteristic is in fact a prime
       // number, since all coefficients are represented as immediates
       #ifndef NOSTREAMIO
       cout<<"convertFacCF2NTLzz_pX: coefficient not immediate! : "<<f<<"\n";
       #else
       //NTL_SNS
       printf("convertFacCF2NTLzz_pX: coefficient not immediate!, char=%d\n",
              getCharacteristic());
       #endif
       NTL_SNS exit(1);
    }
    else
    {
      SetCoeff(ntl_poly,NTLcurrentExp,c.intval());
    }
    NTLcurrentExp--;
  }

  //Set the remaining coefficients of ntl_poly to zero.
  // This is necessary, because NTL internally
  // also stores powers with zero coefficient,
  // whereas factory stores tuples of degree and coefficient
  //leaving out tuples if the coefficient equals zero
  for (k=NTLcurrentExp;k>=0;k--)
  {
    SetCoeff(ntl_poly,k,0);
  }

  //normalize the polynomial and return it
  ntl_poly.normalize();

  return ntl_poly;
}

ZZX convertFacCF2NTLZZX

(

const CanonicalForm &

f

)

Definition at line 680 of file NTLconvert.cc.

{
    ZZX ntl_poly;

    CFIterator i;
    i=f;

    int NTLcurrentExp=i.exp();
    int largestExp=i.exp();
    int k;

    //set the length of the NTL-polynomial
    ntl_poly.SetMaxLength(largestExp+1);

    //Go through the coefficients of the canonicalform and build up the NTL-polynomial
    for (;i.hasTerms();i++)
    {
      for (k=NTLcurrentExp;k>i.exp();k--)
      {
        SetCoeff(ntl_poly,k,0);
      }
      NTLcurrentExp=i.exp();

      //Coefficient is a gmp-number
      ZZ temp=convertFacCF2NTLZZ(i.coeff());

      //set the computed coefficient
      SetCoeff(ntl_poly,NTLcurrentExp,temp);

      NTLcurrentExp--;
    }
    for (k=NTLcurrentExp;k>=0;k--)
    {
      SetCoeff(ntl_poly,k,0);
    }

    //normalize the polynomial
    ntl_poly.normalize();

    return ntl_poly;
}

mat_ZZ* convertFacCFMatrix2NTLmat_ZZ

(

const CFMatrix &

m

)

Definition at line 1132 of file NTLconvert.cc.

{
  mat_ZZ *res=new mat_ZZ;
  res->SetDims(m.rows(),m.columns());

  int i,j;
  for(i=m.rows();i>0;i--)
  {
    for(j=m.columns();j>0;j--)
    {
      (*res)(i,j)=convertFacCF2NTLZZ(m(i,j));
    }
  }
  return res;
}

mat_zz_p* convertFacCFMatrix2NTLmat_zz_p

(

const CFMatrix &

m

)

Definition at line 1161 of file NTLconvert.cc.

{
  mat_zz_p *res=new mat_zz_p;
  res->SetDims(m.rows(),m.columns());

  int i,j;
  for(i=m.rows();i>0;i--)
  {
    for(j=m.columns();j>0;j--)
    {
      if(!(m(i,j)).isImm()) printf("convertFacCFMatrix2NTLmat_zz_p: not imm.\n");
      (*res)(i,j)=(m(i,j)).intval();
    }
  }
  return res;
}

mat_zz_pE* convertFacCFMatrix2NTLmat_zz_pE

(

const CFMatrix &

m

)

Definition at line 1190 of file NTLconvert.cc.

{
  mat_zz_pE *res=new mat_zz_pE;
  res->SetDims(m.rows(),m.columns());

  int i,j;
  for(i=m.rows();i>0;i--)
  {
    for(j=m.columns();j>0;j--)
    {
      zz_pX cc=convertFacCF2NTLzzpX(m(i,j));
      (*res)(i,j)=to_zz_pE(cc);
    }
  }
  return res;
}

CanonicalForm convertNTLGF2E2CF	(	const GF2E &	coefficient,
		const Variable &	x
	)

NAME: convertNTLGF2E2CF.

DESCRIPTION: Routine for conversion of elements of extensions of GF2, having type GF2E, of NTL to their corresponding values of type canonicalform in Factory. To guarantee the correct execution of the algorithm, the characteristic must equal two and Factory has to compute in an extension of F_2. As usual this is an optimized special case of the more general conversion routine from ZZpE to Factory.

INPUT: The coefficient of type GF2E and the variable x indicating the main variable of the computed canonicalform OUTPUT: The converted value of coefficient as type canonicalform

Definition at line 922 of file NTLconvert.cc.

{
  return convertNTLGF2X2CF(rep(coefficient),x);
}

CanonicalForm convertNTLGF2X2CF	(	const GF2X &	poly,
		const Variable &	x
	)

NAME: convertNTLGF2X2CF.

DESCRIPTION: Conversion routine for NTL-Type GF2X to Factory-Type canonicalform, the routine is again an optimized special case of the more general conversion to ZZpX. Additionally a variable x is needed as a parameter indicating the main variable of the computed canonicalform. To guarantee the correct execution of the algorithm the characteristic has a be an arbitrary prime number.

INPUT: A canonicalform f, a variable x OUTPUT: The converted Factory-polynomial of type canonicalform, built by the main variable x

Definition at line 317 of file NTLconvert.cc.

{
  //printf("convertNTLGF2X2CF\n");
  CanonicalForm bigone;

  if (deg(poly)>0)
  {
    // poly is non-constant
    bigone=0;
    bigone.mapinto();
    // Compute the canonicalform coefficient by coefficient,
    // bigone summarizes the result.
    // In constrast to the more general conversion to ZZpX
    // the only possible coefficients are zero
    // and one yielding the following simplified loop
    for (int j=0;j<=deg(poly);j++)
    {
      if (coeff(poly,j)!=0) bigone+=power(x,j);
     // *CanonicalForm(to_long(rep(coeff(poly,j))))) is not necessary any more;
    }
  }
  else
  {
    // poly is immediate
    bigone=CanonicalForm(to_long(rep(coeff(poly,0))));
    bigone.mapinto();
  }

  return bigone;
}

CFMatrix* convertNTLmat_ZZ2FacCFMatrix

(

const mat_ZZ &

m

)

Definition at line 1147 of file NTLconvert.cc.

{
  CFMatrix *res=new CFMatrix(m.NumRows(),m.NumCols());
  int i,j;
  for(i=res->rows();i>0;i--)
  {
    for(j=res->columns();j>0;j--)
    {
      (*res)(i,j)=convertZZ2CF(m(i,j));
    }
  }
  return res;
}

CFMatrix* convertNTLmat_zz_p2FacCFMatrix

(

const mat_zz_p &

m

)

Definition at line 1177 of file NTLconvert.cc.

{
  CFMatrix *res=new CFMatrix(m.NumRows(),m.NumCols());
  int i,j;
  for(i=res->rows();i>0;i--)
  {
    for(j=res->columns();j>0;j--)
    {
      (*res)(i,j)=CanonicalForm(to_long(rep(m(i,j))));
    }
  }
  return res;
}

CFMatrix* convertNTLmat_zz_pE2FacCFMatrix	(	const mat_zz_pE &	m,
		const Variable &	alpha
	)

Definition at line 1206 of file NTLconvert.cc.

{
  CFMatrix *res=new CFMatrix(m.NumRows(),m.NumCols());
  int i,j;
  for(i=res->rows();i>0;i--)
  {
    for(j=res->columns();j>0;j--)
    {
      (*res)(i,j)=convertNTLzzpE2CF(m(i,j), alpha);
    }
  }
  return res;
}

CFFList convertNTLvec_pair_GF2EX_long2FacCFFList	(	const vec_pair_GF2EX_long &	e,
		const GF2E &	multi,
		const Variable &	x,
		const Variable &	alpha
	)

NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.

DESCRIPTION: Routine for converting a vector of polynomials from GF2EX to a CFFList of Factory. This routine will be used after a successful factorization of NTL to convert the result back to Factory. This is a special, but optimized case of the more general conversion from ZZpE to canonicalform. Additionally a variable x and the computed multiplicity, as a type GF2E of NTL, is needed as parameters indicating the main variable of the computed canonicalform and the multiplicity of the original polynomial. To guarantee the correct execution of the algorithm the characteristic has to equal two and computations have to be done in an extention of F_2.

INPUT: A vector of polynomials over GF2E of type vec_pair_GF2EX_long and a variable x and a multiplicity of type GF2E OUTPUT: The converted list of polynomials of type CFFList, all polynomials have x as their main variable

Definition at line 949 of file NTLconvert.cc.

{
  CFFList result;
  GF2EX polynom;
  long exponent;
  CanonicalForm bigone;

  // Maybe, e may additionally be sorted with respect to increasing degree of x, but this is not
  //important for the factorization, but nevertheless would take computing time, so it is omitted

  // multiplicity is always one, so we do not have to worry about that

  // Go through the vector e and build up the CFFList
  // As usual bigone summarizes the result during every loop
  for (int i=e.length()-1;i>=0;i--)
  {
    bigone=0;

    polynom=e[i].a;
    exponent=e[i].b;

    for (int j=0;j<=deg(polynom);j++)
    {
      if (IsOne(coeff(polynom,j)))
      {
        bigone+=power(x,j);
      }
      else
      {
        CanonicalForm coefficient=convertNTLGF2E2CF(coeff(polynom,j),alpha);
        if (coeff(polynom,j)!=0)
        {
          bigone += (power(x,j)*coefficient);
        }
      }
    }

    // append the computed polynomial together with its multiplicity
    result.append(CFFactor(bigone,exponent));

  }

  if (!IsOne(multi))
    result.insert(CFFactor(convertNTLGF2E2CF(multi,alpha),1));

  // return the computed CFFList
  return result;
}

CFFList convertNTLvec_pair_GF2X_long2FacCFFList	(	const vec_pair_GF2X_long &	e,
		GF2	,
		const Variable &	x
	)

NAME: convertNTLvec_pair_GF2X_long2FacCFFList.

DESCRIPTION: Routine for converting a vector of polynomials of type GF2X from NTL to a list CFFList of Factory. This routine will be used after a successful factorization of NTL to convert the result back to Factory. As usual this is simply a special case of the more general conversion routine but again speeded up by leaving out unnecessary steps. Additionally a variable x and the computed multiplicity, as type GF2 of NTL, are needed as parameters indicating the main variable of the computed canonicalform and the multiplicity of the original polynomial. To guarantee the correct execution of the algorithm the characteristic has a be an arbitrary prime number.

INPUT: A vector of polynomials over GF2 of type vec_pair_GF2X_long and a variable x and a multiplicity of type GF2 OUTPUT: The converted list of polynomials of type CFFList, all polynomials have x as their main variable

Definition at line 441 of file NTLconvert.cc.

{
  //printf("convertNTLvec_pair_GF2X_long2FacCFFList\n");
  CFFList result;
  GF2X polynom;
  long exponent;
  CanonicalForm bigone;

  // Maybe, e may additionally be sorted with respect to increasing degree of x
  // but this is not
  //important for the factorization, but nevertheless would take computing time
  // so it is omitted.

  //We do not have to worry about the multiplicity in GF2 since it equals one.

  // Go through the vector e and compute the CFFList
  // bigone summarizes the result again
  for (int i=e.length()-1;i>=0;i--)
  {
    bigone=0;

    polynom=e[i].a;
    exponent=e[i].b;
    for (int j=0;j<=deg(polynom);j++)
    {
      if (coeff(polynom,j)!=0)
        bigone += (power(x,j)*CanonicalForm(to_long(rep(coeff(polynom,j)))));
    }

    //append the converted polynomial to the CFFList
    result.append(CFFactor(bigone,exponent));
  }
  return result;
}

CFFList convertNTLvec_pair_ZZpEX_long2FacCFFList	(	const vec_pair_ZZ_pEX_long &	e,
		const ZZ_pE &	multi,
		const Variable &	x,
		const Variable &	alpha
	)

NAME: convertNTLvec_pair_ZZpEX_long2FacCFFList.

DESCRIPTION: Routine for converting a vector of polynomials from ZZpEX to a CFFList of Factory. This routine will be used after a successful factorization of NTL to convert the result back to Factory. Additionally a variable x and the computed multiplicity, as a type ZZpE of NTL, is needed as parameters indicating the main variable of the computed canonicalform and the multiplicity of the original polynomial. To guarantee the correct execution of the algorithm the characteristic has a be an arbitrary prime number p and computations have to be done in an extention of F_p.

INPUT: A vector of polynomials over ZZpE of type vec_pair_ZZ_pEX_long and a variable x and a multiplicity of type ZZpE OUTPUT: The converted list of polynomials of type CFFList, all polynomials have x as their main variable

Definition at line 815 of file NTLconvert.cc.

{
  CFFList result;
  ZZ_pEX polynom;
  long exponent;
  CanonicalForm bigone;

  // Maybe, e may additionally be sorted with respect to increasing degree of x, but this is not
  //important for the factorization, but nevertheless would take computing time, so it is omitted

  // Go through the vector e and build up the CFFList
  // As usual bigone summarizes the result during every loop
  for (int i=e.length()-1;i>=0;i--)
  {
    bigone=0;

    polynom=e[i].a;
    exponent=e[i].b;

    for (int j=0;j<=deg(polynom);j++)
    {
      if (IsOne(coeff(polynom,j)))
      {
        bigone+=power(x,j);
      }
      else
      {
        CanonicalForm coefficient=convertNTLZZpE2CF(coeff(polynom,j),alpha);
        if (coeff(polynom,j)!=0)
        {
          bigone += (power(x,j)*coefficient);
        }
      }
    }
    //append the computed polynomials together with its exponent to the CFFList
    result.append(CFFactor(bigone,exponent));
  }
  // Start by appending the multiplicity
  if (!IsOne(multi))
    result.insert(CFFactor(convertNTLZZpE2CF(multi,alpha),1));

  //return the computed CFFList
  return result;
}

CFFList convertNTLvec_pair_zzpEX_long2FacCFFList	(	const vec_pair_zz_pEX_long &	e,
		const zz_pE &	multi,
		const Variable &	x,
		const Variable &	alpha
	)

Definition at line 860 of file NTLconvert.cc.

{
  CFFList result;
  zz_pEX polynom;
  long exponent;
  CanonicalForm bigone;

  // Maybe, e may additionally be sorted with respect to increasing degree of x, but this is not
  //important for the factorization, but nevertheless would take computing time, so it is omitted

  // Go through the vector e and build up the CFFList
  // As usual bigone summarizes the result during every loop
  for (int i=e.length()-1;i>=0;i--)
  {
    bigone=0;

    polynom=e[i].a;
    exponent=e[i].b;

    for (int j=0;j<=deg(polynom);j++)
    {
      if (IsOne(coeff(polynom,j)))
      {
        bigone+=power(x,j);
      }
      else
      {
        CanonicalForm coefficient=convertNTLzzpE2CF(coeff(polynom,j),alpha);
        if (coeff(polynom,j)!=0)
        {
          bigone += (power(x,j)*coefficient);
        }
      }
    }
    //append the computed polynomials together with its exponent to the CFFList
    result.append(CFFactor(bigone,exponent));
  }
  // Start by appending the multiplicity
  if (!IsOne(multi))
    result.insert(CFFactor(convertNTLzzpE2CF(multi,alpha),1));

  //return the computed CFFList
  return result;
}

CFFList convertNTLvec_pair_ZZpX_long2FacCFFList	(	const vec_pair_ZZ_pX_long &	e,
		const ZZ_p &	multi,
		const Variable &	x
	)

NAME: convertNTLvec_pair_ZZpX_long2FacCFFList.

DESCRIPTION: Routine for converting a vector of polynomials from ZZpX to a CFFList of Factory. This routine will be used after a successful factorization of NTL to convert the result back to Factory.

Additionally a variable x and the computed multiplicity, as a type ZZp of NTL, is needed as parameters indicating the main variable of the computed canonicalform and the multiplicity of the original polynomial. To guarantee the correct execution of the algorithm the characteristic has a be an arbitrary prime number.

INPUT: A vector of polynomials over ZZp of type vec_pair_ZZ_pX_long and a variable x and a multiplicity of type ZZp OUTPUT: The converted list of polynomials of type CFFList, all polynomials have x as their main variable

Definition at line 369 of file NTLconvert.cc.

{
  //printf("convertNTLvec_pair_ZZpX_long2FacCFFList\n");
  CFFList result;
  ZZ_pX polynom;
  CanonicalForm bigone;

  // Maybe, e may additionally be sorted with respect to increasing degree of x
  // but this is not
  //important for the factorization, but nevertheless would take computing time,
  // so it is omitted


  // Go through the vector e and compute the CFFList
  // again bigone summarizes the result
  for (int i=e.length()-1;i>=0;i--)
  {
    result.append(CFFactor(convertNTLZZpX2CF(e[i].a,x),e[i].b));
  }
  // the multiplicity at pos 1
  if (!IsOne(multi))
    result.insert(CFFactor(CanonicalForm(to_long(rep(multi))),1));
  return result;
}

CFFList convertNTLvec_pair_zzpX_long2FacCFFList	(	const vec_pair_zz_pX_long &	e,
		const zz_p	multi,
		const Variable &	x
	)

Definition at line 394 of file NTLconvert.cc.

{
  //printf("convertNTLvec_pair_zzpX_long2FacCFFList\n");
  CFFList result;
  zz_pX polynom;
  CanonicalForm bigone;

  // Maybe, e may additionally be sorted with respect to increasing degree of x
  // but this is not
  //important for the factorization, but nevertheless would take computing time,
  // so it is omitted


  // Go through the vector e and compute the CFFList
  // again bigone summarizes the result
  for (int i=e.length()-1;i>=0;i--)
  {
    result.append(CFFactor(convertNTLzzpX2CF(e[i].a,x),e[i].b));
  }
  // the multiplicity at pos 1
  if (!IsOne(multi))
    result.insert(CFFactor(CanonicalForm(to_long(rep(multi))),1));
  return result;
}

CFFList convertNTLvec_pair_ZZX_long2FacCFFList	(	const vec_pair_ZZX_long &	e,
		const ZZ &	multi,
		const Variable &	x
	)

NAME: convertNTLvec_pair_ZZX_long2FacCFFList.

DESCRIPTION: Routine for converting a vector of polynomials from ZZ to a list CFFList of Factory. This routine will be used after a successful factorization of NTL to convert the result back to Factory. Additionally a variable x and the computed multiplicity, as a type ZZ of NTL, is needed as parameters indicating the main variable of the computed canonicalform and the multiplicity of the original polynomial. To guarantee the correct execution of the algorithm the characteristic has to equal zero.

INPUT: A vector of polynomials over ZZ of type vec_pair_ZZX_long and a variable x and a multiplicity of type ZZ OUTPUT: The converted list of polynomials of type CFFList, all have x as their main variable

Definition at line 742 of file NTLconvert.cc.

{
  CFFList result;
  ZZX polynom;
  long exponent;
  CanonicalForm bigone;

  // Go through the vector e and build up the CFFList
  // As usual bigone summarizes the result
  for (int i=e.length()-1;i>=0;i--)
  {
    ZZ coefficient;
    polynom=e[i].a;
    exponent=e[i].b;
    bigone=convertNTLZZX2CF(polynom,x);
    //append the converted polynomial to the list
    result.append(CFFactor(bigone,exponent));
  }
  // the multiplicity at pos 1
  //if (!IsOne(multi))
    result.insert(CFFactor(convertZZ2CF(multi),1));

  //return the converted list
  return result;
}

CanonicalForm convertNTLzz_pEX2CF	(	const zz_pEX &	f,
		const Variable &	x,
		const Variable &	alpha
	)

Definition at line 1086 of file NTLconvert.cc.

{
  CanonicalForm bigone;
  if (deg (f) > 0)
  {
    bigone= 0;
    bigone.mapinto();
    for (int j=0;j<deg(f)+1;j++)
    {
      if (coeff(f,j)!=0)
      {
        bigone+=(power(x,j)*convertNTLzzpE2CF(coeff(f,j),alpha));
      }
    }
  }
  else
  {
    bigone= convertNTLzzpE2CF(coeff(f,0),alpha);
    bigone.mapinto();
  }
  return bigone;
}

CanonicalForm convertNTLZZ_pEX2CF	(	const ZZ_pEX &	f,
		const Variable &	x,
		const Variable &	alpha
	)

Definition at line 1109 of file NTLconvert.cc.

{
  CanonicalForm bigone;
  if (deg (f) > 0)
  {
    bigone= 0;
    bigone.mapinto();
    for (int j=0;j<deg(f)+1;j++)
    {
      if (coeff(f,j)!=0)
      {
        bigone+=(power(x,j)*convertNTLZZpE2CF(coeff(f,j),alpha));
      }
    }
  }
  else
  {
    bigone= convertNTLZZpE2CF(coeff(f,0),alpha);
    bigone.mapinto();
  }
  return bigone;
}

CanonicalForm convertNTLZZpE2CF	(	const ZZ_pE &	coefficient,
		const Variable &	x
	)

NAME: convertNTLZZpX2CF.

DESCRIPTION: Routine for conversion of elements of arbitrary extensions of ZZp, having type ZZpE, of NTL to their corresponding values of type canonicalform in Factory. To guarantee the correct execution of the algorithm the characteristic has to be an arbitrary prime number and Factory has to compute in an extension of F_p.

INPUT: The coefficient of type ZZpE and the variable x indicating the main// variable of the computed canonicalform OUTPUT: The converted value of coefficient as type canonicalform

Definition at line 785 of file NTLconvert.cc.

{
  return convertNTLZZpX2CF(rep(coefficient),x);
}

CanonicalForm convertNTLzzpE2CF	(	const zz_pE &	coefficient,
		const Variable &	x
	)

Definition at line 789 of file NTLconvert.cc.

{
  return convertNTLzzpX2CF(rep(coefficient),x);
}

CanonicalForm convertNTLZZpX2CF	(	const ZZ_pX &	poly,
		const Variable &	x
	)

NAME: convertNTLZZpX2CF.

DESCRIPTION: Conversion routine for NTL-Type ZZpX to Factory-Type canonicalform. Additionally a variable x is needed as a parameter indicating the main variable of the computed canonicalform. To guarantee the correct execution of the algorithm, the characteristic has a be an arbitrary prime number.

INPUT: A canonicalform f, a variable x OUTPUT: The converted Factory-polynomial of type canonicalform, built by the main variable x

Definition at line 245 of file NTLconvert.cc.

{
  return convertNTLZZX2CF (to_ZZX (poly), x);
}

CanonicalForm convertNTLzzpX2CF	(	const zz_pX &	poly,
		const Variable &	x
	)

Definition at line 250 of file NTLconvert.cc.

{
  //printf("convertNTLzzpX2CF\n");
  CanonicalForm bigone;


  if (deg(poly)>0)
  {
    // poly is non-constant
    bigone=0;
    bigone.mapinto();
    // Compute the canonicalform coefficient by coefficient,
    // bigone summarizes the result.
    for (int j=0;j<=deg(poly);j++)
    {
      if (coeff(poly,j)!=0)
      {
        bigone+=(power(x,j)*CanonicalForm(to_long(rep(coeff(poly,j)))));
      }
    }
  }
  else
  {
    // poly is immediate
    bigone=CanonicalForm(to_long(rep(coeff(poly,0))));
    bigone.mapinto();
  }
  return bigone;
}

CanonicalForm convertNTLZZX2CF	(	const ZZX &	polynom,
		const Variable &	x
	)

Definition at line 280 of file NTLconvert.cc.

{
  //printf("convertNTLZZX2CF\n");
  CanonicalForm bigone;

  // Go through the vector e and build up the CFFList
  // As usual bigone summarizes the result
  bigone=0;
  ZZ coefficient;

  for (int j=0;j<=deg(polynom);j++)
  {
    coefficient=coeff(polynom,j);
    if (!IsZero(coefficient))
    {
      bigone += (power(x,j)*convertZZ2CF(coefficient));
    }
  }
  return bigone;
}

CanonicalForm convertZZ2CF

(

const ZZ &

a

)

NAME: convertZZ2CF.

DESCRIPTION: Routine for conversion of integers represented in NTL as Type ZZ to integers in Factory represented as canonicalform. To guarantee the correct execution of the algorithm the characteristic has to equal zero.

INPUT: The value coefficient of type ZZ that has to be converted OUTPUT: The converted Factory-integer of type canonicalform

Definition at line 491 of file NTLconvert.cc.

{
  long coeff_long=to_long(a);

  CanonicalForm result;
  if ( (NumBits(a)<((long)NTL_ZZ_NBITS))
  && (coeff_long>((long)MINIMMEDIATE))
  && (coeff_long<((long)MAXIMMEDIATE)))
  {
    return CanonicalForm(coeff_long);
  }
  else
  {
    long sizeofrep= ((long *) a.rep) [1];
    bool lessZero= false;
    if (sizeofrep < 0)
    {
      lessZero= true;
      sizeofrep= -sizeofrep;
    }
    if (cf_stringtemp_l == 0)
    {
      cf_stringtemp_l= sizeofrep*sizeof(mp_limb_t)*2;
      cf_stringtemp= (unsigned char*) Alloc (cf_stringtemp_l);
    }
    else if (cf_stringtemp_l < sizeofrep*sizeof(mp_limb_t)*2)
    {
      Free (cf_stringtemp, cf_stringtemp_l);
      cf_stringtemp_l= sizeofrep*sizeof(mp_limb_t)*2;
      cf_stringtemp= (unsigned char*) Alloc (cf_stringtemp_l);
    }
    int cc= mpn_get_str (cf_stringtemp, 16, (mp_limb_t *) (((long *) (a.rep)) + 2), sizeofrep);

    char* cf_stringtemp2;
    if (lessZero)
    {
      cf_stringtemp2= new char [cc + 2];
      cf_stringtemp2[0]='-';
      for (int j= 1; j <= cc; j++)
        cf_stringtemp2[j]= IntValToChar ((int) cf_stringtemp [j-1]);
      cf_stringtemp2[cc+1]='\0';
    }
    else
    {
      cf_stringtemp2= new char [cc + 1];
      for (int j= 0; j < cc; j++)
        cf_stringtemp2[j]= IntValToChar ((int) cf_stringtemp [j]);
      cf_stringtemp2[cc]='\0';
    }

    result= CanonicalForm (cf_stringtemp2, 16);
    delete [] cf_stringtemp2;
    return result;
  }
  return result;
}

void out_cf	(	const char *	s1,
		const CanonicalForm &	f,
		const char *	s2
	)

cf_algorithm.cc - simple mathematical algorithms.

Hierarchy: mathematical algorithms on canonical forms

Developers note:

A "mathematical" algorithm is an algorithm which calculates some mathematical function in contrast to a "structural" algorithm which gives structural information on polynomials.

Compare these functions to the functions in `cf_ops.cc', which are structural algorithms.

Definition at line 90 of file cf_factor.cc.

{
  printf("%s",s1);
  if (f.isZero()) printf("+0");
  //else if (! f.inCoeffDomain() )
  else if (! f.inBaseDomain() )
  {
    int l = f.level();
    for ( CFIterator i = f; i.hasTerms(); i++ )
    {
      int e=i.exp();
      if (i.coeff().isOne())
      {
        printf("+");
        if (e==0) printf("1");
        else
        {
          printf("v(%d)",l);
          if (e!=1) printf("^%d",e);
        }
      }
      else
      {
        out_cf("+(",i.coeff(),")");
        if (e!=0)
        {
          printf("*v(%d)",l);
          if (e!=1) printf("^%d",e);
        }
      }
    }
  }
  else
  {
    if ( f.isImm() )
    {
      if (CFFactory::gettype()==GaloisFieldDomain)
      {
         long a= imm2int (f.getval());
         if ( a == gf_q )
           printf ("+%ld", a);
         else  if ( a == 0L )
           printf ("+1");
         else  if ( a == 1L )
           printf ("+%c",gf_name);
         else
         {
           printf ("+%c",gf_name);
           printf ("^%ld",a);
         }
      }
      else
        printf("+%ld",f.intval());
    }
    else
    {
    #ifdef NOSTREAMIO
      if (f.inZ())
      {
        mpz_t m;
        gmp_numerator(f,m);
        char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
        str = mpz_get_str( str, 10, m );
        printf("%s",str);
        delete[] str;
        mpz_clear(m);
      }
      else if (f.inQ())
      {
        mpz_t m;
        gmp_numerator(f,m);
        char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
        str = mpz_get_str( str, 10, m );
        printf("%s/",str);
        delete[] str;
        mpz_clear(m);
        gmp_denominator(f,m);
        str = new char[mpz_sizeinbase( m, 10 ) + 2];
        str = mpz_get_str( str, 10, m );
        printf("%s",str);
        delete[] str;
        mpz_clear(m);
      }
    #else
       std::cout << f;
    #endif
    }
    //if (f.inZ()) printf("(Z)");
    //else if (f.inQ()) printf("(Q)");
    //else if (f.inFF()) printf("(FF)");
    //else if (f.inPP()) printf("(PP)");
    //else if (f.inGF()) printf("(PP)");
    //else
    if (f.inExtension()) printf("E(%d)",f.level());
  }
  printf("%s",s2);
}

Variable Documentation

unsigned char* cf_stringtemp

static

Definition at line 476 of file NTLconvert.cc.

unsigned long cf_stringtemp_l =0L

static

Definition at line 477 of file NTLconvert.cc.

long fac_NTL_char = -1

Definition at line 43 of file NTLconvert.cc.