Loading...
Searching...
No Matches
cfModGcd.h File Reference

modular and sparse modular GCD algorithms over finite fields and Z. More...

`#include "cf_assert.h"`
`#include "cf_factory.h"`

Go to the source code of this file.

## Functions

CanonicalForm | modGCDFq (const CanonicalForm &F, const CanonicalForm &G, Variable &alpha, CFList &l, bool &top_level)
static CanonicalForm | modGCDFq (const CanonicalForm &A, const CanonicalForm &B, Variable &alpha)
| GCD of A and B over .
CanonicalForm | modGCDFp (const CanonicalForm &F, const CanonicalForm &G, bool &top_level, CFList &l)
CanonicalForm | modGCDFp (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
static CanonicalForm | modGCDFp (const CanonicalForm &A, const CanonicalForm &B)
| GCD of A and B over .
static CanonicalForm | modGCDFp (const CanonicalForm &A, const CanonicalForm &B, CanonicalForm &coA, CanonicalForm &coB)
CanonicalForm | modGCDGF (const CanonicalForm &F, const CanonicalForm &G, CFList &l, bool &top_level)
static CanonicalForm | modGCDGF (const CanonicalForm &A, const CanonicalForm &B)
| GCD of A and B over GF.
CanonicalForm | sparseGCDFp (const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
static CanonicalForm | sparseGCDFp (const CanonicalForm &A, const CanonicalForm &B)
| Zippel's sparse GCD over Fp.
CanonicalForm | sparseGCDFq (const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, CFList &l, bool &topLevel)
static CanonicalForm | sparseGCDFq (const CanonicalForm &A, const CanonicalForm &B, const Variable &alpha)
| Zippel's sparse GCD over Fq.
CFArray | getMonoms (const CanonicalForm &F)
| extract monomials of F, parts in algebraic variable are considered coefficients
bool | terminationTest (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &coF, const CanonicalForm &coG, const CanonicalForm &cand)
CanonicalForm | modGCDZ (const CanonicalForm &FF, const CanonicalForm &GG)
| modular GCD over Z

## Detailed Description

modular and sparse modular GCD algorithms over finite fields and Z.

Author
  Martin Lee

Date
  22.10.2009

Copyright:
  (c) by The SINGULAR Team, see LICENSE file

Definition in file cfModGcd.h.

## Function Documentation

## getMonoms()

CFArray getMonoms | ( | const CanonicalForm & | F | ) |

extract monomials of F, parts in algebraic variable are considered coefficients

Parameters

  [in] | F | some poly

Definition at line 1965 of file cfModGcd.cc.

{
if (F.inCoeffDomain())
{
CFArray result= CFArray (1);
result [0]= 1;
return result;
}
if (F.isUnivariate())
{
CFArray result= CFArray (size(F));
int j= 0;
for (CFIterator i= F; i.hasTerms(); i++, j++)
result[j]= power (F.mvar(), i.exp());
return result;
}
int numMon= size (F);
CFArray result= CFArray (numMon);
int j= 0;
CFArray recResult;
Variable x= F.mvar();
CanonicalForm powX;
for (CFIterator i= F; i.hasTerms(); i++)
{
powX= power (x, i.exp());
recResult= getMonoms (i.coeff());
for (int k= 0; k < recResult.size(); k++)
result[j+k]= powX*recResult[k];
j += recResult.size();
}
return result;
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
getMonoms
CFArray getMonoms(const CanonicalForm &F)
extract monomials of F, parts in algebraic variable are considered coefficients
Definition cfModGcd.cc:1965
x
Variable x
Definition cfModGcd.cc:4090
Array::size
int size() const
Definition ftmpl_array.cc:92
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition canonicalform.cc:593
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition canonicalform.cc:155
Variable
factory's class for variables
Definition factory.h:127
result
return result
Definition facAbsBiFact.cc:76
j
int j
Definition facHensel.cc:110

## modGCDFp() [1/4]

CanonicalForm modGCDFp | ( | const CanonicalForm & | A,
|  | const CanonicalForm & | B )

inline static

GCD of A and B over .

Parameters

  [in] | A | poly over F_p
  [in] | B | poly over F_p

Definition at line 50 of file cfModGcd.h.

{
CFList list;
bool top_level= true;
return modGCDFp (A, B, top_level, list);
}
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
modGCDFp
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &top_level, CFList &l)
Definition cfModGcd.cc:1213
B
b *CanonicalForm B
Definition facBivar.cc:52
A
#define A
Definition sirandom.c:24

## modGCDFp() [2/4]

CanonicalForm modGCDFp | ( | const CanonicalForm & | A,
|  | const CanonicalForm & | B,
|  | CanonicalForm & | coA,
|  | CanonicalForm & | coB )

inline static

Definition at line 60 of file cfModGcd.h.

{
CFList list;
bool top_level= true;
return modGCDFp (A, B, coA, coB, top_level, list);
}

## modGCDFp() [3/4]

CanonicalForm modGCDFp | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | G,
|  | bool & | top_level,
|  | CFList & | l )

Definition at line 1213 of file cfModGcd.cc.

{
CanonicalForm dummy1, dummy2;
CanonicalForm result= modGCDFp (F, G, dummy1, dummy2, topLevel, l);
return result;
}
l
int l
Definition cfEzgcd.cc:100
topLevel
const CanonicalForm CFMap CFMap bool topLevel
Definition cfGcdAlgExt.cc:58
modGCDFp
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition cfModGcd.cc:1224
G
STATIC_VAR TreeM * G
Definition janet.cc:31

## modGCDFp() [4/4]

CanonicalForm modGCDFp | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | G,
|  | CanonicalForm & | coF,
|  | CanonicalForm & | coG,
|  | bool & | topLevel,
|  | CFList & | l )

Definition at line 1224 of file cfModGcd.cc.

