facMul.h File Reference

This file defines functions for fast multiplication and division with remainder. More...

#include "canonicalform.h"
#include "fac_util.h"

Go to the source code of this file.

Functions
CanonicalForm	mulNTL (const CanonicalForm &F, const CanonicalForm &G, const modpk &b=modpk())
	multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f). More...
CanonicalForm	modNTL (const CanonicalForm &F, const CanonicalForm &G, const modpk &b=modpk())
	mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked More...
CanonicalForm	divNTL (const CanonicalForm &F, const CanonicalForm &G, const modpk &b=modpk())
	division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked More...
void	divrem2 (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CanonicalForm &M)
	division with remainder of F by G wrt Variable (1) modulo M. Uses an algorithm based on Burnikel, Ziegler "Fast recursive division". More...
void FACTORY_PUBLIC	divrem (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &MOD)
	division with remainder of F by G wrt Variable (1) modulo MOD. Uses an algorithm based on Burnikel, Ziegler "Fast recursive division". More...
void	newtonDivrem (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CanonicalForm &M)
	division with remainder of F by G wrt Variable (1) modulo M using Newton inversion More...
CanonicalForm	newtonDiv (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
	division of F by G wrt Variable (1) modulo M using Newton inversion More...
bool	uniFdivides (const CanonicalForm &A, const CanonicalForm &B)
	divisibility test for univariate polys More...
CanonicalForm	mulMod2 (const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
	Karatsuba style modular multiplication for bivariate polynomials. More...
CanonicalForm	mulMod (const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
	Karatsuba style modular multiplication for multivariate polynomials. More...
CanonicalForm	mod (const CanonicalForm &F, const CFList &M)
	reduce F modulo elements in M. More...
CanonicalForm	prodMod (const CFList &L, const CanonicalForm &M)
	product of all elements in L modulo M via divide-and-conquer. More...
CanonicalForm	prodMod (const CFList &L, const CFList &M)
	product of all elements in L modulo M via divide-and-conquer. More...
void	newtonDivrem (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R)
	division with remainder of univariate polynomials over Q and Q(a) using Newton inversion, satisfying F=G*Q+R, deg(R) < deg(G) More...

Detailed Description

This file defines functions for fast multiplication and division with remainder.

Author

Martin Lee

Definition in file facMul.h.

Function Documentation

divNTL()

CanonicalForm divNTL	(	const CanonicalForm &	F,
		const CanonicalForm &	G,
		const modpk &	b = modpk()
	)

division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked

Returns

divNTL returns F/G

Parameters

[in]	F	a univariate poly
[in]	G	a univariate poly
[in]	b	coeff bound

Definition at line 936 of file facMul.cc.

{
  if (CFFactory::gettype() == GaloisFieldDomain)
    return div (F, G);
  if (F.inCoeffDomain() && G.isUnivariate() && !G.inCoeffDomain())
  {
    return 0;
  }
  else if (F.inCoeffDomain() && G.inCoeffDomain())
  {
    if (b.getp() != 0)
    {
      if (!F.inBaseDomain() || !G.inBaseDomain())
      {
        Variable alpha;
        hasFirstAlgVar (F, alpha);
        hasFirstAlgVar (G, alpha);
#if (HAVE_FLINT &&  __FLINT_RELEASE >= 20400)
        fmpz_t FLINTp;
        fmpz_mod_poly_t FLINTmipo;
        fq_ctx_t fq_con;
        fq_t FLINTF, FLINTG;
 
        fmpz_init (FLINTp);
        convertCF2initFmpz (FLINTp, b.getpk());
 
        convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
 
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_ctx_t fmpz_ctx;
        fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
        fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
        #else
        fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
        #endif
 
        convertFacCF2Fq_t (FLINTF, F, fq_con);
        convertFacCF2Fq_t (FLINTG, G, fq_con);
 
        fq_inv (FLINTG, FLINTG, fq_con);
        fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
 
        CanonicalForm result= convertFq_t2FacCF (FLINTF, alpha);
 
        fmpz_clear (FLINTp);
        fq_clear (FLINTF, fq_con);
        fq_clear (FLINTG, fq_con);
        fq_ctx_clear (fq_con);
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
        fmpz_mod_ctx_clear(fmpz_ctx);
        #else
        fmpz_mod_poly_clear (FLINTmipo);
        #endif
        return b (result);
#else
        ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
        ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
        ZZ_pE::init (NTLmipo);
        ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
        ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
        ZZ_pE result;
        div (result, to_ZZ_pE (NTLf), to_ZZ_pE (NTLg));
        return b (convertNTLZZpX2CF (rep (result), alpha));
#endif
      }
      return b(div (F,G));
    }
    return div (F, G);
  }
  else if (F.isUnivariate() && G.inCoeffDomain())
  {
    if (b.getp() != 0)
    {
      if (!G.inBaseDomain())
      {
        Variable alpha;
        hasFirstAlgVar (G, alpha);
#if (HAVE_FLINT &&  __FLINT_RELEASE >= 20400)
        fmpz_t FLINTp;
        fmpz_mod_poly_t FLINTmipo;
        fq_ctx_t fq_con;
        fq_poly_t FLINTF;
        fq_t FLINTG;
 
        fmpz_init (FLINTp);
        convertCF2initFmpz (FLINTp, b.getpk());
 
        convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
 
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_ctx_t fmpz_ctx;
        fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
        fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
        #else
        fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
        #endif
 
        convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
        convertFacCF2Fq_t (FLINTG, G, fq_con);
 
        fq_inv (FLINTG, FLINTG, fq_con);
        fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
 
        CanonicalForm result= convertFq_poly_t2FacCF (FLINTF, F.mvar(),
                                                      alpha, fq_con);
 
        fmpz_clear (FLINTp);
        fq_poly_clear (FLINTF, fq_con);
        fq_clear (FLINTG, fq_con);
        fq_ctx_clear (fq_con);
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
        fmpz_mod_ctx_clear(fmpz_ctx);
        #else
        fmpz_mod_poly_clear (FLINTmipo);
        #endif
        return b (result);
#else
        ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
        ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
        ZZ_pE::init (NTLmipo);
        ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
        ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
        div (NTLf, NTLf, to_ZZ_pE (NTLg));
        return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
#endif
      }
      return b(div (F,G));
    }
    return div (F, G);
  }
 
  if (getCharacteristic() == 0)
  {
 
    Variable alpha;
    if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G, alpha))
    {
#ifdef HAVE_FLINT
      if (b.getp() != 0)
      {
        fmpz_t FLINTpk;
        fmpz_init (FLINTpk);
        convertCF2initFmpz (FLINTpk, b.getpk());
        fmpz_mod_poly_t FLINTF, FLINTG;
        convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
        convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_ctx_t fmpz_ctx;
        fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
        fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fmpz_ctx);
        #else
        fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG);
        #endif
        CanonicalForm result= convertFmpz_mod_poly_t2FacCF (FLINTF,F.mvar(),b);
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_poly_clear (FLINTG, fmpz_ctx);
        fmpz_mod_poly_clear (FLINTF, fmpz_ctx);
        fmpz_mod_ctx_clear(fmpz_ctx);
        #else
        fmpz_mod_poly_clear (FLINTG);
        fmpz_mod_poly_clear (FLINTF);
        #endif
        fmpz_clear (FLINTpk);
        return result;
      }
      return divFLINTQ (F,G);
#else
      if (b.getp() != 0)
      {
        ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
        ZZX ZZf= convertFacCF2NTLZZX (F);
        ZZX ZZg= convertFacCF2NTLZZX (G);
        ZZ_pX NTLf= to_ZZ_pX (ZZf);
        ZZ_pX NTLg= to_ZZ_pX (ZZg);
        div (NTLf, NTLf, NTLg);
        return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
      }
      return div (F, G);
#endif
    }
    else
    {
      if (b.getp() != 0)
      {
#if (HAVE_FLINT &&  __FLINT_RELEASE >= 20400)
        fmpz_t FLINTp;
        fmpz_mod_poly_t FLINTmipo;
        fq_ctx_t fq_con;
        fq_poly_t FLINTF, FLINTG;
 
        fmpz_init (FLINTp);
        convertCF2initFmpz (FLINTp, b.getpk());
 
        convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
 
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_ctx_t fmpz_ctx;
        fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
        fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
        #else
        fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
        #endif
 
        convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
        convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
 
        fq_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
 
        CanonicalForm result= convertFq_poly_t2FacCF (FLINTF, F.mvar(),
                                                      alpha, fq_con);
 
        fmpz_clear (FLINTp);
        fq_poly_clear (FLINTF, fq_con);
        fq_poly_clear (FLINTG, fq_con);
        fq_ctx_clear (fq_con);
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
        fmpz_mod_ctx_clear(fmpz_ctx);
        #else
        fmpz_mod_poly_clear (FLINTmipo);
        #endif
        return b (result);
#else
        ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
        ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
        ZZ_pE::init (NTLmipo);
        ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
        ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
        div (NTLf, NTLf, NTLg);
        return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
#endif
      }
#ifdef HAVE_FLINT
      CanonicalForm Q;
      newtonDiv (F, G, Q);
      return Q;
#else
      return div (F,G);
#endif
    }
  }
 
  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
  ASSERT (F.level() == G.level(), "expected polys of same level");
