Classes | |
class | CDFT_base0 |
class | CDFT_base |
class | CDFT |
class | CDFT_chinrem |
class | TTempPolynom |
a tiny helper class for temporary arrays mpz_t[] in C++ More... | |
Typedefs | |
typedef CDFT_chinrem | TDFT |
typedef TDFT * | PDFT |
typedef mpz_t * | TPolynom |
typedef const mpz_t * | TconstPolynom |
Functions | |
bool | dft_mul_is_recommended (const int k1, const int k2) |
bool | dft_square_is_recommended (const int k) |
const PDFT | get_dft (const unsigned int n, const mpz_t m) |
void | clear_dft_tempmemory () |
void | print (const TconstPolynom P, int k) |
void | eval (mpz_t res, const TconstPolynom P, const int k, const mpz_t x, const mpz_t m) |
template<typename T> | |
T | ld (T n) |
int | classic_mul (const TPolynom __restrict__ Pr, const int kr, const TconstPolynom P1, const int k1, const TconstPolynom P2, const int k2) |
int | classic_mul (const TPolynom __restrict__ Pr, const int kr, const TconstPolynom P1, const int k1, const TconstPolynom P2, const int k2, const mpz_t m) |
static int | square_rek (const TPolynom R, const int kR, const TconstPolynom P, const int k, const TPolynom temp) |
static int | mul_rek (const TPolynom R, const int kR, const TconstPolynom P1, const int k1, const TconstPolynom P2, const int k2, const TPolynom temp) |
int | monic_mul (const TPolynom R, const int kR, const TconstPolynom P1, int k1, const TconstPolynom P2, int k2, const mpz_t m) |
int | monic_square (const TPolynom R, const int kR, const TconstPolynom P, int k, const mpz_t m) |
int | square (const TPolynom R, const int kR, const TconstPolynom P, const int k, const mpz_t m) |
int | square (const TPolynom R, const int kR, const TconstPolynom P, const int k) |
int | mul (const TPolynom R, const int kR, TconstPolynom P1, int k1, TconstPolynom P2, int k2, const mpz_t m) |
int | mul (const TPolynom R, const int kR, TconstPolynom P1, int k1, TconstPolynom P2, int k2) |
void | reciprocal2p1 (TPolynom R, int &kR, const TconstPolynom f, const int np1, const mpz_t m) |
void | reciprocal2 (TPolynom R, int &kR, const TconstPolynom P, const int k, const mpz_t m) |
void | reciprocal (TPolynom R, int &kR, const TconstPolynom P, const int k, const mpz_t m, const unsigned int scale) |
void | classic_div (TPolynom Q, int &kQ, TPolynom R, int &kR, const TconstPolynom P1, int k1, const TconstPolynom P2, int k2, const mpz_t m) |
void | classic_mod (TPolynom R, int &kR, const TconstPolynom P1, int k1, const TconstPolynom P2, int k2, const mpz_t m) |
void | div (TPolynom Q, int &kQ, const TconstPolynom P1, const int k1, const TconstPolynom P2, const int k2, const mpz_t m) |
void | mod (TPolynom R, int &kR, const TconstPolynom P1, int k1, const TconstPolynom P2, int k2, const mpz_t m) |
static void | multipoint_eval_rek (const TPolynom *R, const TconstPolynom P, const int k, TPolynom *A, const int h, const mpz_t m, mpz_t *&res, int *const pos, const int *const step, const int *const stop) |
void | multipoint_eval (mpz_t *res, const TconstPolynom P, const int k, const mpz_t *const array_of_arguments, const int size, const mpz_t m) |
int | construct_polynomial_from_roots (TPolynom &res, const mpz_t *const roots_array, const int size, const mpz_t m) |
int | classic_mul (const TPolynom Pr, const int kr, const TconstPolynom P1, const int k1, const TconstPolynom P2, const int k2) |
int | classic_mul (const TPolynom Pr, const int kr, const TconstPolynom P1, const int k1, const TconstPolynom P2, const int k2, const mpz_t m) |
typedef TDFT* polynomial::PDFT |
typedef const mpz_t* polynomial::TconstPolynom |
Definition at line 28 of file polynomial.H.
typedef CDFT_chinrem polynomial::TDFT |
typedef mpz_t* polynomial::TPolynom |
Definition at line 27 of file polynomial.H.
void polynomial::classic_div | ( | TPolynom | Q, | |
int & | kQ, | |||
TPolynom | R, | |||
int & | kR, | |||
const TconstPolynom | P1, | |||
int | k1, | |||
const TconstPolynom | P2, | |||
int | k2, | |||
const mpz_t | m | |||
) |
Q | result polynomial (quotient) | |
kQ | size of result quotient polynomial | |
R | result polynomial (remainder) | |
kR | size of result remainder polynomial | |
P1 | dividend polynomial | |
k1 | size of P1 | |
P2 | divisor polynomial | |
k2 | size of P2 | |
m | the result will be reduced modulo m |
&Q
, &R
, &P1
and &P2
should be disjoint from each otherDefinition at line 790 of file polynomial.cc.
References cerr, cout, exit(), MARK, mpz_clear(), mpz_cmp_ui(), mpz_init(), mpz_invert(), mpz_mod(), mpz_mul(), mpz_set(), mpz_set_ui(), mpz_sub(), and print().
void polynomial::classic_mod | ( | TPolynom | R, | |
int & | kR, | |||
const TconstPolynom | P1, | |||
int | k1, | |||
const TconstPolynom | P2, | |||
int | k2, | |||
const mpz_t | m | |||
) |
R | result polynomial (remainder) | |
kR | size of result polynomial | |
P1 | dividend polynomial | |
k1 | size of P1 | |
P2 | divisor polynomial | |
k2 | size of P2 | |
m | the result will be reduced modulo m |
&Pr
should be disjoint from &P1
and &P2
Definition at line 866 of file polynomial.cc.
References cerr, cout, exit(), mpz_clear(), mpz_cmp_ui(), mpz_init(), mpz_invert(), mpz_mod(), mpz_mul(), mpz_set(), mpz_set_ui(), mpz_submul(), and print().
Referenced by mod().
int polynomial::classic_mul | ( | const TPolynom | Pr, | |
const int | kr, | |||
const TconstPolynom | P1, | |||
const int | k1, | |||
const TconstPolynom | P2, | |||
const int | k2, | |||
const mpz_t | m | |||
) |
Pr | result polynomial | |
kr | size of result polynomial | |
P1 | first multiplicator polynomial | |
k1 | size of P1 | |
P2 | second multiplicator polynomial | |
k2 | size of P2 | |
m | the result will be reduced modulo m |
Pr
&Pr
must be disjoint from &P1
and &P2
int polynomial::classic_mul | ( | const TPolynom | Pr, | |
const int | kr, | |||
const TconstPolynom | P1, | |||
const int | k1, | |||
const TconstPolynom | P2, | |||
const int | k2 | |||
) |
Pr | result polynomial | |
kr | size of result polynomial | |
P1 | first multiplicator polynomial | |
k1 | size of P1 | |
P2 | second multiplicator polynomial | |
k2 | size of P2 |
Pr
&Pr
must be disjoint from &P1
and &P2
int polynomial::classic_mul | ( | const TPolynom __restrict__ | Pr, | |
const int | kr, | |||
const TconstPolynom | P1, | |||
const int | k1, | |||
const TconstPolynom | P2, | |||
const int | k2, | |||
const mpz_t | m | |||
) |
Definition at line 122 of file polynomial.cc.
References cerr, endl(), mpz_addmul(), mpz_mod(), and mpz_set_ui().
int polynomial::classic_mul | ( | const TPolynom __restrict__ | Pr, | |
const int | kr, | |||
const TconstPolynom | P1, | |||
const int | k1, | |||
const TconstPolynom | P2, | |||
const int | k2 | |||
) |
Definition at line 104 of file polynomial.cc.
References cerr, endl(), mpz_addmul(), and mpz_set_ui().
Referenced by mul().
void polynomial::clear_dft_tempmemory | ( | ) |
int polynomial::construct_polynomial_from_roots | ( | TPolynom & | res, | |
const mpz_t *const | roots_array, | |||
const int | size, | |||
const mpz_t | m | |||
) |
res | result polynomial (coefficients) | |
roots_array | roots of polynomial | |
size | number of roots | |
m | the results will be reduced modulo m |
res
must be set to NULL when function is called Definition at line 1277 of file polynomial.cc.
References cerr, cout, exit(), monic_mul(), mpz_clear(), mpz_cmp_ui(), mpz_init2(), mpz_init_set(), mpz_init_set_ui(), mpz_neg(), mpz_set(), and mpz_sizeinbase().
Referenced by elliptic_curves::go(), and polphi_template().
bool polynomial::dft_mul_is_recommended | ( | const int | k1, | |
const int | k2 | |||
) | [inline] |
bool polynomial::dft_square_is_recommended | ( | const int | k | ) | [inline] |
void polynomial::div | ( | TPolynom | Q, | |
int & | kQ, | |||
const TconstPolynom | P1, | |||
const int | k1, | |||
const TconstPolynom | P2, | |||
const int | k2, | |||
const mpz_t | m | |||
) |
Q | result polynomial (quotient) | |
kQ | size of result polynomial | |
P1 | dividend polynomial | |
k1 | size of P1 | |
P2 | divisor polynomial | |
k2 | size of P2 | |
m | the result will be reduced modulo m |
&Pr
should be disjoint from &P1
and &P2
Definition at line 945 of file polynomial.cc.
References cerr, cout, exit(), mpz_cmp_ui(), mpz_invert(), mpz_mod(), mpz_mul(), mpz_set(), mul(), print(), and reciprocal().
Referenced by mod().
void polynomial::eval | ( | mpz_t | res, | |
const TconstPolynom | P, | |||
const int | k, | |||
const mpz_t | x, | |||
const mpz_t | m | |||
) |
res | result value | |
P | polynomial to evaluate | |
k | size of P | |
x | point at which P is to evaluate | |
m | result will be reduced modulo m |
P
res
= P(x) mod m Definition at line 67 of file polynomial.cc.
References mpz_add(), mpz_clear(), mpz_init_set(), mpz_mod(), mpz_mul(), and mpz_set().
Referenced by do_check().
const PDFT polynomial::get_dft | ( | const unsigned int | n, | |
const mpz_t | m | |||
) |
Definition at line 1056 of file dft.cc.
References cout, endl(), polynomial::CDFT_chinrem::get_N(), polynomial::CDFT_base0::max_size, and mpz_cmp().
Referenced by monic_mul(), monic_square(), mul(), and square().
T polynomial::ld | ( | T | n | ) | [inline] |
Definition at line 82 of file polynomial.cc.
void polynomial::mod | ( | TPolynom | R, | |
int & | kR, | |||
const TconstPolynom | P1, | |||
int | k1, | |||
const TconstPolynom | P2, | |||
int | k2, | |||
const mpz_t | m | |||
) |
R | result polynomial (remainder) | |
kR | size of result polynomial | |
P1 | dividend polynomial | |
k1 | size of P1 | |
P2 | divisor polynomial | |
k2 | size of P2 | |
m | the result will be reduced modulo m |
&Pr
should be disjoint from &P1
and &P2
Definition at line 1033 of file polynomial.cc.
References cerr, classic_mod(), cout, div(), mpz_cmp(), mpz_cmp_ui(), mpz_mod(), mpz_set(), mpz_sub(), mul(), and print().
Referenced by numtheory::normalized_signed_mod().
int polynomial::monic_mul | ( | const TPolynom | R, | |
const int | kR, | |||
const TconstPolynom | P1, | |||
int | k1, | |||
const TconstPolynom | P2, | |||
int | k2, | |||
const mpz_t | m | |||
) |
Definition at line 498 of file polynomial.cc.
References cerr, cout, dft_mul_is_recommended(), endl(), exit(), get_dft(), MARK, mpz_add(), mpz_cmp_ui(), mpz_mod(), mpz_mul(), mpz_set_ui(), mul(), polynomial::CDFT_chinrem::mul(), and print().
Referenced by construct_polynomial_from_roots(), and mul().
int polynomial::monic_square | ( | const TPolynom | R, | |
const int | kR, | |||
const TconstPolynom | P, | |||
int | k, | |||
const mpz_t | m | |||
) |
Definition at line 568 of file polynomial.cc.
References cerr, cout, dft_square_is_recommended(), endl(), exit(), get_dft(), mpz_add(), mpz_addmul_ui(), mpz_cmp_ui(), mpz_mod(), mpz_mul(), mpz_set_ui(), print(), square(), and polynomial::CDFT_chinrem::square().
int polynomial::mul | ( | const TPolynom | R, | |
const int | kR, | |||
TconstPolynom | P1, | |||
int | k1, | |||
TconstPolynom | P2, | |||
int | k2 | |||
) |
R | result polynomial | |
kR | size of result polynomial | |
P1 | first multiplicator polynomial | |
k1 | size of P1 | |
P2 | second multiplicator polynomial | |
k2 | size of P2 |
R
&R
must be disjoint from &P1
and &P2
Definition at line 461 of file polynomial.cc.
References cerr, classic_mul(), cout, endl(), MARK, mul_rek(), and std::swap().
int polynomial::mul | ( | const TPolynom | R, | |
const int | kR, | |||
TconstPolynom | P1, | |||
int | k1, | |||
TconstPolynom | P2, | |||
int | k2, | |||
const mpz_t | m | |||
) |
R | result polynomial | |
kR | size of result polynomial | |
P1 | first multiplicator polynomial | |
k1 | size of P1 | |
P2 | second multiplicator polynomial | |
k2 | size of P2 | |
m | the result will be reduced modulo m |
R
&R
must be disjoint from &P1
and &P2
Definition at line 404 of file polynomial.cc.
References cerr, classic_mul(), cout, dft_mul_is_recommended(), endl(), get_dft(), MARK, monic_mul(), mpz_cmp_ui(), mpz_mod(), mpz_sizeinbase(), mul_rek(), polynomial::CDFT_chinrem::mulmod(), and std::swap().
Referenced by div(), mod(), monic_mul(), reciprocal2(), and reciprocal2p1().
static int polynomial::mul_rek | ( | const TPolynom | R, | |
const int | kR, | |||
const TconstPolynom | P1, | |||
const int | k1, | |||
const TconstPolynom | P2, | |||
const int | k2, | |||
const TPolynom | temp | |||
) | [static] |
Definition at line 205 of file polynomial.cc.
References cout, endl(), MAX(), MIN(), mpz_add(), mpz_mul(), mpz_set(), mpz_set_ui(), mpz_sub(), and mpz_tdiv_q_2exp().
Referenced by mul().
void polynomial::multipoint_eval | ( | mpz_t * | res, | |
const TconstPolynom | P, | |||
const int | k, | |||
const mpz_t *const | array_of_arguments, | |||
const int | size, | |||
const mpz_t | m | |||
) |
res | result coefficients | |
P | polynomial to evaluate | |
k | size of P | |
array_of_arguments | points at which P will be evaluated | |
size | number of points to evaluate | |
m | the results will be reduced modulo m |
Definition at line 1166 of file polynomial.cc.
Referenced by do_check(), elliptic_curves::go(), performance_check(), and polphi_template().
static void polynomial::multipoint_eval_rek | ( | const TPolynom * | R, | |
const TconstPolynom | P, | |||
const int | k, | |||
TPolynom * | A, | |||
const int | h, | |||
const mpz_t | m, | |||
mpz_t *& | res, | |||
int *const | pos, | |||
const int *const | step, | |||
const int *const | stop | |||
) | [static] |
Definition at line 1134 of file polynomial.cc.
void polynomial::print | ( | const TconstPolynom | P, | |
int | k | |||
) |
P | polynomial | |
k | size of polynomial (number of coefficients) |
Definition at line 55 of file polynomial.cc.
References cout, and mpz_out_str().
Referenced by classic_div(), classic_mod(), div(), mod(), monic_mul(), monic_square(), and reciprocal2().
void polynomial::reciprocal | ( | TPolynom | R, | |
int & | kR, | |||
const TconstPolynom | P, | |||
const int | k, | |||
const mpz_t | m, | |||
const unsigned int | scale = 0 | |||
) |
R | result polynomial | |
kR | size of result polynomial | |
P | argument polynomial | |
k | size of P | |
m | the result will be reduced modulo m | |
scale | (optional, with default 0, no scale) |
P
will be multiplied (shifted) by x^(scale) Definition at line 732 of file polynomial.cc.
Referenced by StaticFactorbase::compute_StaticFactorbase(), and div().
void polynomial::reciprocal2 | ( | TPolynom | R, | |
int & | kR, | |||
const TconstPolynom | P, | |||
const int | k, | |||
const mpz_t | m | |||
) |
Definition at line 686 of file polynomial.cc.
References cerr, cin, cout, endl(), mpz_cmp_ui(), mpz_invert(), mpz_mod(), mpz_mul_ui(), mpz_set_ui(), mpz_sub(), mul(), print(), and square().
void polynomial::reciprocal2p1 | ( | TPolynom | R, | |
int & | kR, | |||
const TconstPolynom | f, | |||
const int | np1, | |||
const mpz_t | m | |||
) |
Definition at line 641 of file polynomial.cc.
References mpz_clear(), mpz_init(), mpz_invert(), mpz_mod(), mpz_mul(), mpz_mul_2exp(), mpz_neg(), mpz_set(), mpz_set_ui(), mpz_sub(), mul(), n, and square().
int polynomial::square | ( | const TPolynom | R, | |
const int | kR, | |||
const TconstPolynom | P, | |||
const int | k | |||
) |
R | result polynomial | |
kR | size of result polynomial | |
P | first multiplicator polynomial | |
k | size of P1 |
R
&R
must be disjoint from &P
Definition at line 367 of file polynomial.cc.
References cerr, cout, dft_square_is_recommended(), endl(), get_dft(), MARK, mpz_cmp_ui(), polynomial::CDFT_chinrem::square(), and square_rek().
Referenced by determine_best_MPQS_Multiplier().
int polynomial::square | ( | const TPolynom | R, | |
const int | kR, | |||
const TconstPolynom | P, | |||
const int | k, | |||
const mpz_t | m | |||
) |
R | result polynomial | |
kR | size of result polynomial | |
P | multiplicator polynomial | |
k | size of P | |
m | the result will be reduced modulo m |
R
&R
must be disjoint from &P
Definition at line 332 of file polynomial.cc.
References cerr, dft_square_is_recommended(), endl(), get_dft(), MARK, mpz_mod(), mpz_sizeinbase(), square_rek(), and polynomial::CDFT_chinrem::squaremod().
Referenced by monic_square(), reciprocal2(), and reciprocal2p1().
static int polynomial::square_rek | ( | const TPolynom | R, | |
const int | kR, | |||
const TconstPolynom | P, | |||
const int | k, | |||
const TPolynom | temp | |||
) | [static] |
Definition at line 144 of file polynomial.cc.
References MAX(), mpz_add(), mpz_mul(), mpz_mul_2exp(), mpz_set(), mpz_set_ui(), and mpz_sub().
Referenced by square().