{
CanonicalForm A= F;
CanonicalForm B= G;
if (F.isZero() && degree(G) > 0)
{
coF= 0;
coG= Lc (G);
return G/Lc(G);
}
else if (G.isZero() && degree (F) > 0)
{
coF= Lc (F);
coG= 0;
return F/Lc(F);
}
else if (F.isZero() && G.isZero())
{
coF= coG= 0;
return F.genOne();
}
if (F.inBaseDomain() || G.inBaseDomain())
{
coF= F;
coG= G;
return F.genOne();
}
if (F.isUnivariate() && fdivides(F, G, coG))
{
coF= Lc (F);
return F/Lc(F);
}
if (G.isUnivariate() && fdivides(G, F, coF))
{
coG= Lc (G);
return G/Lc(G);
}
if (F == G)
{
coF= coG= Lc (F);
return F/Lc(F);
}
CFMap M,N;
int best_level= myCompress (A, B, M, N, topLevel);
if (best_level == 0)
{
coF= F;
coG= G;
return B.genOne();
}
A= M(A);
B= M(B);
Variable x= Variable (1);
//univariate case
if (A.isUnivariate() && B.isUnivariate())
{
CanonicalForm result= gcd (A, B);
coF= N (A/result);
coG= N (B/result);
return N (result);
}
CanonicalForm cA, cB; // content of A and B
CanonicalForm ppA, ppB; // primitive part of A and B
CanonicalForm gcdcAcB;
cA = uni_content (A);
cB = uni_content (B);
gcdcAcB= gcd (cA, cB);
ppA= A/cA;
ppB= B/cB;
CanonicalForm lcA, lcB; // leading coefficients of A and B
CanonicalForm gcdlcAlcB;
lcA= uni_lcoeff (ppA);
lcB= uni_lcoeff (ppB);
gcdlcAlcB= gcd (lcA, lcB);
int d= totaldegree (ppA, Variable (2), Variable (ppA.level()));
int d0;
if (d == 0)
{
coF= N (ppA*(cA/gcdcAcB));
coG= N (ppB*(cB/gcdcAcB));
return N(gcdcAcB);
}
d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
if (d0 < d)
d= d0;
if (d == 0)
{
coF= N (ppA*(cA/gcdcAcB));
coG= N (ppB*(cB/gcdcAcB));
return N(gcdcAcB);
}
CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH;
CanonicalForm newtonPoly, coF_random_element, coG_random_element,
coF_m, coG_m, ppCoF, ppCoG;
newtonPoly= 1;
m= gcdlcAlcB;
H= 0;
coF= 0;
coG= 0;
G_m= 0;
Variable alpha, V_buf, cleanUp;
bool fail= false;
bool inextension= false;
topLevel= false;
CFList source, dest;
int bound1= degree (ppA, 1);
int bound2= degree (ppB, 1);
do
{
if (inextension)
random_element= randomElement (m*lcA*lcB, V_buf, l, fail);
else
random_element= FpRandomElement (m*lcA*lcB, l, fail);
if (!fail && !inextension)
{
CFList list;
TIMING_START (gcd_recursion);
G_random_element=
modGCDFp (ppA (random_element,x), ppB (random_element,x),
coF_random_element, coG_random_element, topLevel,
list);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
}
else if (!fail && inextension)
{
CFList list;
TIMING_START (gcd_recursion);
G_random_element=
modGCDFq (ppA (random_element, x), ppB (random_element, x),
coF_random_element, coG_random_element, V_buf,
list, topLevel);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
}
else if (fail && !inextension)
{
source= CFList();
dest= CFList();
CFList list;
CanonicalForm mipo;
int deg= 2;
bool initialized= false;
do
{
mipo= randomIrredpoly (deg, x);
if (initialized)
setMipo (alpha, mipo);
else
alpha= rootOf (mipo);
inextension= true;
initialized= true;
fail= false;
random_element= randomElement (m*lcA*lcB, alpha, l, fail);
deg++;
} while (fail);
list= CFList();
V_buf= alpha;
cleanUp= alpha;
TIMING_START (gcd_recursion);
G_random_element=
modGCDFq (ppA (random_element, x), ppB (random_element, x),
coF_random_element, coG_random_element, alpha,
list, topLevel);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
}
else if (fail && inextension)
{
source= CFList();
dest= CFList();
Variable V_buf3= V_buf;
V_buf= chooseExtension (V_buf);
bool prim_fail= false;
Variable V_buf2;
CanonicalForm prim_elem, im_prim_elem;
prim_elem= primitiveElement (alpha, V_buf2, prim_fail);
if (V_buf3 != alpha)
{
m= mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
G_m= mapDown (G_m, prim_elem, im_prim_elem, alpha, source, dest);
coF_m= mapDown (coF_m, prim_elem, im_prim_elem, alpha, source, dest);
coG_m= mapDown (coG_m, prim_elem, im_prim_elem, alpha, source, dest);
newtonPoly= mapDown (newtonPoly, prim_elem, im_prim_elem, alpha,
source, dest);
ppA= mapDown (ppA, prim_elem, im_prim_elem, alpha, source, dest);
ppB= mapDown (ppB, prim_elem, im_prim_elem, alpha, source, dest);
gcdlcAlcB= mapDown (gcdlcAlcB, prim_elem, im_prim_elem, alpha, source,
dest);
lcA= mapDown (lcA, prim_elem, im_prim_elem, alpha, source, dest);
lcB= mapDown (lcB, prim_elem, im_prim_elem, alpha, source, dest);
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, alpha,
source, dest);
}
ASSERT (!prim_fail, "failure in integer factorizer");
if (prim_fail)
; //ERROR
else
im_prim_elem= mapPrimElem (prim_elem, alpha, V_buf);
DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (alpha));
DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (V_buf2));
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= mapUp (i.getItem(), alpha, V_buf, prim_elem,
im_prim_elem, source, dest);
m= mapUp (m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
G_m= mapUp (G_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
coF_m= mapUp (coF_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
coG_m= mapUp (coG_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
newtonPoly= mapUp (newtonPoly, alpha, V_buf, prim_elem, im_prim_elem,
source, dest);
ppA= mapUp (ppA, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
ppB= mapUp (ppB, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
gcdlcAlcB= mapUp (gcdlcAlcB, alpha, V_buf, prim_elem, im_prim_elem,
source, dest);
lcA= mapUp (lcA, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
lcB= mapUp (lcB, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
fail= false;
random_element= randomElement (m*lcA*lcB, V_buf, l, fail );
DEBOUTLN (cerr, "fail= " << fail);
CFList list;
TIMING_START (gcd_recursion);
G_random_element=
modGCDFq (ppA (random_element, x), ppB (random_element, x),
coF_random_element, coG_random_element, V_buf,
list, topLevel);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
alpha= V_buf;
}
if (!G_random_element.inCoeffDomain())
d0= totaldegree (G_random_element, Variable(2),
Variable (G_random_element.level()));
else
d0= 0;
if (d0 == 0)
{
if (inextension)
prune (cleanUp);
coF= N (ppA*(cA/gcdcAcB));
coG= N (ppB*(cB/gcdcAcB));
return N(gcdcAcB);
}
if (d0 > d)
{
if (!find (l, random_element))
l.append (random_element);
continue;
}
G_random_element= (gcdlcAlcB(random_element,x)/uni_lcoeff(G_random_element))
*G_random_element;
coF_random_element= (lcA(random_element,x)/uni_lcoeff(coF_random_element))
*coF_random_element;
coG_random_element= (lcB(random_element,x)/uni_lcoeff(coG_random_element))
*coG_random_element;
if (!G_random_element.inCoeffDomain())
d0= totaldegree (G_random_element, Variable(2),
Variable (G_random_element.level()));
else
d0= 0;
if (d0 < d)
{
m= gcdlcAlcB;
newtonPoly= 1;
G_m= 0;
d= d0;
coF_m= 0;
coG_m= 0;
}
TIMING_START (newton_interpolation);
H= newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
coF= newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,x);
coG= newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,x);
TIMING_END_AND_PRINT (newton_interpolation,
"time for newton_interpolation: ");
//termination test
if ((uni_lcoeff (H) == gcdlcAlcB) || (G_m == H))
{
TIMING_START (termination_test);
if (gcdlcAlcB.isOne())
cH= 1;
else
cH= uni_content (H);
ppH= H/cH;
ppH /= Lc (ppH);
CanonicalForm lcppH= gcdlcAlcB/cH;
CanonicalForm ccoF= lcppH/Lc (lcppH);
CanonicalForm ccoG= lcppH/Lc (lcppH);
ppCoF= coF/ccoF;
ppCoG= coG/ccoG;
DEBOUTLN (cerr, "ppH= " << ppH);
if (((degree (ppCoF,1)+degree (ppH,1) == bound1) &&
(degree (ppCoG,1)+degree (ppH,1) == bound2) &&
terminationTest (ppA, ppB, ppCoF, ppCoG, ppH)) ||
(fdivides (ppH, ppA, ppCoF) && fdivides (ppH, ppB, ppCoG)))
{
if (inextension)
prune (cleanUp);
coF= N ((cA/gcdcAcB)*ppCoF);
coG= N ((cB/gcdcAcB)*ppCoG);
TIMING_END_AND_PRINT (termination_test,
"time for successful termination Fp: ");
return N(gcdcAcB*ppH);
}
TIMING_END_AND_PRINT (termination_test,
"time for unsuccessful termination Fp: ");
}
G_m= H;
coF_m= coF;
coG_m= coG;
newtonPoly= newtonPoly*(x - random_element);
m= m*(x - random_element);
if (!find (l, random_element))
l.append (random_element);
} while (1);
}
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
m
int m
Definition cfEzgcd.cc:128
modGCDFq
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, Variable &alpha, CFList &l, bool &topLevel)
GCD of F and G over , l and topLevel are only used internally, output is monic based on Alg....
Definition cfModGcd.cc:479
coG
const CanonicalForm const CanonicalForm const CanonicalForm & coG
Definition cfModGcd.cc:68
myCompress
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
Definition cfModGcd.cc:92
chooseExtension
static Variable chooseExtension(const Variable &alpha)
Definition cfModGcd.cc:421
uni_content
static CanonicalForm uni_content(const CanonicalForm &F)
compute the content of F, where F is considered as an element of
Definition cfModGcd.cc:282
uni_lcoeff
static CanonicalForm uni_lcoeff(const CanonicalForm &F)
compute the leading coefficient of F, where F is considered as an element of , order on is dp.
Definition cfModGcd.cc:340
coF
const CanonicalForm const CanonicalForm & coF
Definition cfModGcd.cc:68
randomElement
static CanonicalForm randomElement(const CanonicalForm &F, const Variable &alpha, CFList &list, bool &fail)
compute a random element a of , s.t. F(a) , F is a univariate polynomial, returns fail if there are...
Definition cfModGcd.cc:380
FpRandomElement
static CanonicalForm FpRandomElement(const CanonicalForm &F, CFList &list, bool &fail)
Definition cfModGcd.cc:1172
newtonInterp
static CanonicalForm newtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x)
Newton interpolation - Incremental algorithm. Given a list of values alpha_i and a list of polynomial...
Definition cfModGcd.cc:365
terminationTest
bool terminationTest(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &coF, const CanonicalForm &coG, const CanonicalForm &cand)
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
randomIrredpoly
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition cf_irred.cc:26
mapPrimElem
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition cf_map_ext.cc:451
primitiveElement
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
Definition cf_map_ext.cc:343
mapDown
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
Definition cf_map_ext.cc:124
mapUp
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition cf_map_ext.cc:71
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm::genOne
CanonicalForm genOne() const
Definition canonicalform.cc:1881
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition canonicalform.cc:104
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition debug.h:49
alpha
Variable alpha
Definition facAbsBiFact.cc:52
H
CanonicalForm H
Definition facAbsFact.cc:60
mipo
CanonicalForm mipo
Definition facAlgExt.cc:57
rootOf
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition variable.cc:162
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
prune
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
setMipo
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition variable.cc:219
find
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
M
#define M
Definition sirandom.c:25
TIMING_START
#define TIMING_START(t)
Definition timing.h:92
TIMING_END_AND_PRINT
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836

## modGCDFq() [1/2]

CanonicalForm modGCDFq | ( | const CanonicalForm & | A,
|  | const CanonicalForm & | B,
|  | Variable & | alpha )

inline static

GCD of A and B over .

Parameters

  [in] | A | poly over F_q
  [in] | B | poly over F_q
  [in] | alpha | algebraic variable

Definition at line 28 of file cfModGcd.h.

{
CFList list;
bool top_level= true;
return modGCDFq (A, B, alpha, list, top_level);
}
modGCDFq
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, Variable &alpha, CFList &l, bool &top_level)
Definition cfModGcd.cc:463