#if (!defined(HAVE_FLINT) ||  __FLINT_RELEASE < 20400)
  if (fac_NTL_char != getCharacteristic())
  {
    fac_NTL_char= getCharacteristic();
    zz_p::init (getCharacteristic());
  }
#endif
  Variable alpha;
  CanonicalForm result;
  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
  {
#if (HAVE_FLINT &&  __FLINT_RELEASE >= 20400)
    nmod_poly_t FLINTmipo;
    fq_nmod_ctx_t fq_con;
 
    nmod_poly_init (FLINTmipo, getCharacteristic());
    convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
 
    fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
 
    fq_nmod_poly_t FLINTF, FLINTG;
    convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
    convertFacCF2Fq_nmod_poly_t (FLINTG, G, fq_con);
 
    fq_nmod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
 
    result= convertFq_nmod_poly_t2FacCF (FLINTF, F.mvar(), alpha, fq_con);
 
    fq_nmod_poly_clear (FLINTF, fq_con);
    fq_nmod_poly_clear (FLINTG, fq_con);
    nmod_poly_clear (FLINTmipo);
    fq_nmod_ctx_clear (fq_con);
#else
    zz_pX NTLMipo= convertFacCF2NTLzzpX(getMipo (alpha));
    zz_pE::init (NTLMipo);
    zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
    zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
    div (NTLF, NTLF, NTLG);
    result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
#endif
  }
  else
  {
#ifdef HAVE_FLINT
    nmod_poly_t FLINTF, FLINTG;
    convertFacCF2nmod_poly_t (FLINTF, F);
    convertFacCF2nmod_poly_t (FLINTG, G);
    nmod_poly_div (FLINTF, FLINTF, FLINTG);
    result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
    nmod_poly_clear (FLINTF);
    nmod_poly_clear (FLINTG);
#else
    zz_pX NTLF= convertFacCF2NTLzzpX (F);
    zz_pX NTLG= convertFacCF2NTLzzpX (G);
    div (NTLF, NTLF, NTLG);
    result= convertNTLzzpX2CF(NTLF, F.mvar());
#endif
  }
  return result;
}

divrem()

void FACTORY_PUBLIC divrem	(	const CanonicalForm &	F,
		const CanonicalForm &	G,
		CanonicalForm &	Q,
		CanonicalForm &	R,
		const CFList &	MOD
	)

division with remainder of F by G wrt Variable (1) modulo MOD. Uses an algorithm based on Burnikel, Ziegler "Fast recursive division".

See also

divrem2()

Parameters

[in]	F	multivariate, compressed polynomial
[in]	G	multivariate, compressed polynomial
[in,out]	Q	dividend
[in,out]	R	remainder, degree (R, 1) < degree (G, 1)
[in]	MOD	only contains powers of Variables of level higher than 1

Definition at line 3716 of file facMul.cc.

{
  CanonicalForm A= mod (F, MOD);
  CanonicalForm B= mod (G, MOD);
  Variable x= Variable (1);
  int degB= degree (B, x);
  if (degB > degree (A, x))
  {
    Q= 0;
    R= A;
    return;
  }
 
  if (degB <= 0)
  {
    divrem (A, B, Q, R);
    Q= mod (Q, MOD);
    R= mod (R, MOD);
    return;
  }
  CFList splitA= split (A, degB, x);
 
  CanonicalForm xToDegB= power (x, degB);
  CanonicalForm H, bufQ;
  Q= 0;
  CFListIterator i= splitA;
  H= i.getItem()*xToDegB;
  i++;
  H += i.getItem();
  while (i.hasItem())
  {
    divrem21 (H, B, bufQ, R, MOD);
    i++;
    if (i.hasItem())
      H= R*xToDegB + i.getItem();
    Q *= xToDegB;
    Q += bufQ;
  }
  return;
}

divrem2()

void divrem2	(	const CanonicalForm &	F,
		const CanonicalForm &	G,
		CanonicalForm &	Q,
		CanonicalForm &	R,
		const CanonicalForm &	M
	)

division with remainder of F by G wrt Variable (1) modulo M. Uses an algorithm based on Burnikel, Ziegler "Fast recursive division".

Returns

Q returns the dividend, R returns the remainder.

See also

