Qsieve: polynomial Namespace Reference

Definition at line 1020 of file dft.cc.

typedef const mpz_t* polynomial::TconstPolynom

Definition at line 28 of file polynomial.H.

Definition at line 1019 of file dft.cc.

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
	)

Parameters:

	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`

Remarks:

This function implements the classical division

complexity O(k1*k2)
use it only for small sized polynomials
&Q , &R , &P1 and &P2 should be disjoint from each other
this function is deprecated

Definition 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().

Here is the call graph for this function:

void polynomial::classic_mod	(	TPolynom	R,
		int &	kR,
		const TconstPolynom	P1,
		int	k1,
		const TconstPolynom	P2,
		int	k2,
		const mpz_t	m
	)

Parameters:

	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`

Remarks:

This function implements the classical division

complexity O(k1*k2)
use it only for small sized polynomials
&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().

Here is the call graph for this function:

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
	)

Parameters:

	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`

Returns:: size of the product polynomial Pr

Remarks:

This function implements the classical multiplication

complexity O(k1*k2)
use it only for small sized polynomials
&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
	)

Parameters:

	Pr	result polynomial
	kr	size of result polynomial
	P1	first multiplicator polynomial
	k1	size of `P1`
	P2	second multiplicator polynomial
	k2	size of `P2`

Returns:: size of the product polynomial Pr

Remarks:

This function implements the classical multiplication

complexity O(k1*k2)
use it only for small sized polynomials
&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().

Here is the call graph for this function:

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().

Here is the call graph for this function:

void polynomial::clear_dft_tempmemory ( )

Remarks:

When the discrete fast fourier transform is activated, then it will use some internal temporary memory, which can be safely released using this function.

Definition at line 1088 of file dft.cc.

Referenced by main().

int polynomial::construct_polynomial_from_roots	(	TPolynom &	res,
		const mpz_t *const	roots_array,
		const int	size,
		const mpz_t	m
	)

Parameters:

	res	result polynomial (coefficients)
	roots_array	roots of polynomial
	size	number of roots
	m	the results will be reduced modulo `m`

Returns:: size of result polynomial

Remarks:

This function implements fast evaluation schemes

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().

Here is the call graph for this function:

bool polynomial::dft_mul_is_recommended	(	const int	k1,
		const int	k2
	)			`[inline]`

Definition at line 1024 of file dft.cc.

Referenced by monic_mul(), and mul().

bool polynomial::dft_square_is_recommended ( const int k ) [inline]

Definition at line 1033 of file dft.cc.

Referenced by monic_square(), and square().

void polynomial::div	(	TPolynom	Q,
		int &	kQ,
		const TconstPolynom	P1,
		const int	k1,
		const TconstPolynom	P2,
		const int	k2,
		const mpz_t	m
	)

Parameters:

	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`

Remarks:

This function implements division using newton method (using reciprocal polynomial)

complexity depends on fastest multiplication, should be O(max(k1,k2)*ld(max(k1,k2))
&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().

Here is the call graph for this function:

void polynomial::eval	(	mpz_t	res,
		const TconstPolynom	P,
		const int	k,
		const mpz_t	x,
		const mpz_t	m
	)

Parameters:

	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`

Remarks:

This function implements the horner scheme

use it only for single point evaluations of 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().

Here is the call graph for this function:

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().

Here is the call graph for this function:

template<typename T>

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
	)

Parameters:

	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`

Remarks:

This function implements division using newton method (using reciprocal polynomial)

complexity depends on fastest multiplication, should be O(max(k1,k2)*ld(max(k1,k2))
use it for medium and large sized polynomials
&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().

Here is the call graph for this function:

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().

Here is the call graph for this function:

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().

Here is the call graph for this function:

int polynomial::mul	(	const TPolynom	R,
		const int	kR,
		TconstPolynom	P1,
		int	k1,
		TconstPolynom	P2,
		int	k2
	)

Parameters:

	R	result polynomial
	kR	size of result polynomial
	P1	first multiplicator polynomial
	k1	size of `P1`
	P2	second multiplicator polynomial
	k2	size of `P2`

Returns:: size of the product polynomial R

Remarks:

This function implements the Karatsuba algorithms

complexity O(max(k1,k2)^1.59), Karatsuba
use it for medium and big sized polynomials
&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().

Here is the call graph for this function:

int polynomial::mul	(	const TPolynom	R,
		const int	kR,
		TconstPolynom	P1,
		int	k1,
		TconstPolynom	P2,
		int	k2,
		const mpz_t	m
	)

Parameters:

	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`

Returns:: size of the product polynomial R

Remarks:

This function implements the various multiplication algorithms

complexity O(max(k1,k2)^1.59), Karatsuba
complexity O((k1+k2)*ld(k1+k2)), dft & chinese remaindering
use it for medium and big sized polynomials
&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().

Here is the call graph for this function:

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().

Here is the call graph for this function:

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
	)

Parameters:

	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`

Remarks:

This function implements fast evaluation schemes

for medium and big size faster than horner evaluation

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
	)

Parameters:

	P	polynomial
	k	size of polynomial (number of coefficients)

Remarks:

This function prints the given polynomial to stdout.

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().

Here is the call graph for this function:

void polynomial::reciprocal	(	TPolynom	R,
		int &	kR,
		const TconstPolynom	P,
		const int	k,
		const mpz_t	m,
		const unsigned int	scale = `0`
	)

Parameters:

	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)

Remarks:

This function computes the reciprocal polynomial of R

The argument polynomial 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().

Here is the call graph for this function:

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().

Here is the call graph for this function:

int polynomial::square	(	const TPolynom	R,
		const int	kR,
		const TconstPolynom	P,
		const int	k
	)

Parameters:

	R	result polynomial
	kR	size of result polynomial
	P	first multiplicator polynomial
	k	size of `P1`

Returns:: size of the product polynomial R

Remarks:

This function implements the Karatsuba multiplication

complexity O(k^1.59)
&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().

Here is the call graph for this function:

int polynomial::square	(	const TPolynom	R,
		const int	kR,
		const TconstPolynom	P,
		const int	k,
		const mpz_t	m
	)

Parameters:

	R	result polynomial
	kR	size of result polynomial
	P	multiplicator polynomial
	k	size of `P`
	m	the result will be reduced modulo `m`

Returns:: size of the product polynomial R

Remarks:

This function implements the Karatsuba multiplication

complexity O(k^1.59)
&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().

Here is the call graph for this function:

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().

Here is the call graph for this function:

polynomial Namespace Reference

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation


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)