## modGCDFq() [2/2]

CanonicalForm modGCDFq | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | G,
|  | Variable & | alpha,
|  | CFList & | l,
|  | bool & | top_level )

Definition at line 463 of file cfModGcd.cc.

{
CanonicalForm dummy1, dummy2;
CanonicalForm result= modGCDFq (F, G, dummy1, dummy2, alpha, l,
topLevel);
return result;
}

## modGCDGF() [1/2]

CanonicalForm modGCDGF | ( | const CanonicalForm & | A,
|  | const CanonicalForm & | B )

inline static

GCD of A and B over GF.

Parameters

  [in] | A | poly over GF
  [in] | B | poly over GF

Definition at line 74 of file cfModGcd.h.

{
ASSERT (CFFactory::gettype() == GaloisFieldDomain,
"GF as base field expected");
CFList list;
bool top_level= true;
return modGCDGF (A, B, list, top_level);
}
modGCDGF
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CFList &l, bool &top_level)
Definition cfModGcd.cc:859
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28

## modGCDGF() [2/2]

CanonicalForm modGCDGF | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | G,
|  | CFList & | l,
|  | bool & | top_level )

Definition at line 859 of file cfModGcd.cc.

{
CanonicalForm dummy1, dummy2;
CanonicalForm result= modGCDGF (F, G, dummy1, dummy2, l, topLevel);
return result;
}
modGCDGF
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, CFList &l, bool &topLevel)
GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms forComputer Algebra" by Geddes...
Definition cfModGcd.cc:873