divrem()

Parameters

[in]	F	bivariate, compressed polynomial
[in]	G	bivariate, compressed polynomial
[in,out]	Q	dividend
[in,out]	R	remainder, degree (R, 1) < degree (G, 1)
[in]	M	power of Variable (2)

Definition at line 3649 of file facMul.cc.

{
  CanonicalForm A= mod (F, M);
  CanonicalForm B= mod (G, M);
 
  if (B.inCoeffDomain())
  {
    divrem (A, B, Q, R);
    return;
  }
  if (A.inCoeffDomain() && !B.inCoeffDomain())
  {
    Q= 0;
    R= A;
    return;
  }
 
  if (B.level() < A.level())
  {
    divrem (A, B, Q, R);
    return;
  }
  if (A.level() > B.level())
  {
    R= A;
    Q= 0;
    return;
  }
  if (B.level() == 1 && B.isUnivariate())
  {
    divrem (A, B, Q, R);
    return;
  }
 
  Variable x= Variable (1);
  int degB= degree (B, x);
  if (degB > degree (A, x))
  {
    Q= 0;
    R= A;
    return;
  }
 
  CFList splitA= split (A, degB, x);
 
  CanonicalForm xToDegB= power (x, degB);
  CanonicalForm H, bufQ;
  Q= 0;
  CFListIterator i= splitA;
  H= i.getItem()*xToDegB;
  i++;
  H += i.getItem();
  CFList buf;
  while (i.hasItem())
  {
    buf= CFList (M);
    divrem21 (H, B, bufQ, R, buf);
    i++;
    if (i.hasItem())
      H= R*xToDegB + i.getItem();
    Q *= xToDegB;
    Q += bufQ;
  }
  return;
}

mod()

CanonicalForm mod	(	const CanonicalForm &	F,
		const CFList &	M
	)

reduce F modulo elements in M.

Returns

mod returns F modulo M

Parameters

[in]	F	compressed polynomial
[in]	M	list containing only univariate polynomials

Definition at line 3072 of file facMul.cc.

{
  CanonicalForm A= F;
  for (CFListIterator i= M; i.hasItem(); i++)
    A= mod (A, i.getItem());
  return A;
}

modNTL()

CanonicalForm modNTL	(	const CanonicalForm &	F,
		const CanonicalForm &	G,
		const modpk &	b = modpk()
	)

mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked

Returns

modNTL returns F mod G

Parameters

[in]	F	a univariate poly
[in]	G	a univariate poly
[in]	b	coeff bound

Definition at line 731 of file facMul.cc.

{
  if (CFFactory::gettype() == GaloisFieldDomain)
    return mod (F, G);
  if (F.inCoeffDomain() && G.isUnivariate() && !G.inCoeffDomain())
  {
    if (b.getp() != 0)
      return b(F);
    return F;
  }
  else if (F.inCoeffDomain() && G.inCoeffDomain())
  {
    if (b.getp() != 0)
      return b(F%G);
    return mod (F, G);
  }
  else if (F.isUnivariate() && G.inCoeffDomain())
  {
    if (b.getp() != 0)
      return b(F%G);
    return mod (F,G);
  }
 
  if (getCharacteristic() == 0)
  {
    Variable alpha;
    if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G, alpha))
    {
#ifdef HAVE_FLINT
      if (b.getp() != 0)
      {
        fmpz_t FLINTpk;
        fmpz_init (FLINTpk);
        convertCF2initFmpz (FLINTpk, b.getpk());
        fmpz_mod_poly_t FLINTF, FLINTG;
        convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
        convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_ctx_t fmpz_ctx;
        fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
        fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG, fmpz_ctx);
        #else
        fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
        #endif
        CanonicalForm result= convertFmpz_mod_poly_t2FacCF (FLINTF,F.mvar(),b);
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_poly_clear (FLINTG, fmpz_ctx);
        fmpz_mod_poly_clear (FLINTF, fmpz_ctx);
        fmpz_mod_ctx_clear(fmpz_ctx);
        #else
        fmpz_mod_poly_clear (FLINTG);
        fmpz_mod_poly_clear (FLINTF);
        #endif
        fmpz_clear (FLINTpk);
        return result;
      }
      return modFLINTQ (F, G);
#else
      if (b.getp() != 0)
      {
        ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
        ZZX ZZf= convertFacCF2NTLZZX (F);
        ZZX ZZg= convertFacCF2NTLZZX (G);
        ZZ_pX NTLf= to_ZZ_pX (ZZf);
        ZZ_pX NTLg= to_ZZ_pX (ZZg);
        rem (NTLf, NTLf, NTLg);
        return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
      }
      return mod (F, G);
#endif
    }
    else
    {
      if (b.getp() != 0)
      {
#if (HAVE_FLINT &&  __FLINT_RELEASE >= 20400)
        fmpz_t FLINTp;
        fmpz_mod_poly_t FLINTmipo;
        fq_ctx_t fq_con;
        fq_poly_t FLINTF, FLINTG;
 
        fmpz_init (FLINTp);
 
        convertCF2initFmpz (FLINTp, b.getpk());
 
        CanonicalForm mipo=getMipo (alpha);
        bool rat=isOn(SW_RATIONAL);
        On(SW_RATIONAL);
        CanonicalForm cd = bCommonDen(mipo);
        mipo *= cd;
        if (!rat) Off(SW_RATIONAL);
        convertFacCF2Fmpz_mod_poly_t (FLINTmipo, mipo, FLINTp);
 
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_ctx_t fmpz_ctx;
        fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
        fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
        #else
        fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
        #endif
 
        convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
        convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
 
        fq_poly_rem (FLINTF, FLINTF, FLINTG, fq_con);
 
        CanonicalForm result= convertFq_poly_t2FacCF (FLINTF, F.mvar(),
                                                      alpha, fq_con);
 
        fmpz_clear (FLINTp);
        fq_poly_clear (FLINTF, fq_con);
        fq_poly_clear (FLINTG, fq_con);
        fq_ctx_clear (fq_con);
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
        fmpz_mod_ctx_clear(fmpz_ctx);
        #else
        fmpz_mod_poly_clear (FLINTmipo);
        #endif
 
        return b(result);
#else
        ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
        ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
        ZZ_pE::init (NTLmipo);
        ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
        ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
        rem (NTLf, NTLf, NTLg);
        return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
#endif
      }
#ifdef HAVE_FLINT
      CanonicalForm Q, R;
      newtonDivrem (F, G, Q, R);
      return R;
#else
      return mod (F,G);
#endif
    }
  }
 
  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
  ASSERT (F.level() == G.level(), "expected polys of same level");
#if (!defined(HAVE_FLINT) ||  __FLINT_RELEASE < 20400)
  if (fac_NTL_char != getCharacteristic())
  {
    fac_NTL_char= getCharacteristic();
    zz_p::init (getCharacteristic());
  }
