1 #ifndef _DUNIPOLYNOMIAL_H_ 2 #define _DUNIPOLYNOMIAL_H_ 5 #include "../polynomial.h" 7 #include "../DyadicRationalNumber/Multiplication/multiplication.h" 9 #include "../FFT/src/dft_general.h" 10 #include "../FFT/src/dft16.h" 11 #include "../FFT/src/dft_general_fermat.h" 13 #include "../Utils/TemplateHelpers.hpp" 19 template <
class Field>
22 private Derived_from<Field, BPASField<Field>>
31 for (
int i = 0; i < n; ++i)
35 if (curd && q.curd && (name != q.name))
39 for (
int i = 0; i <= curd; ++i) {
40 if (coef[i] != q.coef[i])
49 for (
int i = curd, j = b.curd; j > -1; --i, --j) {
50 Field elem = t * b.coef[j];
56 for (
int i = curd, j = b.curd; i > -1; --i, --j) {
57 Field elem = coef[i] * c;
59 elem += t * b.coef[j];
66 inline void resetDegree() {
67 for (
int i = curd; i > 0; --i) {
87 Field lc = b.coef[b.curd];
95 return a / a.coef[a.curd];
103 static mpz_class p1, p2, p3, p4, p5, p6, p7;
113 characteristic = coef[0].characteristic;
121 if (s < 1) { s = 1; }
128 characteristic = coef[0].characteristic;
135 characteristic = e.characteristic;
145 std::copy(b.coef, b.coef+n, coef);
174 inline Field trailingCoefficient()
const {
175 for (
size_t i = 0; i <= curd; ++i) {
183 inline Integer numberOfTerms()
const {
185 for (
size_t i = 0; i <= curd; ++i) {
201 std::cout <<
"BPAS: warning, try to access a non-exist coefficient " << k <<
" from DUFP(" << n <<
")." << std::endl;
222 if (k >= n || k < 0) {
223 std::cout <<
"BPAS: error, DUFP(" << n <<
") but trying to access " << k <<
"." << std::endl;
228 if (k > curd && value != 0){
257 if (n) {
delete [] coef; n = 0; }
262 std::copy(b.coef, b.coef+n, coef);
278 return !(isEqual(b));
296 return (coef[0] == 0);
316 return (coef[0].
isOne());
327 for (
int i = 1; i < n; ++i)
347 coef[0].negativeOne();
348 for (
int i = 1; i < n; ++i)
357 if (curd) {
return 0; }
358 else if (!coef[0].
isZero()) {
return 1; }
364 Field leadInv = lead.inverse();
382 return Field((
int)!
isZero());
386 std::cerr <<
"DenseUnivariatePolynomial<Field>::primitivePart() NOT YET IMPLEMENTED" << std::endl;
402 unsigned long int q = e / 2, r = e % 2;
404 for (
int i = 0; i < q; ++i)
406 if (r) { res *= *
this; }
426 int s = curd + k + 1;
431 r.coef =
new Field[s];
432 for (
int i = 0; i < k; ++i)
434 for (
int i = k; i < s; ++i)
435 r.coef[i] = coef[i-k];
458 int s = curd - k + 1;
463 r.coef =
new Field[s];
464 for (
int i = 0; i < s; ++i)
465 r.coef[i] = coef[i+k];
486 if (!curd) {
return (b + coef[0]); }
488 return (*
this + b.coef[0]);
490 if (name != b.name) {
491 std::cout <<
"BPAS: error, trying to add between Q[" << name <<
"] and Q[" << b.name <<
"]." << std::endl;
495 int size = (curd > b.curd)? curd+1 : b.curd+1;
500 res.coef =
new Field[size];
501 for (
int i = 0; i < size; ++i) {
532 for (
int i = curd; i >= 0; --i) {
534 coef[i] += b.coef[i];
569 if (!curd) {
return (coef[0] - b); }
570 if (!b.curd) {
return (*
this - b.coef[0]); }
571 if (name != b.name) {
572 std::cout <<
"BPAS: error, trying to subtract between Field[" << name <<
"] and Field[" << b.name <<
"]." << std::endl;
577 int size = (curd > b.curd)? curd+1 : b.curd+1;
582 res.coef =
new Field[size];
583 for (
int i = 0; i < size; ++i) {
615 for (
int i = 0; i <= curd; ++i)
616 res.coef[i] = -coef[i];
625 for (
int i = curd; i >= 0; --i) {
627 coef[i] -= b.coef[i];
664 else if(cmp(p, p2)==0)
666 else if(cmp(p, p3)==0)
668 else if(cmp(p, p4)==0)
670 else if(cmp(p, p5)==0)
672 else if(cmp(p, p6)==0)
674 else if(cmp(p, p7)==0)
686 return (b * coef[0]);
689 return (*
this * b.coef[0]);
691 if (name != b.name) {
692 std::cout <<
"BPAS: error, trying to multiply between Field[" << name <<
"] and Field[" << b.name <<
"]." << std::endl;
704 res2->coef =
new Field[size];
709 res.coef =
new Field[size];
711 if(Field::characteristic == 0){
749 for(
int i=0; i<d; i++){
750 for(
int j=0; j<m; j++){
751 res.coef[i+j] += coef[i] * b.coef[j];
874 for(
int i=0; i<d; i++){
875 for(
int j=0; j<m; j++){
876 res.coef[i+j] += coef[i] * b.coef[j];
886 DFT_general(field, K, e, omega);
891 DFT_general(field, K, e, omega);
895 std::cout <<
" i called generalized FFT " << std::endl;
896 dft_general_fermat(field, K, e, omega);
913 inverse_DFT(field, K, e, omega);
928 inverse_DFT(field, K, e, omega);
943 inverse_fermat_DFT(field, K, e, omega);
972 if (e != 0 && e != 1) {
973 for (
int i = 0; i <= curd; ++i)
976 else if (e == 0) {
zero(); }
1002 std::cout <<
"BPAS: error, dividend is zero from DUFP." << std::endl;
1006 return (*
this /= b.coef[0]);
1012 if (name != b.name) {
1013 std::cout <<
"BPAS: error,rem trying to exact divide between Field[" << name <<
"] and Field[" << b.name <<
"]." << std::endl;
1019 while (rem.curd >= b.curd) {
1020 Field lc = rem.coef[rem.curd] / b.coef[b.curd];
1021 int diff = rem.curd - b.curd;
1022 rem.pomopo(1, -lc, b);
1026 if (!rem.isZero()) {
1027 std::cout <<
"BPAS: error, not exact division from DUFP." << std::endl;
1050 std::cout <<
"BPAS: error, dividend is zero from DUFP." << std::endl;
1054 for (
int i = 0; i <= curd; ++i)
1063 std::cout <<
"BPAS: error, dividend is zero from DUFP." << std::endl;
1071 q.coef =
new Field[1];
1074 q.coef[0] = c / p.coef[0];
1088 std::cout <<
"BPAS: error, dividend is zero from DUFP." << std::endl;
1091 else if (b.coef[b.curd] != 1) {
1092 std::cout <<
"BPAS: error, leading coefficient is not one in monicDivide() from DUFP." << std::endl;
1105 if (name != b.name) {
1106 std::cout <<
"BPAS: error, trying to monic divide between [" << name <<
"] and Q[" << b.name <<
"]." << std::endl;
1110 int size = curd - b.curd + 1;
1112 quo.curd = size - 1;
1114 while (curd >= b.curd) {
1115 Field lc = coef[curd];
1116 int diff = curd - b.curd;
1118 quo.coef[diff] = lc;
1132 return rem->monicDivide(b);
1147 int da = curd, db = b.curd;
1148 if (b.isZero() || !db) {
1149 std::cout <<
"BPAS: error, dividend is zero or constant." << std::endl;
1158 if (name != b.name) {
1159 std::cout <<
"BPAS: error, trying to pseudo divide between Field[" << name <<
"] and Field[" << b.name <<
"]." << std::endl;
1169 int size = curd - b.curd + 1;
1171 quo.curd = size - 1;
1173 int e = 0, diff = da - db;
1174 Field blc = b.coef[b.curd];
1175 while (curd >= b.curd) {
1176 Field lc = coef[curd];
1177 int k = curd - b.curd;
1180 pomopo(blc, -coef[curd], b);
1184 for (
int i = e; i <= diff; ++i)
1201 return rem->lazyPseudoDivide(b, c, d);
1256 while (!b.isZero()) {
1258 q.name = r.name = name;
1259 Field e = b.coef[b.curd];
1264 q = g->monicDivide(b, &r);
1280 a1 /= g->coef[g->curd];
1281 *g /= g->coef[g->curd];
1296 *s = a.halfExtendedEuclidean(b, &g);
1297 if (g.coef[g.curd] != 1) {
1298 f /= g.coef[g.curd];
1299 g /= g.coef[g.curd];
1301 q = f.monicDivide(g, &r);
1303 std::cout <<
"BPAS: error, " << *
this <<
" is not in the ideal (" << a <<
", " << b <<
") from DUQP." << std::endl;
1308 Field e = b.coef[b.curd];
1309 if (e != 1) { b /= e; }
1310 if (s->curd >= b.curd) {
1312 s->monicDivide(b, &r);
1318 if (e != 1) { g /= e; }
1319 *t = g.monicDivide(b);
1328 *
this = this->derivative(k);
1337 if (k <= 0) {
return *
this; }
1338 for (
int i = k; i <= ret.curd; ++i) {
1339 ret.coef[i-k] = ret.coef[i];
1340 for (
int j = 0; j < k; ++j)
1341 ret.coef[i-k] *= (i - j);
1349 return derivative(1);
1361 b.coef =
new Field[b.n];
1363 for (
int i = 0; i <= curd; ++i)
1364 b.coef[i+1] = coef[i] / (i + 1);
1375 Field px = coef[curd];
1376 for (
int i = curd-1; i > -1; --i)
1377 px = px * x + coef[i];
1389 return (coef[0] == 0);
1397 if (
isZero()) {
return q; }
1398 if (q.isZero()) {
return *
this; }
1399 if (!curd || !q.curd) {
1406 if (name != q.name) {
1407 std::cout <<
"BPAS: error, remtrying to compute GCD between Q[" << name <<
"] and Q[" << q.name <<
"]." << std::endl;
1413 r = euclideanGCD(q);
1432 std::vector<DenseUnivariatePolynomial<Field> > sf;
1434 sf.push_back(*
this);
1436 else if (curd == 1) {
1439 t.coef[0] = coef[curd];
1441 t = *
this / t.coef[0];
1454 while (!z.isZero()) {
1467 for (
int i = 0; i < sf.size(); ++i) {
1468 e *= sf[i].coef[sf[i].curd];
1469 sf[i] /= sf[i].coef[sf[i].curd];
1474 sf.insert(sf.begin(), t);
1478 f.setRingElement(sf[0]);
1479 for (
int i = 1; i < sf.size(); ++i) {
1480 f.addFactor(sf[i], i);
1494 for (
int i = 0; i <= curd; ++i)
1495 coef[i] = coef[i+1];
1512 for (
int i = 0; i < (curd+1)/2; ++i) {
1513 Field elem = coef[i];
1514 coef[i] = coef[curd-i];
1515 coef[curd-i] = elem;
1525 for (
int i = 0; i <= curd; ++i)
1526 coef[i] <<= (curd - i) * k;
1534 for (
int i = 0; i <= curd; ++i)
1543 for (
int i = 0; i <= curd; ++i) {
1555 for (
int i = 0; i <= curd; ++i)
1566 inline void print(std::ostream& out)
const {
1569 for (
int i = 0; i <= this->curd; ++i) {
1570 if (!this->coef[i].
isZero()) {
1574 if (!this->coef[i].
isOne())
1575 out << this->coef[i] <<
"*";
1580 else { out << this->coef[i]; }
1584 if (isFirst) { out <<
"0"; }
1588 std::cerr <<
"DenseUnivariatePolynomial<Field>::convertToExpressionTree() NOT YET IMPLEMENTED" << std::endl;
1602 std::cerr <<
"DenseUnivariatePolynomial::ExactDivision NOT YET IMPLEMENTED" << std::endl;
1608 std::cerr <<
"DenseUnivariatePolynomial::extendedEuclidean NOT YET IMPLEMENTED" << std::endl;
1614 std::cerr <<
"DenseUnivariatePolynomial::quotient NOT YET IMPLEMENTED" << std::endl;
1620 std::cerr <<
"DenseUnivariatePolynomial::remainder NOT YET IMPLEMENTED" << std::endl;
1644 y.setVariableName(this->name);
1645 for(
int i = this->
degree(); i >=0; i--){
1663 int r = ceil(log2(l));
1664 for(
int i=0; i<r; i++){
1665 g = (g*two) - ((*
this)*(g*g));
1666 int deg = g.degree();
1667 int it = pow(2, i+1);
1669 temp.setVariableName(this->name);
1671 for(
int j=0; j<it; j++){
1672 temp.setCoefficient(j, g.coefficient(j));
1694 int m = this->
degree() - b.degree();
1698 tempQuot = this->
Reverse() * bb.NewtonIterationInversion(l);
1700 tempModQuot.setVariableName(this->name);
1701 for(
int j=0; j<m+1; j++){
1702 tempModQuot.setCoefficient(j, tempQuot.coefficient(j));
1704 q = tempModQuot.Reverse();
1705 r = (*this) - (b*q);
1709 template <
class Field>
1711 template <
class Field>
1713 template <
class Field>
1714 mpz_class
DenseUnivariatePolynomial<Field>::p3(
"52374250506775412587080182017685909013279339260195121351951847958786555732255090462694066661827009813312276859354987266719224819790981416185422168457217",10);
1715 template <
class Field>
1716 mpz_class
DenseUnivariatePolynomial<Field>::p4(
"41855814947416230160905824077102044107723669195743478941314613188961602997492974631771080284897031989884853955219823218284507222180203198418365663867454557929637857661786690253443410218509127538830031125593957763469901695303351030684228602570766096943274989297544663448958866408079360000000000000001",10);
1717 template <
class Field>
1718 mpz_class
DenseUnivariatePolynomial<Field>::p5(
"2877263539710446421731156102715413817501924683780203686146470704479400367915116616138891969740546502029403969510010797456265193559830952776697283528940113468571280365197702193026548850188074400758303550622614323711553963509499617917475399195332219370635307438240127286098723642161848281710791141158514433179269730389996820841870847439976376347222063201890220935378395463717774388387120384211168483542746311978533439751087743189685602954995966307828869222780207146437854468321622285523442498620491234986821135672225672571988303097617848628157952640424574080207395225600000000000000000000000000000001",10);
1719 template <
class Field>
1720 mpz_class
DenseUnivariatePolynomial<Field>::p6(
"56616002759896959989415322854958727265928518265558894081721915112338478642152987382081777901106335963367885845155763417916565153797308803666707803977539356324269844089304564587076354736376986405278272779897162317130287620982152662704148023386047880191229049189096093126016047741788639253285397227699187048459276900664828446151952389379779872483448827148216422038130194295758324036868739847281348652718382706086985165783151098320403070769834562613385987477083199297963686734355937454052502472824036058010003416215471582444408483889852282411679533336856925440851946178882063994444491916045719853726844950223273102469496195879587497097269220475494120869128671848644970662426110042888649905237795797441676015340881806045138767954343337713455178248747715202796137422620937669272350685622178511493534367574328398416598592863781482592003147323049228191952409766232800103525201364901470397364906237602845461804081111668634216071070833972247292545003189326173445338852542217465888156430817411944210832836729444740015333742919095761005296073941774939988656174783310275846314511363344139168277105168250508129957477572900470266117913389691465601936338974995950792881631257549184987642764414960873189711746068672863213585432577",10);
1721 template <
class Field>
1722 mpz_class
DenseUnivariatePolynomial<Field>::p7(
"1090748133587739207496133104623209685652043340944525583769922043686052876979141040038395373676653597591795495926807366279537470195844376816521507523618991686398153905679787781478759328905566212525054647896231628355359135635798293361069723097331736557050988577986243892532466698313135887886138444662377632073755381143950221100025346676696096637756641164069467382471667320021238955178621076923370794798694345041333296701870548156651489758101607968522281523969635189200754728978386730361168951561126882965293650334538609649761122401061010853886509602124698406378631272561442673369233937827268652039439967721278901678024095092864613759484683254583736063704358175932953266749684554868685618312267884858266625457439986285293580091133149878361352074448701717504456518088365128951751801324867934946295450111407936849396611409550525348661741918663903030770894532253322458469943425510889282843922868145807907363320595378693696835191869459437314830716877183603950247193579548207267489507689973156425200759112179070584550934920498931256877825412489146370885286547409945479643242694187863206290671548410690203340958006276613646712414730669667136223216464966782734564195802691203036768257805594494102413460722901406746958482564038382712381753485759119365977102301962480617202907182258596705133279208778898957530866346338095658945650199559035759233831660684522622662629611826038362788351572091930801750440291059713981728995722747793865224424707283629868761313993150399745881815938602359160601744218529135375895347494668407421931150844787149547879919791239585278863789643049041266244553112251574272797287440972746560481170921474633126611400596027422225750981318016619477921226148845565965761129968247215480526365772473453996471123113518375556705346341505539769221542741170266489368211724332244794506899906126995079451869450859316306542657546308047179341725779510114986968935109860258498110066067846826136020542550539706591317400144521343503647697440441721640835065587388170041690014385725998766494102073306124651052994491828044263831344641288860621253508151934136220329913691383260972274841983306863608939116025856836931995877644594086124860302354708294645851839410316355926145110650494378186764629875649766904746646788333914098179144689393484186874701417787934689792155194373081952167714271117559720776224173158712008495626957577178627392043052139387289600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001",10);
void scaleTransform(int k)
Scale transform operation.
Definition: dupolynomial.h:1533
DenseUnivariatePolynomial< Field > Reverse() const
Reverse a polynomial (based on Modern Computer Algebra , Newton Iteration Chapter 9) ...
Definition: dupolynomial.h:1642
DenseUnivariatePolynomial< Field > operator-() const
Overload operator -, negate.
Definition: dupolynomial.h:611
DenseUnivariatePolynomial< Field > NewtonIterationInversion(int l)
Does Newton Iteration to compute the Reverse Inverse of a polynomial (based on Modern Computer Algebr...
Definition: dupolynomial.h:1657
DenseUnivariatePolynomial< Field > & operator>>=(int k)
Overload operator >>= replace by dividing x^k, and return the quotient.
Definition: dupolynomial.h:475
bool operator==(const DenseUnivariatePolynomial< Field > &b) const
Overload operator ==.
Definition: dupolynomial.h:285
A univariate polynomial with arbitrary BPASField coefficients represented densely.
Definition: dupolynomial.h:20
void zero()
Zero polynomial.
Definition: dupolynomial.h:304
DenseUnivariatePolynomial< Field > operator%(const DenseUnivariatePolynomial< Field > &b) const
Get the remainder of *this and b;.
Definition: dupolynomial.h:1625
bool isConstantTermZero() const
Is the least signficant coefficient zero.
Definition: dupolynomial.h:1388
bool isZero() const
Is zero polynomial.
Definition: dupolynomial.h:294
void diophantinEquationSolve(const DenseUnivariatePolynomial< Field > &a, const DenseUnivariatePolynomial< Field > &b, DenseUnivariatePolynomial< Field > *s, DenseUnivariatePolynomial< Field > *t)
s*a + t*b = c, where c in the ideal (a,b)
Definition: dupolynomial.h:1294
DenseUnivariatePolynomial< Field > operator/(const DenseUnivariatePolynomial< Field > &b) const
Overload operator / ExactDivision.
Definition: dupolynomial.h:990
DenseUnivariatePolynomial< Field > operator*(const DenseUnivariatePolynomial< Field > &b) const
Multiply to another polynomial.
Definition: dupolynomial.h:684
DenseUnivariatePolynomial< Field > & operator<<=(int k)
Overload operator <<= replace by muplitying x^k.
Definition: dupolynomial.h:444
DenseUnivariatePolynomial< Field > extendedEuclidean(const DenseUnivariatePolynomial< Field > &b, DenseUnivariatePolynomial< Field > *s=NULL, DenseUnivariatePolynomial< Field > *t=NULL) const
Perofrm the extended euclidean division on *this and b.
Definition: dupolynomial.h:1607
An ExpressionTree encompasses various forms of data that can be expressed generically as a binary tre...
Definition: ExpressionTree.hpp:17
void subtract(const DenseUnivariatePolynomial< Field > &b)
Subtract another polynomial from itself.
Definition: dupolynomial.h:624
Field evaluate(const Field &x) const
Evaluate f(x)
Definition: dupolynomial.h:1373
void negativeVariable()
Compute f(-x)
Definition: dupolynomial.h:1542
A finite field whose prime should be a generalized fermat number.
Definition: GeneralizedFermatPrimeField.hpp:36
bool isOne() const
Is polynomial a constatn 1.
Definition: dupolynomial.h:314
DenseUnivariatePolynomial< Field > operator^(long long int e) const
Overload operator ^ replace xor operation by exponentiation.
Definition: dupolynomial.h:398
Factors< DenseUnivariatePolynomial< Field > > squareFree() const
Square free.
Definition: dupolynomial.h:1431
bool SRGFNcmp(mpz_class &p)
Helper function to compare a given prime number with manually computed Generalized Fermat Numbers...
Definition: dupolynomial.h:661
Field leadingCoefficient() const
Get the leading coefficient.
Definition: dupolynomial.h:170
A prime field whose prime is 32 bits or less.
Definition: SmallPrimeField.hpp:449
void negativeOne()
Set polynomial to -1.
Definition: dupolynomial.h:345
DenseUnivariatePolynomial< Field > gcd(const DenseUnivariatePolynomial< Field > &q, int type) const
GCD(p, q)
Definition: dupolynomial.h:1396
bool operator!=(const DenseUnivariatePolynomial< Field > &b) const
Overload operator !=.
Definition: dupolynomial.h:277
void print(std::ostream &out) const
Overload stream operator <<.
Definition: dupolynomial.h:1566
DenseUnivariatePolynomial< Field > & operator-=(const DenseUnivariatePolynomial< Field > &b)
Overload operator -=.
Definition: dupolynomial.h:599
DenseUnivariatePolynomial< Field > & operator^=(long long int e)
Overload operator ^= replace xor operation by exponentiation.
Definition: dupolynomial.h:415
DenseUnivariatePolynomial< Field > monicDivide(const DenseUnivariatePolynomial< Field > &b)
Monic division Return quotient and itself become the remainder.
Definition: dupolynomial.h:1086
DenseUnivariatePolynomial< Field > pseudoDivide(const DenseUnivariatePolynomial< Field > &b, DenseUnivariatePolynomial< Field > *rem, Field *d) const
Pseudo dividsion Return the quotient.
Definition: dupolynomial.h:1232
A prime field whose prime can be arbitrarily large.
Definition: BigPrimeField.hpp:27
int isConstant() const
Is a constant.
Definition: dupolynomial.h:356
DenseUnivariatePolynomial< Field > & operator=(const DenseUnivariatePolynomial< Field > &b)
Overload operator =.
Definition: dupolynomial.h:255
void reciprocal()
Number of coefficient sign variation.
Definition: dupolynomial.h:1511
DenseUnivariatePolynomial< Field > pseudoDivide(const DenseUnivariatePolynomial< Field > &b, Field *d=NULL)
Pseudo dividsion Return the quotient and itself becomes remainder.
Definition: dupolynomial.h:1212
A simple data structure for encapsulating a collection of Factor elements.
Definition: Factors.hpp:95
bool divideByVariableIfCan()
Divide by variable if it is zero.
Definition: dupolynomial.h:1489
DenseUnivariatePolynomial< Field > operator+(const DenseUnivariatePolynomial< Field > &b) const
Overload operator +.
Definition: dupolynomial.h:485
void setCoefficient(int k, const Field &value)
Set a coefficient of the polynomial.
Definition: dupolynomial.h:221
void one()
Set polynomial to 1.
Definition: dupolynomial.h:324
void add(const DenseUnivariatePolynomial< Field > &b)
Add another polynomial to itself.
Definition: dupolynomial.h:531
DenseUnivariatePolynomial< Field > quotient(const DenseUnivariatePolynomial< Field > &b) const
Get the quotient of *this and b.
Definition: dupolynomial.h:1613
DenseUnivariatePolynomial< Field > lazyPseudoDivide(const DenseUnivariatePolynomial< Field > &b, DenseUnivariatePolynomial< Field > *rem, Field *c, Field *d) const
Lazy pseudo dividsion Return the quotient e is the exact number of division steps.
Definition: dupolynomial.h:1199
void homothetic(int k)
Homothetic operation.
Definition: dupolynomial.h:1524
An arbitrary-precision Integer.
Definition: Integer.hpp:22
bool isNegativeOne() const
Is polynomial a constatn -1.
Definition: dupolynomial.h:335
DenseUnivariatePolynomial< Field > unitCanonical(DenseUnivariatePolynomial< Field > *u, DenseUnivariatePolynomial< Field > *v) const
Obtain the unit normal (a.k.a canonical associate) of an element.
Definition: dupolynomial.h:362
An abstract class defining the interface of a univariate polynomial over an arbitrary BPASRing...
Definition: polynomial.h:88
DenseUnivariatePolynomial< Field > euclideanSize() const
Euclidean domain methods.
Definition: dupolynomial.h:1597
DenseUnivariatePolynomial< Field > halfExtendedEuclidean(const DenseUnivariatePolynomial< Field > &b, DenseUnivariatePolynomial< Field > *g)
s * a g (mod b), where g = gcd(a, b)
Definition: dupolynomial.h:1247
DenseUnivariatePolynomial< Field > euclideanDivision(const DenseUnivariatePolynomial< Field > &b, DenseUnivariatePolynomial< Field > *q=NULL) const
Perform the eucldiean division of *this and b.
Definition: dupolynomial.h:1601
An abstract class defining the interface of a Euclidean domain.
Definition: BPASEuclideanDomain.hpp:12
DenseUnivariatePolynomial< Field > remainder(const DenseUnivariatePolynomial< Field > &b) const
Get the remainder of *this and b.
Definition: dupolynomial.h:1619
Field * coefficients(int k=0)
Get coefficients of the polynomial, given start offset.
Definition: dupolynomial.h:198
Symbol variable() const
Get variable's name.
Definition: dupolynomial.h:239
An encapsulation of a mathematical symbol.
Definition: Symbol.hpp:23
DenseUnivariatePolynomial< Field > & operator/=(const DenseUnivariatePolynomial< Field > &b)
Overload operator /= ExactDivision.
Definition: dupolynomial.h:1000
virtual mpz_class characteristic()
The characteristic of this ring class.
Definition: BPASRing.hpp:87
DenseUnivariatePolynomial< Field > monicDivide(const DenseUnivariatePolynomial< Field > &b, DenseUnivariatePolynomial< Field > *rem) const
Monic division Return quotient.
Definition: dupolynomial.h:1130
void negate()
Compute -f(x)
Definition: dupolynomial.h:1554
DenseUnivariatePolynomial< Field > gcd(const DenseUnivariatePolynomial< Field > &q) const
Get GCD of *this and other.
Definition: dupolynomial.h:1422
DenseUnivariatePolynomial< Field > & operator*=(const DenseUnivariatePolynomial< Field > &b)
Overload operator *=.
Definition: dupolynomial.h:952
DenseUnivariatePolynomial< Field > & operator+=(const DenseUnivariatePolynomial< Field > &b)
Overload Operator +=.
Definition: dupolynomial.h:518
DenseUnivariatePolynomial< Field > operator>>(int k) const
Overload operator >> replace by dividing x^k, and return the quotient.
Definition: dupolynomial.h:455
Field coefficient(int k) const
Get a coefficient of the polynomial.
Definition: dupolynomial.h:210
DenseUnivariatePolynomial< Field > operator<<(int k) const
Overload operator << replace by muplitying x^k.
Definition: dupolynomial.h:425
Integer degree() const
Get degree of the polynomial.
Definition: dupolynomial.h:161
DenseUnivariatePolynomial< Field > & operator%=(const DenseUnivariatePolynomial< Field > &b)
Assign *this to be the remainder of *this and b.
Definition: dupolynomial.h:1631
void differentiate(int k)
Compute k-th differentiate.
Definition: dupolynomial.h:1327
Field content() const
Content of the polynomial.
Definition: dupolynomial.h:381
ExpressionTree convertToExpressionTree() const
Convert this to an expression tree.
Definition: dupolynomial.h:1587
void NewtonDivisionQuotient(DenseUnivariatePolynomial< Field > &b, DenseUnivariatePolynomial< Field > &q, DenseUnivariatePolynomial< Field > &r, int l)
Fast Division (based on Modern Computer Algebra , Newton Iteration Chapter 9)
Definition: dupolynomial.h:1690
DenseUnivariatePolynomial< Field > lazyPseudoDivide(const DenseUnivariatePolynomial< Field > &b, Field *c, Field *d)
Lazy pseudo dividsion Return the quotient and itself becomes remainder e is the exact number of divis...
Definition: dupolynomial.h:1144
void setVariableName(const Symbol &x)
Set variable's name.
Definition: dupolynomial.h:247
DenseUnivariatePolynomial< Field > integrate() const
Compute the integral with constant of integration 0.
Definition: dupolynomial.h:1357