## modGCDZ()

CanonicalForm modGCDZ | ( | const CanonicalForm & | FF,
|  | const CanonicalForm & | GG )

modular GCD over Z

Parameters

  [in] | FF | poly over Z
  [in] | GG | poly over Z

## sparseGCDFp() [1/2]

CanonicalForm sparseGCDFp | ( | const CanonicalForm & | A,
|  | const CanonicalForm & | B )

inline static

Zippel's sparse GCD over Fp.

Parameters

  [in] | A | poly over F_p
  [in] | B | poly over F_p

Definition at line 90 of file cfModGcd.h.

{
ASSERT (CFFactory::gettype() == FiniteFieldDomain,
"Fp as base field expected");
CFList list;
bool topLevel= true;
return sparseGCDFp (A, B, topLevel, list);
}
sparseGCDFp
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition cfModGcd.cc:3570
FiniteFieldDomain
#define FiniteFieldDomain
Definition cf_defs.h:19

## sparseGCDFp() [2/2]

CanonicalForm sparseGCDFp | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | G,
|  | bool & | topLevel,
|  | CFList & | l )

Definition at line 3570 of file cfModGcd.cc.

{
CanonicalForm A= F;
CanonicalForm B= G;
if (F.isZero() && degree(G) > 0) return G/Lc(G);
else if (G.isZero() && degree (F) > 0) return F/Lc(F);
else if (F.isZero() && G.isZero()) return F.genOne();
if (F.inBaseDomain() || G.inBaseDomain()) return F.genOne();
if (F.isUnivariate() && fdivides(F, G)) return F/Lc(F);
if (G.isUnivariate() && fdivides(G, F)) return G/Lc(G);
if (F == G) return F/Lc(F);
CFMap M,N;
int best_level= myCompress (A, B, M, N, topLevel);
if (best_level == 0) return B.genOne();
A= M(A);
B= M(B);
Variable x= Variable (1);
//univariate case
if (A.isUnivariate() && B.isUnivariate())
return N (gcd (A, B));
CanonicalForm cA, cB; // content of A and B
CanonicalForm ppA, ppB; // primitive part of A and B
CanonicalForm gcdcAcB;
cA = uni_content (A);
cB = uni_content (B);
gcdcAcB= gcd (cA, cB);
ppA= A/cA;
ppB= B/cB;
CanonicalForm lcA, lcB; // leading coefficients of A and B
CanonicalForm gcdlcAlcB;
lcA= uni_lcoeff (ppA);
lcB= uni_lcoeff (ppB);
if (fdivides (lcA, lcB))
{
if (fdivides (A, B))
return F/Lc(F);
}
if (fdivides (lcB, lcA))
{
if (fdivides (B, A))
return G/Lc(G);
}
gcdlcAlcB= gcd (lcA, lcB);
int d= totaldegree (ppA, Variable (2), Variable (ppA.level()));
int d0;
if (d == 0)
return N(gcdcAcB);
d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
if (d0 < d)
d= d0;
if (d == 0)
return N(gcdcAcB);
CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH, skeleton;
CanonicalForm newtonPoly= 1;
m= gcdlcAlcB;
G_m= 0;
H= 0;
bool fail= false;
topLevel= false;
bool inextension= false;
Variable V_buf, alpha, cleanUp;
CanonicalForm prim_elem, im_prim_elem;
CFList source, dest;
do //first do
{
if (inextension)
random_element= randomElement (m, V_buf, l, fail);
else
random_element= FpRandomElement (m, l, fail);
if (random_element == 0 && !fail)
{
if (!find (l, random_element))
l.append (random_element);
continue;
}
if (!fail && !inextension)
{
CFList list;
TIMING_START (gcd_recursion);
G_random_element=
sparseGCDFp (ppA (random_element,x), ppB (random_element,x), topLevel,
list);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
}
else if (!fail && inextension)
{
CFList list;
TIMING_START (gcd_recursion);
G_random_element=
sparseGCDFq (ppA (random_element, x), ppB (random_element, x), alpha,
list, topLevel);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
}
else if (fail && !inextension)
{
source= CFList();
dest= CFList();
CFList list;
CanonicalForm mipo;
int deg= 2;
bool initialized= false;
do
{
mipo= randomIrredpoly (deg, x);
if (initialized)
setMipo (alpha, mipo);
else
alpha= rootOf (mipo);
inextension= true;
fail= false;
initialized= true;
random_element= randomElement (m, alpha, l, fail);
deg++;
} while (fail);
cleanUp= alpha;
V_buf= alpha;
list= CFList();
TIMING_START (gcd_recursion);
G_random_element=
sparseGCDFq (ppA (random_element, x), ppB (random_element, x), alpha,
list, topLevel);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
}
else if (fail && inextension)
{
source= CFList();
dest= CFList();
Variable V_buf3= V_buf;
V_buf= chooseExtension (V_buf);
bool prim_fail= false;
Variable V_buf2;
CanonicalForm prim_elem, im_prim_elem;
prim_elem= primitiveElement (alpha, V_buf2, prim_fail);
if (V_buf3 != alpha)
{
m= mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
G_m= mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
newtonPoly= mapDown (newtonPoly, prim_elem, im_prim_elem, alpha, source,
dest);
ppA= mapDown (ppA, prim_elem, im_prim_elem, alpha, source, dest);
ppB= mapDown (ppB, prim_elem, im_prim_elem, alpha, source, dest);
gcdlcAlcB= mapDown (gcdlcAlcB, prim_elem, im_prim_elem, alpha, source,
dest);
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, alpha,
source, dest);
}
ASSERT (!prim_fail, "failure in integer factorizer");
if (prim_fail)
; //ERROR
else
im_prim_elem= mapPrimElem (prim_elem, alpha, V_buf);
DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (alpha));
DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (V_buf2));
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= mapUp (i.getItem(), alpha, V_buf, prim_elem,
im_prim_elem, source, dest);
m= mapUp (m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
G_m= mapUp (G_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
newtonPoly= mapUp (newtonPoly, alpha, V_buf, prim_elem, im_prim_elem,
source, dest);
ppA= mapUp (ppA, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
ppB= mapUp (ppB, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
gcdlcAlcB= mapUp (gcdlcAlcB, alpha, V_buf, prim_elem, im_prim_elem,
source, dest);
fail= false;
random_element= randomElement (m, V_buf, l, fail );
DEBOUTLN (cerr, "fail= " << fail);
CFList list;
TIMING_START (gcd_recursion);
G_random_element=
sparseGCDFq (ppA (random_element, x), ppB (random_element, x), V_buf,
list, topLevel);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
alpha= V_buf;
}
if (!G_random_element.inCoeffDomain())
d0= totaldegree (G_random_element, Variable(2),
Variable (G_random_element.level()));
else
d0= 0;
if (d0 == 0)
{
if (inextension)
prune (cleanUp);
return N(gcdcAcB);
}
if (d0 > d)
{
if (!find (l, random_element))
l.append (random_element);
continue;
}
G_random_element=
(gcdlcAlcB(random_element, x)/uni_lcoeff (G_random_element))
* G_random_element;
skeleton= G_random_element;
if (!G_random_element.inCoeffDomain())
d0= totaldegree (G_random_element, Variable(2),
Variable (G_random_element.level()));
else
d0= 0;
if (d0 < d)
{
m= gcdlcAlcB;
newtonPoly= 1;
G_m= 0;
d= d0;
}
H= newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
if (uni_lcoeff (H) == gcdlcAlcB)
{
cH= uni_content (H);
ppH= H/cH;
ppH /= Lc (ppH);
DEBOUTLN (cerr, "ppH= " << ppH);
if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
{
if (inextension)
prune (cleanUp);
return N(gcdcAcB*ppH);
}
}
G_m= H;
newtonPoly= newtonPoly*(x - random_element);
m= m*(x - random_element);
if (!find (l, random_element))
l.append (random_element);
if ((getCharacteristic() > 3 && size (skeleton) < 200))
{
CFArray Monoms;
CFArray* coeffMonoms;
do //second do
{
if (inextension)
random_element= randomElement (m, alpha, l, fail);
else
random_element= FpRandomElement (m, l, fail);
if (random_element == 0 && !fail)
{
if (!find (l, random_element))
l.append (random_element);
continue;
}
bool sparseFail= false;
if (!fail && !inextension)
{
CFList list;
TIMING_START (gcd_recursion);
if (LC (skeleton).inCoeffDomain())
G_random_element=
monicSparseInterpol(ppA(random_element, x), ppB (random_element, x),
skeleton, x, sparseFail, coeffMonoms,
Monoms);
else
G_random_element=
nonMonicSparseInterpol(ppA(random_element,x), ppB(random_element,x),
skeleton, x, sparseFail,
coeffMonoms, Monoms);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
}
else if (!fail && inextension)
{
CFList list;
TIMING_START (gcd_recursion);
if (LC (skeleton).inCoeffDomain())
G_random_element=
monicSparseInterpol(ppA (random_element,x), ppB (random_element, x),
skeleton, alpha, sparseFail, coeffMonoms,
Monoms);
else
G_random_element=
nonMonicSparseInterpol(ppA(random_element,x), ppB(random_element,x),
skeleton, alpha, sparseFail, coeffMonoms,
Monoms);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
}
else if (fail && !inextension)
{
source= CFList();
dest= CFList();
CFList list;
CanonicalForm mipo;
int deg= 2;
bool initialized= false;
do
{
mipo= randomIrredpoly (deg, x);
if (initialized)
setMipo (alpha, mipo);
else
alpha= rootOf (mipo);
inextension= true;
fail= false;
initialized= true;
random_element= randomElement (m, alpha, l, fail);
deg++;
} while (fail);
cleanUp= alpha;
V_buf= alpha;
list= CFList();
TIMING_START (gcd_recursion);
if (LC (skeleton).inCoeffDomain())
G_random_element=
monicSparseInterpol (ppA (random_element,x), ppB (random_element,x),
skeleton, alpha, sparseFail, coeffMonoms,
Monoms);
else
G_random_element=
nonMonicSparseInterpol(ppA(random_element,x), ppB(random_element,x),
skeleton, alpha, sparseFail, coeffMonoms,
Monoms);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
}
else if (fail && inextension)
{
source= CFList();
dest= CFList();
Variable V_buf3= V_buf;
V_buf= chooseExtension (V_buf);
bool prim_fail= false;
Variable V_buf2;
CanonicalForm prim_elem, im_prim_elem;
prim_elem= primitiveElement (alpha, V_buf2, prim_fail);
if (V_buf3 != alpha)
{
m= mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
G_m= mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
newtonPoly= mapDown (newtonPoly, prim_elem, im_prim_elem, alpha,
source, dest);
ppA= mapDown (ppA, prim_elem, im_prim_elem, alpha, source, dest);
ppB= mapDown (ppB, prim_elem, im_prim_elem, alpha, source, dest);
gcdlcAlcB= mapDown (gcdlcAlcB, prim_elem, im_prim_elem, alpha,
source, dest);
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, alpha,
source, dest);
}
ASSERT (!prim_fail, "failure in integer factorizer");
if (prim_fail)
; //ERROR
else
im_prim_elem= mapPrimElem (prim_elem, alpha, V_buf);
DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (alpha));
DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (V_buf2));
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= mapUp (i.getItem(), alpha, V_buf, prim_elem,
im_prim_elem, source, dest);
m= mapUp (m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
G_m= mapUp (G_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
newtonPoly= mapUp (newtonPoly, alpha, V_buf, prim_elem, im_prim_elem,
source, dest);
ppA= mapUp (ppA, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
ppB= mapUp (ppB, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
gcdlcAlcB= mapUp (gcdlcAlcB, alpha, V_buf, prim_elem, im_prim_elem,
source, dest);
fail= false;
random_element= randomElement (m, V_buf, l, fail );
DEBOUTLN (cerr, "fail= " << fail);
CFList list;
TIMING_START (gcd_recursion);
if (LC (skeleton).inCoeffDomain())
G_random_element=
monicSparseInterpol (ppA (random_element, x), ppB (random_element, x),
skeleton, V_buf, sparseFail, coeffMonoms,
Monoms);
else
G_random_element=
nonMonicSparseInterpol (ppA(random_element,x), ppB(random_element,x),
skeleton, V_buf, sparseFail,
coeffMonoms, Monoms);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
alpha= V_buf;
}
if (sparseFail)
break;
if (!G_random_element.inCoeffDomain())
d0= totaldegree (G_random_element, Variable(2),
Variable (G_random_element.level()));
else
d0= 0;
if (d0 == 0)
{
if (inextension)
prune (cleanUp);
return N(gcdcAcB);
}
if (d0 > d)
{
if (!find (l, random_element))
l.append (random_element);
continue;
}
G_random_element=
(gcdlcAlcB(random_element, x)/uni_lcoeff (G_random_element))
* G_random_element;
if (!G_random_element.inCoeffDomain())
d0= totaldegree (G_random_element, Variable(2),
Variable (G_random_element.level()));
else
d0= 0;
if (d0 < d)
{
m= gcdlcAlcB;
newtonPoly= 1;
G_m= 0;
d= d0;
}
TIMING_START (newton_interpolation);
H= newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
TIMING_END_AND_PRINT (newton_interpolation,
"time for newton interpolation: ");
//termination test
if (uni_lcoeff (H) == gcdlcAlcB)
{
cH= uni_content (H);
ppH= H/cH;
ppH /= Lc (ppH);
DEBOUTLN (cerr, "ppH= " << ppH);
if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
{
if (inextension)
prune (cleanUp);
return N(gcdcAcB*ppH);
}
}
G_m= H;
newtonPoly= newtonPoly*(x - random_element);
m= m*(x - random_element);
if (!find (l, random_element))
l.append (random_element);
} while (1); //end of second do
}
else
{
if (inextension)
prune (cleanUp);
return N(gcdcAcB*modGCDFp (ppA, ppB));
}
} while (1); //end of first do
}
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
sparseGCDFq
CanonicalForm sparseGCDFq(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, CFList &l, bool &topLevel)
Definition cfModGcd.cc:3138
monicSparseInterpol
CanonicalForm monicSparseInterpol(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms)
Definition cfModGcd.cc:2207
nonMonicSparseInterpol
CanonicalForm nonMonicSparseInterpol(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms)
Definition cfModGcd.cc:2491
sparseGCDFp
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition cfModGcd.cc:3570

## sparseGCDFq() [1/2]

CanonicalForm sparseGCDFq | ( | const CanonicalForm & | A,
|  | const CanonicalForm & | B,
|  | const Variable & | alpha )

inline static

Zippel's sparse GCD over Fq.

Parameters

  [in] | A | poly over F_q
  [in] | B | poly over F_q
  [in] | alpha | algebraic variable

Definition at line 108 of file cfModGcd.h.

{
CFList list;
bool topLevel= true;
return sparseGCDFq (A, B, alpha, list, topLevel);
}
sparseGCDFq
CanonicalForm sparseGCDFq(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, CFList &l, bool &topLevel)
Definition cfModGcd.cc:3138

## sparseGCDFq() [2/2]

CanonicalForm sparseGCDFq | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | G,
|  | const Variable & | alpha,
|  | CFList & | l,
|  | bool & | topLevel )

Definition at line 3138 of file cfModGcd.cc.

{
CanonicalForm A= F;
CanonicalForm B= G;
if (F.isZero() && degree(G) > 0) return G/Lc(G);
else if (G.isZero() && degree (F) > 0) return F/Lc(F);
else if (F.isZero() && G.isZero()) return F.genOne();
if (F.inBaseDomain() || G.inBaseDomain()) return F.genOne();
if (F.isUnivariate() && fdivides(F, G)) return F/Lc(F);
if (G.isUnivariate() && fdivides(G, F)) return G/Lc(G);
if (F == G) return F/Lc(F);
CFMap M,N;
int best_level= myCompress (A, B, M, N, topLevel);
if (best_level == 0) return B.genOne();
A= M(A);
B= M(B);
Variable x= Variable (1);
//univariate case
if (A.isUnivariate() && B.isUnivariate())
return N (gcd (A, B));
CanonicalForm cA, cB; // content of A and B
CanonicalForm ppA, ppB; // primitive part of A and B
CanonicalForm gcdcAcB;
cA = uni_content (A);
cB = uni_content (B);
gcdcAcB= gcd (cA, cB);
ppA= A/cA;
ppB= B/cB;
CanonicalForm lcA, lcB; // leading coefficients of A and B
CanonicalForm gcdlcAlcB;
lcA= uni_lcoeff (ppA);
lcB= uni_lcoeff (ppB);
if (fdivides (lcA, lcB))
{
if (fdivides (A, B))
return F/Lc(F);
}
if (fdivides (lcB, lcA))
{
if (fdivides (B, A))
return G/Lc(G);
}
gcdlcAlcB= gcd (lcA, lcB);
int d= totaldegree (ppA, Variable (2), Variable (ppA.level()));
int d0;
if (d == 0)
return N(gcdcAcB);
d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
if (d0 < d)
d= d0;
if (d == 0)
return N(gcdcAcB);
CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH, skeleton;
CanonicalForm newtonPoly= 1;
m= gcdlcAlcB;
G_m= 0;
H= 0;
bool fail= false;
topLevel= false;
bool inextension= false;
Variable V_buf= alpha, V_buf4= alpha;
CanonicalForm prim_elem, im_prim_elem;
CanonicalForm prim_elem_alpha, im_prim_elem_alpha;
CFList source, dest;
do // first do
{
random_element= randomElement (m, V_buf, l, fail);
if (random_element == 0 && !fail)
{
if (!find (l, random_element))
l.append (random_element);
continue;
}
if (fail)
{
source= CFList();
dest= CFList();
Variable V_buf3= V_buf;
V_buf= chooseExtension (V_buf);
bool prim_fail= false;
Variable V_buf2;
prim_elem= primitiveElement (V_buf4, V_buf2, prim_fail);
if (V_buf4 == alpha)
prim_elem_alpha= prim_elem;
if (V_buf3 != V_buf4)
{
m= mapDown (m, prim_elem, im_prim_elem, V_buf4, source, dest);
G_m= mapDown (m, prim_elem, im_prim_elem, V_buf4, source, dest);
newtonPoly= mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
source, dest);
ppA= mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
ppB= mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
gcdlcAlcB= mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4, source,
dest);
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, V_buf4,
source, dest);
}
ASSERT (!prim_fail, "failure in integer factorizer");
if (prim_fail)
; //ERROR
else
im_prim_elem= mapPrimElem (prim_elem, V_buf4, V_buf);
if (V_buf4 == alpha)
im_prim_elem_alpha= im_prim_elem;
else
im_prim_elem_alpha= mapUp (im_prim_elem_alpha, V_buf4, V_buf, prim_elem,
im_prim_elem, source, dest);
DEBOUTLN (cerr, "getMipo (V_buf4)= " << getMipo (V_buf4));
DEBOUTLN (cerr, "getMipo (V_buf2)= " << getMipo (V_buf2));
inextension= true;
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= mapUp (i.getItem(), V_buf4, V_buf, prim_elem,
im_prim_elem, source, dest);
m= mapUp (m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
G_m= mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
newtonPoly= mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
source, dest);
ppA= mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
ppB= mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
gcdlcAlcB= mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
source, dest);
fail= false;
random_element= randomElement (m, V_buf, l, fail );
DEBOUTLN (cerr, "fail= " << fail);
CFList list;
TIMING_START (gcd_recursion);
G_random_element=
sparseGCDFq (ppA (random_element, x), ppB (random_element, x), V_buf,
list, topLevel);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
V_buf4= V_buf;
}
else
{
CFList list;
TIMING_START (gcd_recursion);
G_random_element=
sparseGCDFq (ppA(random_element, x), ppB(random_element, x), V_buf,
list, topLevel);
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
}
if (!G_random_element.inCoeffDomain())
d0= totaldegree (G_random_element, Variable(2),
Variable (G_random_element.level()));
else
d0= 0;
if (d0 == 0)
{
if (inextension)
prune1 (alpha);
return N(gcdcAcB);
}
if (d0 > d)
{
if (!find (l, random_element))
l.append (random_element);
continue;
}
G_random_element=
(gcdlcAlcB(random_element, x)/uni_lcoeff (G_random_element))
* G_random_element;
skeleton= G_random_element;
if (!G_random_element.inCoeffDomain())
d0= totaldegree (G_random_element, Variable(2),
Variable (G_random_element.level()));
else
d0= 0;
if (d0 < d)
{
m= gcdlcAlcB;
newtonPoly= 1;
G_m= 0;
d= d0;
}
H= newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
if (uni_lcoeff (H) == gcdlcAlcB)
{
cH= uni_content (H);
ppH= H/cH;
if (inextension)
{
CFList u, v;
//maybe it's better to test if ppH is an element of F(\alpha) before
//mapping down
if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
{
DEBOUTLN (cerr, "ppH before mapDown= " << ppH);
ppH= mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha, alpha, u, v);
ppH /= Lc(ppH);
DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
prune1 (alpha);
return N(gcdcAcB*ppH);
}
}
else if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
return N(gcdcAcB*ppH);
}
G_m= H;
newtonPoly= newtonPoly*(x - random_element);
m= m*(x - random_element);
if (!find (l, random_element))
l.append (random_element);
if (getCharacteristic () > 3 && size (skeleton) < 100)
{
CFArray Monoms;
CFArray *coeffMonoms;
do //second do
{
random_element= randomElement (m, V_buf, l, fail);
if (random_element == 0 && !fail)
{
if (!find (l, random_element))
l.append (random_element);
continue;
}
if (fail)
{
source= CFList();
dest= CFList();
Variable V_buf3= V_buf;
V_buf= chooseExtension (V_buf);
bool prim_fail= false;
Variable V_buf2;
prim_elem= primitiveElement (V_buf4, V_buf2, prim_fail);
if (V_buf4 == alpha)
prim_elem_alpha= prim_elem;
if (V_buf3 != V_buf4)
{
m= mapDown (m, prim_elem, im_prim_elem, V_buf4, source, dest);
G_m= mapDown (m, prim_elem, im_prim_elem, V_buf4, source, dest);
newtonPoly= mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
source, dest);
ppA= mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
ppB= mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
gcdlcAlcB= mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4,
source, dest);
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, V_buf4,
source, dest);
}
ASSERT (!prim_fail, "failure in integer factorizer");
if (prim_fail)
; //ERROR
else
im_prim_elem= mapPrimElem (prim_elem, V_buf4, V_buf);
if (V_buf4 == alpha)
im_prim_elem_alpha= im_prim_elem;
else
im_prim_elem_alpha= mapUp (im_prim_elem_alpha, V_buf4, V_buf,
prim_elem, im_prim_elem, source, dest);
DEBOUTLN (cerr, "getMipo (V_buf4)= " << getMipo (V_buf4));
DEBOUTLN (cerr, "getMipo (V_buf2)= " << getMipo (V_buf2));
inextension= true;
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= mapUp (i.getItem(), V_buf4, V_buf, prim_elem,
im_prim_elem, source, dest);
m= mapUp (m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
G_m= mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
newtonPoly= mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
source, dest);
ppA= mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
ppB= mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
gcdlcAlcB= mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
source, dest);
fail= false;
random_element= randomElement (m, V_buf, l, fail);
DEBOUTLN (cerr, "fail= " << fail);
CFList list;
TIMING_START (gcd_recursion);
V_buf4= V_buf;
//sparseInterpolation
bool sparseFail= false;
if (LC (skeleton).inCoeffDomain())
G_random_element=
monicSparseInterpol (ppA (random_element, x), ppB(random_element,x),
skeleton,V_buf, sparseFail, coeffMonoms,Monoms);
else
G_random_element=
nonMonicSparseInterpol (ppA(random_element,x),ppB(random_element,x),
skeleton, V_buf, sparseFail, coeffMonoms,
Monoms);
if (sparseFail)
break;
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
}
else
{
CFList list;
TIMING_START (gcd_recursion);
bool sparseFail= false;
if (LC (skeleton).inCoeffDomain())
G_random_element=
monicSparseInterpol (ppA (random_element, x),ppB(random_element, x),
skeleton,V_buf, sparseFail,coeffMonoms, Monoms);
else
G_random_element=
nonMonicSparseInterpol (ppA(random_element,x),ppB(random_element,x),
skeleton, V_buf, sparseFail, coeffMonoms,
Monoms);
if (sparseFail)
break;
TIMING_END_AND_PRINT (gcd_recursion,
"time for recursive call: ");
DEBOUTLN (cerr, "G_random_element= " << G_random_element);
}
if (!G_random_element.inCoeffDomain())
d0= totaldegree (G_random_element, Variable(2),
Variable (G_random_element.level()));
else
d0= 0;
if (d0 == 0)
{
if (inextension)
prune1 (alpha);
return N(gcdcAcB);
}
if (d0 > d)
{
if (!find (l, random_element))
l.append (random_element);
continue;
}
G_random_element=
(gcdlcAlcB(random_element, x)/uni_lcoeff (G_random_element))
* G_random_element;
if (!G_random_element.inCoeffDomain())
d0= totaldegree (G_random_element, Variable(2),
Variable (G_random_element.level()));
else
d0= 0;
if (d0 < d)
{
m= gcdlcAlcB;
newtonPoly= 1;
G_m= 0;
d= d0;
}
TIMING_START (newton_interpolation);
H= newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
TIMING_END_AND_PRINT (newton_interpolation,
"time for newton interpolation: ");
//termination test
if (uni_lcoeff (H) == gcdlcAlcB)
{
cH= uni_content (H);
ppH= H/cH;
if (inextension)
{
CFList u, v;
//maybe it's better to test if ppH is an element of F(\alpha) before
//mapping down
if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
{
DEBOUTLN (cerr, "ppH before mapDown= " << ppH);
ppH= mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha, alpha, u, v);
ppH /= Lc(ppH);
DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
prune1 (alpha);
return N(gcdcAcB*ppH);
}
}
else if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
{
return N(gcdcAcB*ppH);
}
}
G_m= H;
newtonPoly= newtonPoly*(x - random_element);
m= m*(x - random_element);
if (!find (l, random_element))
l.append (random_element);
} while (1);
}
} while (1);
}
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
prune1
void prune1(const Variable &alpha)
Definition variable.cc:291

## terminationTest()

bool terminationTest | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | G,
|  | const CanonicalForm & | coF,
|  | const CanonicalForm & | coG,
|  | const CanonicalForm & | cand )