#endif
  Variable alpha;
  CanonicalForm result;
  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
  {
#if (HAVE_FLINT &&  __FLINT_RELEASE >= 20400)
    nmod_poly_t FLINTmipo;
    fq_nmod_ctx_t fq_con;
 
    nmod_poly_init (FLINTmipo, getCharacteristic());
    convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
 
    fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
 
    fq_nmod_poly_t FLINTF, FLINTG;
    convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
    convertFacCF2Fq_nmod_poly_t (FLINTG, G, fq_con);
 
    fq_nmod_poly_rem (FLINTF, FLINTF, FLINTG, fq_con);
 
    result= convertFq_nmod_poly_t2FacCF (FLINTF, F.mvar(), alpha, fq_con);
 
    fq_nmod_poly_clear (FLINTF, fq_con);
    fq_nmod_poly_clear (FLINTG, fq_con);
    nmod_poly_clear (FLINTmipo);
    fq_nmod_ctx_clear (fq_con);
#else
    zz_pX NTLMipo= convertFacCF2NTLzzpX(getMipo (alpha));
    zz_pE::init (NTLMipo);
    zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
    zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
    rem (NTLF, NTLF, NTLG);
    result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
#endif
  }
  else
  {
#ifdef HAVE_FLINT
    nmod_poly_t FLINTF, FLINTG;
    convertFacCF2nmod_poly_t (FLINTF, F);
    convertFacCF2nmod_poly_t (FLINTG, G);
    nmod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
    result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
    nmod_poly_clear (FLINTF);
    nmod_poly_clear (FLINTG);
#else
    zz_pX NTLF= convertFacCF2NTLzzpX (F);
    zz_pX NTLG= convertFacCF2NTLzzpX (G);
    rem (NTLF, NTLF, NTLG);
    result= convertNTLzzpX2CF(NTLF, F.mvar());
#endif
  }
  return result;
}

mulMod()

CanonicalForm mulMod	(	const CanonicalForm &	A,
		const CanonicalForm &	B,
		const CFList &	MOD
	)

Karatsuba style modular multiplication for multivariate polynomials.

Returns

mulMod2 returns A * B mod MOD.

Parameters

[in]	A	multivariate, compressed polynomial
[in]	B	multivariate, compressed polynomial
[in]	MOD	only contains powers of Variables of level higher than 1

Definition at line 3080 of file facMul.cc.

{
  if (A.isZero() || B.isZero())
    return 0;
 
  if (MOD.length() == 1)
    return mulMod2 (A, B, MOD.getLast());
 
  CanonicalForm M= MOD.getLast();
  CanonicalForm F= mod (A, M);
  CanonicalForm G= mod (B, M);
  if (F.inCoeffDomain())
    return G*F;
  if (G.inCoeffDomain())
    return F*G;
 
  int sizeF= size (F);
  int sizeG= size (G);
 
  if (sizeF / MOD.length() < 100 || sizeG / MOD.length() < 100)
  {
    if (sizeF < sizeG)
      return mod (G*F, MOD);
    else
      return mod (F*G, MOD);
  }
 
  Variable y= M.mvar();
  int degF= degree (F, y);
  int degG= degree (G, y);
 
  if ((degF <= 1 && F.level() <= M.level()) &&
      (degG <= 1 && G.level() <= M.level()))
  {
    CFList buf= MOD;
    buf.removeLast();
    if (degF == 1 && degG == 1)
    {
      CanonicalForm F0= mod (F, y);
      CanonicalForm F1= div (F, y);
      CanonicalForm G0= mod (G, y);
      CanonicalForm G1= div (G, y);
      if (degree (M) > 2)
      {
        CanonicalForm H00= mulMod (F0, G0, buf);
        CanonicalForm H11= mulMod (F1, G1, buf);
        CanonicalForm H01= mulMod (F0 + F1, G0 + G1, buf);
        return H11*y*y + (H01 - H00 - H11)*y + H00;
      }
      else //here degree (M) == 2
      {
        buf.append (y);
        CanonicalForm F0G1= mulMod (F0, G1, buf);
        CanonicalForm F1G0= mulMod (F1, G0, buf);
        CanonicalForm F0G0= mulMod (F0, G0, MOD);
        CanonicalForm result= F0G0 + y*(F0G1 + F1G0);
        return result;
      }
    }
    else if (degF == 1 && degG == 0)
      return mulMod (div (F, y), G, buf)*y + mulMod (mod (F, y), G, buf);
    else if (degF == 0 && degG == 1)
      return mulMod (div (G, y), F, buf)*y + mulMod (mod (G, y), F, buf);
    else
      return mulMod (F, G, buf);
  }
  int m= (int) ceil (degree (M)/2.0);
  if (degF >= m || degG >= m)
  {
    CanonicalForm MLo= power (y, m);
    CanonicalForm MHi= power (y, degree (M) - m);
    CanonicalForm F0= mod (F, MLo);
    CanonicalForm F1= div (F, MLo);
    CanonicalForm G0= mod (G, MLo);
    CanonicalForm G1= div (G, MLo);
    CFList buf= MOD;
    buf.removeLast();
    buf.append (MHi);
    CanonicalForm F0G1= mulMod (F0, G1, buf);
    CanonicalForm F1G0= mulMod (F1, G0, buf);
    CanonicalForm F0G0= mulMod (F0, G0, MOD);
    return F0G0 + MLo*(F0G1 + F1G0);
  }
  else
  {
    m= (tmax(degF, degG)+1)/2;
    CanonicalForm yToM= power (y, m);
    CanonicalForm F0= mod (F, yToM);
    CanonicalForm F1= div (F, yToM);
    CanonicalForm G0= mod (G, yToM);
    CanonicalForm G1= div (G, yToM);
    CanonicalForm H00= mulMod (F0, G0, MOD);
    CanonicalForm H11= mulMod (F1, G1, MOD);
    CanonicalForm H01= mulMod (F0 + F1, G0 + G1, MOD);
    return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
  }
  DEBOUTLN (cerr, "fatal end in mulMod");
}

mulMod2()

CanonicalForm mulMod2	(	const CanonicalForm &	A,
		const CanonicalForm &	B,
		const CanonicalForm &	M
	)

Karatsuba style modular multiplication for bivariate polynomials.

Returns

mulMod2 returns A * B mod M.

Parameters

[in]	A	bivariate, compressed polynomial
[in]	B	bivariate, compressed polynomial
[in]	M	power of Variable (2)

Definition at line 2986 of file facMul.cc.

