My Project
|
This file defines functions for fast multiplication and division with remainder. More...
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... | |
This file defines functions for fast multiplication and division with remainder.
Definition in file facMul.h.
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
[in] | F | a univariate poly |
[in] | G | a univariate poly |
[in] | b | coeff bound |
Definition at line 936 of file facMul.cc.
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".
[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.
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".
[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 mod | ( | const CanonicalForm & | F, |
const CFList & | M | ||
) |
reduce F modulo elements in M.
[in] | F | compressed polynomial |
[in] | M | list containing only univariate polynomials |
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
[in] | F | a univariate poly |
[in] | G | a univariate poly |
[in] | b | coeff bound |
Definition at line 731 of file facMul.cc.
CanonicalForm mulMod | ( | const CanonicalForm & | A, |
const CanonicalForm & | B, | ||
const CFList & | MOD | ||
) |
Karatsuba style modular multiplication for multivariate polynomials.
[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.
CanonicalForm mulMod2 | ( | const CanonicalForm & | A, |
const CanonicalForm & | B, | ||
const CanonicalForm & | M | ||
) |
Karatsuba style modular multiplication for bivariate polynomials.
[in] | A | bivariate, compressed polynomial |
[in] | B | bivariate, compressed polynomial |
[in] | M | power of Variable (2) |
Definition at line 2986 of file facMul.cc.
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).
[in] | F | a univariate poly |
[in] | G | a univariate poly |
[in] | b | coeff bound |
Definition at line 411 of file facMul.cc.
CanonicalForm newtonDiv | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const CanonicalForm & | M | ||
) |
division of F by G wrt Variable (1) modulo M using Newton inversion
[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.
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)
[in] | F | univariate poly |
[in] | G | univariate poly |
[in,out] | Q | quotient |
[in,out] | R | remainder |
Definition at line 346 of file facMul.cc.
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
[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 prodMod | ( | const CFList & | L, |
const CanonicalForm & | M | ||
) |
product of all elements in L modulo M via divide-and-conquer.
[in] | L | contains only bivariate, compressed polynomials |
[in] | M | power of Variable (2) |
Definition at line 3180 of file facMul.cc.
CanonicalForm prodMod | ( | const CFList & | L, |
const CFList & | M | ||
) |
product of all elements in L modulo M via divide-and-conquer.
[in] | L | contains multivariate, compressed polynomials |
[in] | M | contains only powers of Variables |
Definition at line 3207 of file facMul.cc.
bool uniFdivides | ( | const CanonicalForm & | A, |
const CanonicalForm & | B | ||
) |
divisibility test for univariate polys
[in] | A | univariate poly |
[in] | B | univariate poly |
Definition at line 3759 of file facMul.cc.