carl::DiophantineEquations< Integer > Class Template Reference

Includes the algorithms 6.2 and 6.3 from the book Algorithms for Computer Algebra by Geddes, Czaper, Labahn. More...

#include <MultivariateHensel.h>

Collaboration diagram for carl::DiophantineEquations< Integer >:

Public Member Functions
	DiophantineEquations (unsigned p, unsigned k)
std::vector< Polynomial >	solveMultivariateDiophantine (const std::vector< Polynomial > &a, const MultiPoly &c, const std::map< Variable, GFNumber< Integer >> &I, unsigned d) const
	Solve in the domain Z_(p^k)[x_!,...,x_v] the multivariate polynomial diophantine equation sigma_1 * b_1 + ... More...
std::vector< Polynomial >	univariateDiophantine (const std::vector< Polynomial > &a, Variable::Arg x, unsigned m) const
	Solve in Z_(p^k)[x] the univariate polynomial Diophantine equation: s_1 x b_1 + ... More...

Private Types
typedef UnivariatePolynomial< GFNumber< Integer > >	Polynomial
typedef MultivariatePolynomial< GFNumber< Integer > >	MultiPoly

Private Member Functions
std::vector< Polynomial >	MultiTermEEAlift (const std::vector< Polynomial > &a) const
std::vector< Polynomial >	EEAlift (Polynomial a, Polynomial b) const
	EEAlift computes s,t such that s*a + tb == 1 (mod p^k) with deg(s) < deg(b) and deg(t) < deg(a). More...

Private Attributes
const GaloisField< Integer > *	mGf_pk
const GaloisField< Integer > *	mGf_p

Detailed Description

template<typename Integer>
class carl::DiophantineEquations< Integer >

Includes the algorithms 6.2 and 6.3 from the book Algorithms for Computer Algebra by Geddes, Czaper, Labahn.

The Algorithms are used to computer the Multivariate GCD.

Definition at line 25 of file MultivariateHensel.h.

Member Typedef Documentation

MultiPoly

template<typename Integer >

typedef MultivariatePolynomial<GFNumber<Integer> > carl::DiophantineEquations< Integer >::MultiPoly

private

Definition at line 28 of file MultivariateHensel.h.

Polynomial

template<typename Integer >

typedef UnivariatePolynomial<GFNumber<Integer> > carl::DiophantineEquations< Integer >::Polynomial

private

Definition at line 27 of file MultivariateHensel.h.

Constructor & Destructor Documentation

DiophantineEquations()

template<typename Integer >

carl::DiophantineEquations< Integer >::DiophantineEquations ( unsigned  p, unsigned  k  )

inline

Definition at line 33 of file MultivariateHensel.h.

Member Function Documentation

EEAlift()

template<typename Integer >

std::vector<Polynomial> carl::DiophantineEquations< Integer >::EEAlift ( Polynomial  a, Polynomial  b  ) const

inlineprivate

EEAlift computes s,t such that s*a + tb == 1 (mod p^k) with deg(s) < deg(b) and deg(t) < deg(a).

Assumption GCD(a mod p, b mod p) = 1 in Z_p[x]

Parameters

a	Polynomial in Z_p^k[x]
b	Polynomial in Z_p^k[x]

Returns

Definition at line 200 of file MultivariateHensel.h.

Here is the call graph for this function:

Here is the caller graph for this function:

MultiTermEEAlift()

template<typename Integer >

std::vector<Polynomial> carl::DiophantineEquations< Integer >::MultiTermEEAlift ( const std::vector< Polynomial > &  a ) const

inlineprivate

Definition at line 164 of file MultivariateHensel.h.

Here is the call graph for this function:

Here is the caller graph for this function:

solveMultivariateDiophantine()

template<typename Integer >

std::vector<Polynomial> carl::DiophantineEquations< Integer >::solveMultivariateDiophantine ( const std::vector< Polynomial > &  a, const MultiPoly &  c, const std::map< Variable, GFNumber< Integer >> &  I, unsigned  d  ) const

inline

Solve in the domain Z_(p^k)[x_!,...,x_v] the multivariate polynomial diophantine equation sigma_1 * b_1 + ...

sigma_r * b_r = c (mod <I^(d+1), p^k>) where, in terms of the given list of polynomials a_1,...,a_r the polynomials b_i, i = 1,...,r, are defined by: b_i = a_1 * ... * a_(i-1) * a_(i+1) * ... * a_r. The unique solution sigma_i, i = 1,...,r, will be computed such that degree(sigma_i,x_i) < degree(a_i,x_1).

Conditions: (1) p must not divide lcoeff(a_i mod I), i = 1,...,r; (2) A_i mod <I,p>, i = 1,...,r, must be pairwise relatively prime in Z_p[x_1]; (3) degree(c,x_1) < sum(degree(a_i,x_1), i = 1,...,r)

The prime integer p and the positive integer k must bei specified in the constructor.

Parameters

a	A list a of r > 1 polynomials in the domain Z_(p^k)[x_1,...,x_v].
c	A polynomial c from Z_(p^k)[x_1,...,x_v].
I	A list of equations [x_2 = alpha_2,...,x_v = alpha_v].
d	A nonnegative integer d specifying the maximum total degree with respect to x_2,...,x_v of the desired result.

Returns

The list sigma = [sigma_1,...,sigma_r].

Todo:

implement

Definition at line 65 of file MultivariateHensel.h.

Here is the call graph for this function:

Here is the caller graph for this function:

univariateDiophantine()

template<typename Integer >

std::vector<Polynomial> carl::DiophantineEquations< Integer >::univariateDiophantine ( const std::vector< Polynomial > &  a, Variable::Arg  x, unsigned  m  ) const

inline

Solve in Z_(p^k)[x] the univariate polynomial Diophantine equation: s_1 x b_1 + ...

s_r x b_r === x^m (mod p^k) where in terms of the given list a: [a_1, ... a_r] the polynomials b_i for i = 1...r are defined by: b_i = a_1 x ... x a_{i-1} x a_{i+1} x ... x a_r The unique solution s_1,... s_r, will be computed such that deg(s_i) < deg(a_i).

Definition at line 139 of file MultivariateHensel.h.

Here is the call graph for this function:

Field Documentation

mGf_p

template<typename Integer >

const GaloisField<Integer>* carl::DiophantineEquations< Integer >::mGf_p

private

Definition at line 30 of file MultivariateHensel.h.

mGf_pk

template<typename Integer >

const GaloisField<Integer>* carl::DiophantineEquations< Integer >::mGf_pk

private

Definition at line 29 of file MultivariateHensel.h.

---

The documentation for this class was generated from the following file:

• carl-arith/poly/umvpoly/functions/MultivariateHensel.h