{
  if (A.isZero() || B.isZero())
    return 0;
 
  ASSERT (M.isUnivariate(), "M must be univariate");
 
  CanonicalForm F= mod (A, M);
  CanonicalForm G= mod (B, M);
  if (F.inCoeffDomain())
    return G*F;
  if (G.inCoeffDomain())
    return F*G;
 
  Variable y= M.mvar();
  int degF= degree (F, y);
  int degG= degree (G, y);
 
  if ((degF < 1 && degG < 1) && (F.isUnivariate() && G.isUnivariate()) &&
      (F.level() == G.level()))
  {
    CanonicalForm result= mulNTL (F, G);
    return mod (result, M);
  }
  else if (degF <= 1 && degG <= 1)
  {
    CanonicalForm result= F*G;
    return mod (result, M);
  }
 
  int sizeF= size (F);
  int sizeG= size (G);
 
  int fallBackToNaive= 50;
  if (sizeF < fallBackToNaive || sizeG < fallBackToNaive)
  {
    if (sizeF < sizeG)
      return mod (G*F, M);
    else
      return mod (F*G, M);
  }
 
#ifdef HAVE_FLINT
  if (getCharacteristic() == 0)
    return mulMod2FLINTQa (F, G, M);
#endif
 
  if (getCharacteristic() > 0 && CFFactory::gettype() != GaloisFieldDomain &&
      (((degF-degG) < 50 && degF > degG) || ((degG-degF) < 50 && degF <= degG)))
    return mulMod2NTLFq (F, G, M);
 
  int m= (int) ceil (degree (M)/2.0);
  if (degF >= m || degG >= m)
  {
    CanonicalForm MLo= power (y, m);
    CanonicalForm MHi= power (y, degree (M) - m);
    CanonicalForm F0= mod (F, MLo);
    CanonicalForm F1= div (F, MLo);
    CanonicalForm G0= mod (G, MLo);
    CanonicalForm G1= div (G, MLo);
    CanonicalForm F0G1= mulMod2 (F0, G1, MHi);
    CanonicalForm F1G0= mulMod2 (F1, G0, MHi);
    CanonicalForm F0G0= mulMod2 (F0, G0, M);
    return F0G0 + MLo*(F0G1 + F1G0);
  }
  else
  {
    m= (int) ceil (tmax (degF, degG)/2.0);
    CanonicalForm yToM= power (y, m);
    CanonicalForm F0= mod (F, yToM);
    CanonicalForm F1= div (F, yToM);
    CanonicalForm G0= mod (G, yToM);
    CanonicalForm G1= div (G, yToM);
    CanonicalForm H00= mulMod2 (F0, G0, M);
    CanonicalForm H11= mulMod2 (F1, G1, M);
    CanonicalForm H01= mulMod2 (F0 + F1, G0 + G1, M);
    return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
  }
  DEBOUTLN (cerr, "fatal end in mulMod2");
}

mulNTL()

CanonicalForm mulNTL	(	const CanonicalForm &	F,
		const CanonicalForm &	G,
		const modpk &	b = modpk()
	)

multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f).

Returns

mulNTL returns F*G

Parameters

[in]	F	a univariate poly
[in]	G	a univariate poly
[in]	b	coeff bound

Definition at line 411 of file facMul.cc.

{
  if (CFFactory::gettype() == GaloisFieldDomain)
    return F*G;
  if (getCharacteristic() == 0)
  {
    Variable alpha;
    if ((!F.inCoeffDomain() && !G.inCoeffDomain()) &&
        (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha)))
    {
      if (b.getp() != 0)
      {
        CanonicalForm mipo= getMipo (alpha);
        bool is_rat= isOn (SW_RATIONAL);
        if (!is_rat)
          On (SW_RATIONAL);
        mipo *=bCommonDen (mipo);
        if (!is_rat)
          Off (SW_RATIONAL);
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
        fmpz_t FLINTp;
        fmpz_mod_poly_t FLINTmipo;
        fq_ctx_t fq_con;
        fq_poly_t FLINTF, FLINTG;
 
        fmpz_init (FLINTp);
 
        convertCF2initFmpz (FLINTp, b.getpk());
 
        convertFacCF2Fmpz_mod_poly_t (FLINTmipo, mipo, FLINTp);
 
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_ctx_t fmpz_ctx;
        fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
        fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
        #else
        fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
        #endif
 
        convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
        convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
 
        fq_poly_mul (FLINTF, FLINTF, FLINTG, fq_con);
 
        CanonicalForm result= convertFq_poly_t2FacCF (FLINTF, F.mvar(),
                                                      alpha, fq_con);
 
        fmpz_clear (FLINTp);
        fq_poly_clear (FLINTF, fq_con);
        fq_poly_clear (FLINTG, fq_con);
        fq_ctx_clear (fq_con);
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_poly_clear (FLINTmipo,fmpz_ctx);
        fmpz_mod_ctx_clear(fmpz_ctx);
        #else
        fmpz_mod_poly_clear(FLINTmipo);
        #endif
        return b (result);
#endif
#ifdef HAVE_NTL
        ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
        ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (mipo));
        ZZ_pE::init (NTLmipo);
        ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
        ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
        mul (NTLf, NTLf, NTLg);
 
        return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
#endif
      }
#ifdef HAVE_FLINT
      CanonicalForm result= mulFLINTQa (F, G, alpha);
      return result;
#else
      return F*G;
#endif
    }
    else if (!F.inCoeffDomain() && !G.inCoeffDomain())
    {
#ifdef HAVE_FLINT
      if (b.getp() != 0)
      {
        fmpz_t FLINTpk;
        fmpz_init (FLINTpk);
        convertCF2initFmpz (FLINTpk, b.getpk());
        fmpz_mod_poly_t FLINTF, FLINTG;
        convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
        convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_ctx_t fmpz_ctx;
        fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
        fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG, fmpz_ctx);
        #else
        fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG);
        #endif
        CanonicalForm result= convertFmpz_mod_poly_t2FacCF (FLINTF, F.mvar(),b);
        #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        fmpz_mod_poly_clear (FLINTG,fmpz_ctx);
        fmpz_mod_poly_clear (FLINTF,fmpz_ctx);
        fmpz_mod_ctx_clear(fmpz_ctx);
        #else
        fmpz_mod_poly_clear (FLINTG);
        fmpz_mod_poly_clear (FLINTF);
        #endif
        fmpz_clear (FLINTpk);
        return result;
      }
      return mulFLINTQ (F, G);
#endif
#ifdef HAVE_NTL
      if (b.getp() != 0)
      {
        ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
        ZZX ZZf= convertFacCF2NTLZZX (F);
        ZZX ZZg= convertFacCF2NTLZZX (G);
        ZZ_pX NTLf= to_ZZ_pX (ZZf);
        ZZ_pX NTLg= to_ZZ_pX (ZZg);
        mul (NTLf, NTLf, NTLg);
        return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
      }
      return F*G;
