![]() |
My Project
UNKNOWN_GIT_VERSION
|
This file implements functions for fast multiplication and division with remainder. More...
#include "debug.h"
#include "config.h"
#include "canonicalform.h"
#include "facMul.h"
#include "cf_util.h"
#include "templates/ftmpl_functions.h"
#include <NTL/lzz_pEX.h>
#include "NTLconvert.h"
#include "FLINTconvert.h"
Go to the source code of this file.
This file implements functions for fast multiplication and division with remainder.
Nomenclature rules: kronSub* -> plain Kronecker substitution reverseSubst* -> reverse Kronecker substitution kronSubRecipro* -> reciprocal Kronecker substitution as described in D. Harvey "Faster polynomial multiplication via multipoint Kronecker substitution"
Definition in file facMul.cc.
CanonicalForm divFLINTQ | ( | const CanonicalForm & | F, |
const CanonicalForm & | G | ||
) |
Definition at line 170 of file facMul.cc.
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 850 of file facMul.cc.
void 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 3583 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 3516 of file facMul.cc.
|
inlinestatic |
Definition at line 3376 of file facMul.cc.
|
inlinestatic |
Definition at line 3447 of file facMul.cc.
void kronSubFp | ( | nmod_poly_t | result, |
const CanonicalForm & | A, | ||
int | d | ||
) |
void kronSubFq | ( | fq_nmod_poly_t | result, |
const CanonicalForm & | A, | ||
int | d, | ||
const fq_nmod_ctx_t | fq_con | ||
) |
Definition at line 1138 of file facMul.cc.
void kronSubQa | ( | fmpz_poly_t | result, |
const CanonicalForm & | A, | ||
int | d | ||
) |
Definition at line 42 of file facMul.cc.
void kronSubQa | ( | fmpz_poly_t | result, |
const CanonicalForm & | A, | ||
int | d1, | ||
int | d2 | ||
) |
Definition at line 1220 of file facMul.cc.
void kronSubReciproFp | ( | nmod_poly_t | subA1, |
nmod_poly_t | subA2, | ||
const CanonicalForm & | A, | ||
int | d | ||
) |
void kronSubReciproFq | ( | fq_nmod_poly_t | subA1, |
fq_nmod_poly_t | subA2, | ||
const CanonicalForm & | A, | ||
int | d, | ||
const fq_nmod_ctx_t | fq_con | ||
) |
Definition at line 1296 of file facMul.cc.
void kronSubReciproQ | ( | fmpz_poly_t | subA1, |
fmpz_poly_t | subA2, | ||
const CanonicalForm & | A, | ||
int | d | ||
) |
Definition at line 1341 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 |
Definition at line 2939 of file facMul.cc.
CanonicalForm modFLINTQ | ( | const CanonicalForm & | F, |
const CanonicalForm & | G | ||
) |
Definition at line 188 of file facMul.cc.
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 676 of file facMul.cc.
CanonicalForm mulFLINTQ | ( | const CanonicalForm & | F, |
const CanonicalForm & | G | ||
) |
Definition at line 129 of file facMul.cc.
CanonicalForm mulFLINTQa | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const Variable & | alpha | ||
) |
Definition at line 99 of file facMul.cc.
CanonicalForm mulFLINTQaTrunc | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const Variable & | alpha, | ||
int | m | ||
) |
Definition at line 206 of file facMul.cc.
CanonicalForm mulFLINTQTrunc | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
int | m | ||
) |
Definition at line 237 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 2947 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 2853 of file facMul.cc.
CanonicalForm mulMod2FLINTFp | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const CanonicalForm & | M | ||
) |
Definition at line 1995 of file facMul.cc.
CanonicalForm mulMod2FLINTFpReci | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const CanonicalForm & | M | ||
) |
Definition at line 1957 of file facMul.cc.
CanonicalForm mulMod2FLINTFq | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const CanonicalForm & | M, | ||
const Variable & | alpha, | ||
const fq_nmod_ctx_t | fq_con | ||
) |
Definition at line 2069 of file facMul.cc.
CanonicalForm mulMod2FLINTFqReci | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const CanonicalForm & | M, | ||
const Variable & | alpha, | ||
const fq_nmod_ctx_t | fq_con | ||
) |
Definition at line 2027 of file facMul.cc.
CanonicalForm mulMod2FLINTQ | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const CanonicalForm & | M | ||
) |
Definition at line 2139 of file facMul.cc.
CanonicalForm mulMod2FLINTQa | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const CanonicalForm & | M | ||
) |
Definition at line 2199 of file facMul.cc.
CanonicalForm mulMod2FLINTQReci | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const CanonicalForm & | M | ||
) |
Definition at line 2102 of file facMul.cc.
CanonicalForm mulMod2NTLFq | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const CanonicalForm & | M | ||
) |
Definition at line 2793 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 407 of file facMul.cc.
void newtonDiv | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
CanonicalForm & | Q | ||
) |
Definition at line 376 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 3180 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 342 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 3259 of file facMul.cc.
CanonicalForm newtonInverse | ( | const CanonicalForm & | F, |
const int | n, | ||
const Variable & | x | ||
) |
Definition at line 287 of file facMul.cc.
CanonicalForm newtonInverse | ( | const CanonicalForm & | F, |
const int | n, | ||
const CanonicalForm & | M | ||
) |
Definition at line 3125 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 3047 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 3074 of file facMul.cc.
CanonicalForm reverse | ( | const CanonicalForm & | F, |
int | d | ||
) |
Definition at line 3101 of file facMul.cc.
CanonicalForm reverseSubstFp | ( | const nmod_poly_t | F, |
int | d | ||
) |
Definition at line 1921 of file facMul.cc.
CanonicalForm reverseSubstFq | ( | const fq_nmod_poly_t | F, |
int | d, | ||
const Variable & | alpha, | ||
const fq_nmod_ctx_t | fq_con | ||
) |
Definition at line 1886 of file facMul.cc.
CanonicalForm reverseSubstQ | ( | const fmpz_poly_t | F, |
int | d | ||
) |
Definition at line 1366 of file facMul.cc.
CanonicalForm reverseSubstQa | ( | const fmpz_poly_t | F, |
int | d, | ||
const Variable & | x, | ||
const Variable & | alpha, | ||
const CanonicalForm & | den | ||
) |
Definition at line 62 of file facMul.cc.
CanonicalForm reverseSubstQa | ( | const fmpz_poly_t | F, |
int | d1, | ||
int | d2, | ||
const Variable & | alpha, | ||
const fmpq_poly_t | mipo | ||
) |
Definition at line 1472 of file facMul.cc.
CanonicalForm reverseSubstReciproFp | ( | const nmod_poly_t | F, |
const nmod_poly_t | G, | ||
int | d, | ||
int | k | ||
) |
Definition at line 1529 of file facMul.cc.
CanonicalForm reverseSubstReciproFq | ( | const fq_nmod_poly_t | F, |
const fq_nmod_poly_t | G, | ||
int | d, | ||
int | k, | ||
const Variable & | alpha, | ||
const fq_nmod_ctx_t | fq_con | ||
) |
Definition at line 1648 of file facMul.cc.
CanonicalForm reverseSubstReciproQ | ( | const fmpz_poly_t | F, |
const fmpz_poly_t | G, | ||
int | d, | ||
int | k | ||
) |
Definition at line 1752 of file facMul.cc.
Definition at line 3336 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 3626 of file facMul.cc.
CanonicalForm uniReverse | ( | const CanonicalForm & | F, |
int | d, | ||
const Variable & | x | ||
) |
Definition at line 270 of file facMul.cc.