351{
353
354 if (
A.isZero() ||
B.isZero())
355 return 0;
356
359 if (
A.level() <
x.level())
361 if (
B.level() <
x.level())
363
364 if (degAx == 0)
366 else if (degBx == 0)
368
369 if (
A.isUnivariate() &&
B.isUnivariate() &&
A.level() ==
B.level())
371
374
377
380
382
386
389
395 bool extOfExt= false;
399 if (!algExt && (
p < (1 << 28)))
400 {
401
402
407 gen= AlgExtGen.
clone();
408 for (
int i= 0;
i <
p;
i++)
410 }
411 else if (!algExt)
412 {
415 }
416 else
417 {
420 {
421 mpz_t field_size;
422 mpz_init (field_size);
423 mpz_ui_pow_ui (field_size,
p,
425
426
427 if (mpz_fits_sint_p (field_size))
428 {
433 bool primFail= false;
434 extOfExt= true;
436 ASSERT (!primFail,
"failure in integer factorizer");
437 if (primFail)
438 ;
439 else
441 F=
mapUp (F,
alpha,
v, primElemAlpha, imPrimElemAlpha, source, dest);
442 G=
mapUp (
G,
alpha,
v, primElemAlpha, imPrimElemAlpha, source, dest);
443 }
444 else
445 {
447 mpz_ui_pow_ui (field_size,
p, deg);
449 {
451 mpz_ui_pow_ui (field_size,
p, deg);
452 }
454 {
458 bool primFail= false;
459 extOfExt= true;
461 ASSERT (!primFail,
"failure in integer factorizer");
462 if (primFail)
463 ;
464 else
466 F=
mapUp (F,
alpha,
v, primElemAlpha, imPrimElemAlpha, source, dest);
467 G=
mapUp (
G,
alpha,
v, primElemAlpha, imPrimElemAlpha, source, dest);
468 }
469 }
470 mpz_clear (field_size);
471 }
473 gen= AlgExtGen.
clone();
474 for (
int i= 0;
i <
p;
i++)
476 }
478 int equalCount= 0;
480 do
481 {
483
485
486 H=
newtonInterp ((*gen).item(), recResult, newtonPoly, modResult,
y);
487
489 equalCount++;
490 else
491 equalCount= 0;
492
494 if (
count >
bound || (prob && equalCount == 2 && !
H.inCoeffDomain()))
495 {
497 break;
498 else if (algExt)
499 {
500 if (extOfExt && !
isInExtension (
H, imPrimElemAlpha, 1, primElemAlpha,
501 dest, source))
502 {
503 H=
mapDown (
H, primElemAlpha, imPrimElemAlpha,
alpha, dest, source);
505 break;
506 }
507 else if (!extOfExt)
508 break;
509 }
510 }
511
513 newtonPoly *= (
y - (*gen).item());
514 if ((*gen).hasItems())
515 (*gen).next();
516 else
518 } while (1);
519
520 delete gen;
521
523}
const CanonicalForm CFMap CFMap & N
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
const CanonicalForm CFMap CFMap & N
CanonicalForm resultantFp(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Fp
static CanonicalForm uniResultant(const CanonicalForm &F, const CanonicalForm &G)
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
const CanonicalForm CFMap & M
static CanonicalForm newtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x)
#define STICKYASSERT(expression, message)
#define ASSERT(expression, message)
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
static CanonicalForm bound(const CFMatrix &M)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
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
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 ,...
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
generate all elements in F_p(alpha) starting from 0
virtual class for generators
virtual CFGenerator * clone() const
generate all elements in F_p starting from 0
CFGenerator * clone() const
factory's class for variables
const CanonicalForm int const CFList const Variable & y
const Variable & v
< [in] a sqrfree bivariate poly
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
void FACTORY_PUBLIC prune(Variable &alpha)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
gmp_float log(const gmp_float &a)
const signed long ceil(const ampf< Precision > &x)
int status int void size_t count