#endif
    }
    if (b.getp() != 0)
    {
      if (!F.inBaseDomain() && !G.inBaseDomain())
      {
        if (hasFirstAlgVar (G, alpha) || hasFirstAlgVar (F, alpha))
        {
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
          fmpz_t FLINTp;
          fmpz_mod_poly_t FLINTmipo;
          fq_ctx_t fq_con;
 
          fmpz_init (FLINTp);
          convertCF2initFmpz (FLINTp, b.getpk());
 
          CanonicalForm mipo=getMipo (alpha);
          bool rat=isOn(SW_RATIONAL);
          On(SW_RATIONAL);
          CanonicalForm cd = bCommonDen(mipo);
          mipo *= cd;
          if (!rat) Off(SW_RATIONAL);
          convertFacCF2Fmpz_mod_poly_t (FLINTmipo, mipo, FLINTp);
 
          #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
          fmpz_mod_ctx_t fmpz_ctx;
          fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
          fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
          #else
          fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
          #endif
 
          CanonicalForm result;
 
          if (F.inCoeffDomain() && !G.inCoeffDomain())
          {
            fq_poly_t FLINTG;
            fmpz_poly_t FLINTF;
            convertFacCF2Fmpz_poly_t (FLINTF, F);
            convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
 
            fq_poly_scalar_mul_fq (FLINTG, FLINTG, FLINTF, fq_con);
 
            result= convertFq_poly_t2FacCF (FLINTG, G.mvar(), alpha, fq_con);
            fmpz_poly_clear (FLINTF);
            fq_poly_clear (FLINTG, fq_con);
          }
          else if (!F.inCoeffDomain() && G.inCoeffDomain())
          {
            fq_poly_t FLINTF;
            fmpz_poly_t FLINTG;
 
            convertFacCF2Fmpz_poly_t (FLINTG, G);
            convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
 
            fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
 
            result= convertFq_poly_t2FacCF (FLINTF, F.mvar(), alpha, fq_con);
            fmpz_poly_clear (FLINTG);
            fq_poly_clear (FLINTF, fq_con);
          }
          else
          {
            fq_t FLINTF, FLINTG;
 
            convertFacCF2Fq_t (FLINTF, F, fq_con);
            convertFacCF2Fq_t (FLINTG, G, fq_con);
 
            fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
 
            result= convertFq_t2FacCF (FLINTF, alpha);
            fq_clear (FLINTF, fq_con);
            fq_clear (FLINTG, fq_con);
          }
 
          fmpz_clear (FLINTp);
          #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
          fmpz_mod_poly_clear (FLINTmipo,fmpz_ctx);
          fmpz_mod_ctx_clear(fmpz_ctx);
          #else
          fmpz_mod_poly_clear (FLINTmipo);
          #endif
          fq_ctx_clear (fq_con);
 
          return b (result);
#endif
#ifdef HAVE_NTL
          ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
          ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
          ZZ_pE::init (NTLmipo);
 
          if (F.inCoeffDomain() && !G.inCoeffDomain())
          {
            ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
            ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
            mul (NTLg, to_ZZ_pE (NTLf), NTLg);
            return b (convertNTLZZ_pEX2CF (NTLg, G.mvar(), alpha));
          }
          else if (!F.inCoeffDomain() && G.inCoeffDomain())
          {
            ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
            ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
            mul (NTLf, NTLf, to_ZZ_pE (NTLg));
            return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
          }
          else
          {
            ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
            ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
            ZZ_pE result;
            mul (result, to_ZZ_pE (NTLg), to_ZZ_pE (NTLf));
            return b (convertNTLZZpX2CF (rep (result), alpha));
          }
#endif
        }
      }
      return b (F*G);
    }
    return F*G;
  }
  else if (F.inCoeffDomain() || G.inCoeffDomain())
    return F*G;
  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
  ASSERT (F.level() == G.level(), "expected polys of same level");
#ifdef HAVE_NTL
#if (!defined(HAVE_FLINT) ||  __FLINT_RELEASE < 20400)
  if (fac_NTL_char != getCharacteristic())
  {
    fac_NTL_char= getCharacteristic();
    zz_p::init (getCharacteristic());
  }
#endif
#endif
  Variable alpha;
  CanonicalForm result;
  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
  {
    if (!getReduce (alpha))
    {
      result= 0;
      for (CFIterator i= F; i.hasTerms(); i++)
        result += i.coeff()*G*power (F.mvar(),i.exp());
      return result;
    }
#if (HAVE_FLINT &&  __FLINT_RELEASE >= 20400)
    nmod_poly_t FLINTmipo;
    fq_nmod_ctx_t fq_con;
 
    nmod_poly_init (FLINTmipo, getCharacteristic());
    convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
 
    fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
 
    fq_nmod_poly_t FLINTF, FLINTG;
    convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
    convertFacCF2Fq_nmod_poly_t (FLINTG, G, fq_con);
 
    fq_nmod_poly_mul (FLINTF, FLINTF, FLINTG, fq_con);
 
    result= convertFq_nmod_poly_t2FacCF (FLINTF, F.mvar(), alpha, fq_con);
 
    fq_nmod_poly_clear (FLINTF, fq_con);
    fq_nmod_poly_clear (FLINTG, fq_con);
    nmod_poly_clear (FLINTmipo);
    fq_nmod_ctx_clear (fq_con);
    return result;
#elif defined(AHVE_NTL)
    zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
    zz_pE::init (NTLMipo);
    zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
    zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
    mul (NTLF, NTLF, NTLG);
    result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
    return result;
#endif
  }
  else
  {
#ifdef HAVE_FLINT
    nmod_poly_t FLINTF, FLINTG;
    convertFacCF2nmod_poly_t (FLINTF, F);
    convertFacCF2nmod_poly_t (FLINTG, G);
    nmod_poly_mul (FLINTF, FLINTF, FLINTG);
    result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
    nmod_poly_clear (FLINTF);
    nmod_poly_clear (FLINTG);
    return result;
#endif
#ifdef HAVE_NTL
    zz_pX NTLF= convertFacCF2NTLzzpX (F);
    zz_pX NTLG= convertFacCF2NTLzzpX (G);
    mul (NTLF, NTLF, NTLG);
    return convertNTLzzpX2CF(NTLF, F.mvar());
#endif
  }
  return F*G;
}

newtonDiv()

CanonicalForm newtonDiv	(	const CanonicalForm &	F,
		const CanonicalForm &	G,
		const CanonicalForm &	M
	)

division of F by G wrt Variable (1) modulo M using Newton inversion

Returns

newtonDiv returns the dividend

See also

divrem2(), newtonDivrem()

Parameters

[in]	F	bivariate, compressed polynomial
[in]	G	bivariate, compressed polynomial which is monic in Variable (1)
[in]	M	power of Variable (2)

Definition at line 3313 of file facMul.cc.

{
  ASSERT (getCharacteristic() > 0, "positive characteristic expected");
 
  CanonicalForm A= mod (F, M);
  CanonicalForm B= mod (G, M);
 
  Variable x= Variable (1);
  int degA= degree (A, x);
  int degB= degree (B, x);
  int m= degA - degB;
  if (m < 0)
    return 0;
 
  Variable v;
  CanonicalForm Q;
  if (degB < 1 || CFFactory::gettype() == GaloisFieldDomain)
  {
    CanonicalForm R;
    divrem2 (A, B, Q, R, M);
  }
  else
  {
    if (hasFirstAlgVar (A, v) || hasFirstAlgVar (B, v))
    {
      CanonicalForm R= reverse (A, degA);
      CanonicalForm revB= reverse (B, degB);
      revB= newtonInverse (revB, m + 1, M);
      Q= mulMod2 (R, revB, M);
      Q= mod (Q, power (x, m + 1));
      Q= reverse (Q, m);
    }
    else
    {
      Variable y= Variable (2);
#if (HAVE_FLINT &&  __FLINT_RELEASE >= 20400)
      nmod_poly_t FLINTmipo;
      fq_nmod_ctx_t fq_con;
 
      nmod_poly_init (FLINTmipo, getCharacteristic());
      convertFacCF2nmod_poly_t (FLINTmipo, M);
 
      fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
 
 
      fq_nmod_poly_t FLINTA, FLINTB;
      convertFacCF2Fq_nmod_poly_t (FLINTA, swapvar (A, x, y), fq_con);
      convertFacCF2Fq_nmod_poly_t (FLINTB, swapvar (B, x, y), fq_con);
 
      fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB, fq_con);
 
      Q= convertFq_nmod_poly_t2FacCF (FLINTA, x, y, fq_con);
 
      fq_nmod_poly_clear (FLINTA, fq_con);
      fq_nmod_poly_clear (FLINTB, fq_con);
      nmod_poly_clear (FLINTmipo);
      fq_nmod_ctx_clear (fq_con);
#else
      bool zz_pEbak= zz_pE::initialized();
      zz_pEBak bak;
      if (zz_pEbak)
        bak.save();
      zz_pX mipo= convertFacCF2NTLzzpX (M);
      zz_pEX NTLA, NTLB;
      NTLA= convertFacCF2NTLzz_pEX (swapvar (A, x, y), mipo);
      NTLB= convertFacCF2NTLzz_pEX (swapvar (B, x, y), mipo);
      div (NTLA, NTLA, NTLB);
      Q= convertNTLzz_pEX2CF (NTLA, x, y);
      if (zz_pEbak)
        bak.restore();
#endif
    }
  }
 
  return Q;
}

newtonDivrem() [1/2]

void newtonDivrem	(	const CanonicalForm &	F,
		const CanonicalForm &	G,
		CanonicalForm &	Q,
		CanonicalForm &	R
	)

division with remainder of univariate polynomials over Q and Q(a) using Newton inversion, satisfying F=G*Q+R, deg(R) < deg(G)

Parameters

[in]	F	univariate poly
[in]	G	univariate poly
[in,out]	Q	quotient
[in,out]	R	remainder

Definition at line 346 of file facMul.cc.

{
  ASSERT (F.level() == G.level(), "F and G have different level");
  CanonicalForm A= F;
  CanonicalForm B= G;
  Variable x= A.mvar();
  int degA= degree (A);
  int degB= degree (B);
  int m= degA - degB;
 
  if (m < 0)
  {
    R= A;
    Q= 0;
    return;
  }
 
  if (degB <= 1)
    divrem (A, B, Q, R);
  else
  {
    R= uniReverse (A, degA, x);
 
    CanonicalForm revB= uniReverse (B, degB, x);
    revB= newtonInverse (revB, m + 1, x);
    Q= mulFLINTQTrunc (R, revB, m + 1);
    Q= uniReverse (Q, m, x);
 
    R= A - mulNTL (Q, B);
  }
}

newtonDivrem() [2/2]

void newtonDivrem	(	const CanonicalForm &	F,
		const CanonicalForm &	G,
		CanonicalForm &	Q,
		CanonicalForm &	R,
		const CanonicalForm &	M
	)

division with remainder of F by G wrt Variable (1) modulo M using Newton inversion

Returns

Q returns the dividend, R returns the remainder.

See also

divrem2(), newtonDiv()

Parameters

[in]	F	bivariate, compressed polynomial
[in]	G	bivariate, compressed polynomial which is monic in Variable (1)
[in,out]	Q	dividend
[in,out]	R	remainder, degree (R, 1) < degree (G, 1)
[in]	M	power of Variable (2)

Definition at line 3392 of file facMul.cc.

{
  CanonicalForm A= mod (F, M);
  CanonicalForm B= mod (G, M);
  Variable x= Variable (1);
  int degA= degree (A, x);
  int degB= degree (B, x);
  int m= degA - degB;
 
  if (m < 0)
  {
    R= A;
    Q= 0;
    return;
  }
 
  Variable v;
  if (degB <= 1 || CFFactory::gettype() == GaloisFieldDomain)
  {
     divrem2 (A, B, Q, R, M);
  }
  else
  {
    if (hasFirstAlgVar (A, v) || hasFirstAlgVar (B, v))
    {
      R= reverse (A, degA);
 
      CanonicalForm revB= reverse (B, degB);
      revB= newtonInverse (revB, m + 1, M);
      Q= mulMod2 (R, revB, M);
 
      Q= mod (Q, power (x, m + 1));
      Q= reverse (Q, m);
 
      R= A - mulMod2 (Q, B, M);
    }
    else
    {
      Variable y= Variable (2);
#if (HAVE_FLINT &&  __FLINT_RELEASE >= 20400)
      nmod_poly_t FLINTmipo;
      fq_nmod_ctx_t fq_con;
 
      nmod_poly_init (FLINTmipo, getCharacteristic());
      convertFacCF2nmod_poly_t (FLINTmipo, M);
 
      fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
 
      fq_nmod_poly_t FLINTA, FLINTB;
      convertFacCF2Fq_nmod_poly_t (FLINTA, swapvar (A, x, y), fq_con);
      convertFacCF2Fq_nmod_poly_t (FLINTB, swapvar (B, x, y), fq_con);
 
      fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB, fq_con);
 
      Q= convertFq_nmod_poly_t2FacCF (FLINTA, x, y, fq_con);
      R= convertFq_nmod_poly_t2FacCF (FLINTB, x, y, fq_con);
 
      fq_nmod_poly_clear (FLINTA, fq_con);
      fq_nmod_poly_clear (FLINTB, fq_con);
      nmod_poly_clear (FLINTmipo);
      fq_nmod_ctx_clear (fq_con);
#else
      zz_pX mipo= convertFacCF2NTLzzpX (M);
      zz_pEX NTLA, NTLB;
      NTLA= convertFacCF2NTLzz_pEX (swapvar (A, x, y), mipo);
      NTLB= convertFacCF2NTLzz_pEX (swapvar (B, x, y), mipo);
      zz_pEX NTLQ, NTLR;
      DivRem (NTLQ, NTLR, NTLA, NTLB);
      Q= convertNTLzz_pEX2CF (NTLQ, x, y);
      R= convertNTLzz_pEX2CF (NTLR, x, y);
#endif
    }
  }
}

prodMod() [1/2]

CanonicalForm prodMod	(	const CFList &	L,
		const CanonicalForm &	M
	)

product of all elements in L modulo M via divide-and-conquer.

Returns

prodMod returns product of all elements in L modulo M.

Parameters

[in]	L	contains only bivariate, compressed polynomials
[in]	M	power of Variable (2)

Definition at line 3180 of file facMul.cc.

{
  if (L.isEmpty())
    return 1;
  int l= L.length();
  if (l == 1)
    return mod (L.getFirst(), M);
  else if (l == 2) {
    CanonicalForm result= mulMod2 (L.getFirst(), L.getLast(), M);
    return result;
  }
  else
  {
    l /= 2;
    CFList tmp1, tmp2;
    CFListIterator i= L;
    CanonicalForm buf1, buf2;
    for (int j= 1; j <= l; j++, i++)
      tmp1.append (i.getItem());
    tmp2= Difference (L, tmp1);
    buf1= prodMod (tmp1, M);
    buf2= prodMod (tmp2, M);
    CanonicalForm result= mulMod2 (buf1, buf2, M);
    return result;
  }
}

prodMod() [2/2]

CanonicalForm prodMod	(	const CFList &	L,
		const CFList &	M
	)

product of all elements in L modulo M via divide-and-conquer.

Returns

prodMod returns product of all elements in L modulo M.

Parameters

[in]	L	contains multivariate, compressed polynomials
[in]	M	contains only powers of Variables

Definition at line 3207 of file facMul.cc.

{
  if (L.isEmpty())
    return 1;
  else if (L.length() == 1)
    return L.getFirst();
  else if (L.length() == 2)
    return mulMod (L.getFirst(), L.getLast(), M);
  else
  {
    int l= L.length()/2;
    CFListIterator i= L;
    CFList tmp1, tmp2;
    CanonicalForm buf1, buf2;
    for (int j= 1; j <= l; j++, i++)
      tmp1.append (i.getItem());
    tmp2= Difference (L, tmp1);
    buf1= prodMod (tmp1, M);
    buf2= prodMod (tmp2, M);
    return mulMod (buf1, buf2, M);
  }
}

uniFdivides()

bool uniFdivides	(	const CanonicalForm &	A,
		const CanonicalForm &	B
	)

divisibility test for univariate polys

Returns

uniFdivides returns true if A divides B

Parameters

[in]	A	univariate poly
[in]	B	univariate poly

Definition at line 3759 of file facMul.cc.

{
  if (B.isZero())
    return true;
  if (A.isZero())
    return false;
  if (CFFactory::gettype() == GaloisFieldDomain)
    return fdivides (A, B);
  int p= getCharacteristic();
  if (A.inCoeffDomain() || B.inCoeffDomain())
  {
    if (A.inCoeffDomain())
      return true;
    else
      return false;
  }
  if (p > 0)
  {
#if (!defined(HAVE_FLINT) ||  __FLINT_RELEASE < 20400)
    if (fac_NTL_char != p)
    {
      fac_NTL_char= p;
      zz_p::init (p);
    }
#endif
    Variable alpha;
    if (hasFirstAlgVar (A, alpha) || hasFirstAlgVar (B, alpha))
    {
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
      nmod_poly_t FLINTmipo;
      fq_nmod_ctx_t fq_con;
 
      nmod_poly_init (FLINTmipo, getCharacteristic());
      convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
 
      fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
 
      fq_nmod_poly_t FLINTA, FLINTB;
      convertFacCF2Fq_nmod_poly_t (FLINTA, A, fq_con);
      convertFacCF2Fq_nmod_poly_t (FLINTB, B, fq_con);
      int result= fq_nmod_poly_divides (FLINTA, FLINTB, FLINTA, fq_con);
      fq_nmod_poly_clear (FLINTA, fq_con);
      fq_nmod_poly_clear (FLINTB, fq_con);
      nmod_poly_clear (FLINTmipo);
      fq_nmod_ctx_clear (fq_con);
      return result;
#else
      zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
      zz_pE::init (NTLMipo);
      zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
      zz_pEX NTLB= convertFacCF2NTLzz_pEX (B, NTLMipo);
      return divide (NTLB, NTLA);
#endif
    }
#ifdef HAVE_FLINT
    nmod_poly_t FLINTA, FLINTB;
    convertFacCF2nmod_poly_t (FLINTA, A);
    convertFacCF2nmod_poly_t (FLINTB, B);
    nmod_poly_divrem (FLINTB, FLINTA, FLINTB, FLINTA);
    bool result= nmod_poly_is_zero (FLINTA);
    nmod_poly_clear (FLINTA);
    nmod_poly_clear (FLINTB);
    return result;
#else
    zz_pX NTLA= convertFacCF2NTLzzpX (A);
    zz_pX NTLB= convertFacCF2NTLzzpX (B);
    return divide (NTLB, NTLA);
#endif
  }
#ifdef HAVE_FLINT
  Variable alpha;
  bool isRat= isOn (SW_RATIONAL);
  if (!isRat)
    On (SW_RATIONAL);
  if (!hasFirstAlgVar (A, alpha) && !hasFirstAlgVar (B, alpha))
  {
    fmpq_poly_t FLINTA,FLINTB;
    convertFacCF2Fmpq_poly_t (FLINTA, A);
    convertFacCF2Fmpq_poly_t (FLINTB, B);
    fmpq_poly_rem (FLINTA, FLINTB, FLINTA);
    bool result= fmpq_poly_is_zero (FLINTA);
    fmpq_poly_clear (FLINTA);
    fmpq_poly_clear (FLINTB);
    if (!isRat)
      Off (SW_RATIONAL);
    return result;
  }
  CanonicalForm Q, R;
  newtonDivrem (B, A, Q, R);
  if (!isRat)
    Off (SW_RATIONAL);
  return R.isZero();
#else
  bool isRat= isOn (SW_RATIONAL);
  if (!isRat)
    On (SW_RATIONAL);
  bool result= fdivides (A, B);
  if (!isRat)
    Off (SW_RATIONAL);
  return result; //maybe NTL?
#endif
}