finite modulo-N arithmetic with polynomials of degree < M. More...
#include <vnl_finite.h>
Public Member Functions | |
vnl_finite_int_poly (vcl_vector< Scalar > const &p) | |
Creates a general finite_int_poly. | |
vnl_finite_int_poly (Scalar const &n) | |
Creates a degree 0 finite_int_poly. | |
vnl_finite_int_poly () | |
Default constructor. Creates a degree 0 finite_int_poly equal to 0. | |
vnl_finite_int_poly (Base const &x) | |
~vnl_finite_int_poly () | |
vcl_size_t | deg () const |
Formal degree of this polynomial. | |
int | degree () const |
Effective degree of this polynomial; equals -1 when this polynomial is 0. | |
Scalar | operator[] (unsigned int i) const |
Access to individual coefficients. | |
Base & | operator= (Base const &x) |
Assignment. | |
Base & | operator= (Scalar const &n) |
bool | operator== (Base const &x) const |
Comparison of finite int polys. | |
bool | operator!= (Base const &x) const |
bool | operator== (Scalar const &x) const |
bool | operator!= (Scalar const &x) const |
Base | operator- () const |
Unary minus - returns the additive inverse. | |
Base | operator+ () const |
Unary plus - returns the current polynomial. | |
bool | operator! () const |
Unary not - returns true if finite int poly is equal to zero. | |
Base & | operator+= (Base const &r) |
Plus&assign: replace lhs by lhs + rhs. | |
Base & | operator-= (Base const &r) |
Minus&assign: replace lhs by lhs - rhs. | |
Base & | operator*= (Scalar const &n) |
Scalar multiple of this. | |
unsigned int | additive_order () const |
The additive order of x is the smallest positive r such that r*x == 0. | |
Base & | operator*= (Base const &r) |
Multiply&assign: replace lhs by lhs * rhs, modulo the "modulo" polynomial. | |
unsigned int | multiplicative_order () const |
Return the multiplicative order of this polynomial. | |
Static Public Member Functions | |
static unsigned int | cardinality () |
The number of different finite_int polynomials of this type. | |
static vcl_vector< Scalar > & | modulo_polynomial (vcl_vector< Scalar > p=vcl_vector< Scalar >()) |
get/set the (irreducible) modulo polynomial of degree M. | |
static bool | is_field () |
Return true when this ring is a field. | |
static Base | smallest_generator () |
Return the smallest multiplicative generator of the units in this ring. | |
Private Types | |
typedef vnl_finite_int_poly< N, M > | Base |
typedef vnl_finite_int< N > | Scalar |
Private Member Functions | |
void | add_modulo_poly (unsigned int m, Scalar const &x) |
Add x to the i-th degree coefficient of val_, possibly reducing modulo the "modulo" poly. | |
Static Private Member Functions | |
static unsigned int | Ntothe (unsigned int m) |
Private Attributes | |
vcl_vector< Scalar > | val_ |
M-tuple (or degree M-1 polynomial) representing this. | |
Related Functions | |
(Note that these are not member functions.) | |
template<int N, int M> | |
vnl_finite_int_poly< N, M > | operator+ (vnl_finite_int_poly< N, M > const &r1, vnl_finite_int_poly< N, M > const &r2) |
Returns the sum of two finite int polynomials. | |
template<int N, int M> | |
vnl_finite_int_poly< N, M > | operator- (vnl_finite_int_poly< N, M > const &r1, vnl_finite_int_poly< N, M > const &r2) |
Returns the difference of two finite int polynomials. | |
template<int N, int M> | |
vnl_finite_int_poly< N, M > | operator* (vnl_finite_int_poly< N, M > const &r1, vnl_finite_int< N > const &r2) |
Returns a scalar multiple of a finite int polynomial. | |
template<int N, int M> | |
vnl_finite_int_poly< N, M > | operator* (vnl_finite_int< N > const &r2, vnl_finite_int_poly< N, M > const &r1) |
Returns a scalar multiple of a finite int polynomial. | |
template<int N, int M> | |
vnl_finite_int_poly< N, M > | operator* (vnl_finite_int_poly< N, M > const &r1, vnl_finite_int_poly< N, M > const &r2) |
Multiplies two finite int polynomials. | |
template<int N, int M> | |
vcl_ostream & | operator<< (vcl_ostream &s, vnl_finite_int_poly< N, M > const &r) |
formatted output. |
finite modulo-N arithmetic with polynomials of degree < M.
This class implements arithmetic with polynomials of degree < M over vnl_finite_int<N>. Multiplication is defined modulo a polynomial of degree M.
For N prime, and when the "modulo" polynomial is irreducible, vnl_finite_int_poly<N,M> implements the finite field GF(N^M).
Addition, subtraction and scalar multiplication are already defined without the presence of a "modulo" polynomial. Restricted to these operations, vnl_finite_int_poly<N,M> forms an M-dimensional vector space over vnl_finite_int<N>. The current implementation does not yet implement anything more than that.
Definition at line 422 of file vnl_finite.h.
typedef vnl_finite_int_poly<N,M> vnl_finite_int_poly< N, M >::Base [private] |
Definition at line 424 of file vnl_finite.h.
typedef vnl_finite_int<N> vnl_finite_int_poly< N, M >::Scalar [private] |
Definition at line 425 of file vnl_finite.h.
vnl_finite_int_poly< N, M >::vnl_finite_int_poly | ( | vcl_vector< Scalar > const & | p | ) | [inline] |
Creates a general finite_int_poly.
Definition at line 436 of file vnl_finite.h.
vnl_finite_int_poly< N, M >::vnl_finite_int_poly | ( | Scalar const & | n | ) | [inline] |
Creates a degree 0 finite_int_poly.
Definition at line 438 of file vnl_finite.h.
vnl_finite_int_poly< N, M >::vnl_finite_int_poly | ( | ) | [inline] |
Default constructor. Creates a degree 0 finite_int_poly equal to 0.
Definition at line 440 of file vnl_finite.h.
vnl_finite_int_poly< N, M >::vnl_finite_int_poly | ( | Base const & | x | ) | [inline] |
Definition at line 442 of file vnl_finite.h.
vnl_finite_int_poly< N, M >::~vnl_finite_int_poly | ( | ) | [inline] |
Definition at line 444 of file vnl_finite.h.
void vnl_finite_int_poly< N, M >::add_modulo_poly | ( | unsigned int | m, |
Scalar const & | x | ||
) | [inline, private] |
Add x to the i-th degree coefficient of val_, possibly reducing modulo the "modulo" poly.
Definition at line 569 of file vnl_finite.h.
unsigned int vnl_finite_int_poly< N, M >::additive_order | ( | ) | const [inline] |
The additive order of x is the smallest positive r such that r*x == 0.
Definition at line 501 of file vnl_finite.h.
static unsigned int vnl_finite_int_poly< N, M >::cardinality | ( | ) | [inline, static] |
The number of different finite_int polynomials of this type.
Definition at line 433 of file vnl_finite.h.
vcl_size_t vnl_finite_int_poly< N, M >::deg | ( | ) | const [inline] |
Formal degree of this polynomial.
Definition at line 447 of file vnl_finite.h.
int vnl_finite_int_poly< N, M >::degree | ( | ) | const [inline] |
Effective degree of this polynomial; equals -1 when this polynomial is 0.
Definition at line 450 of file vnl_finite.h.
static bool vnl_finite_int_poly< N, M >::is_field | ( | ) | [inline, static] |
Return true when this ring is a field.
Note that this requires that N is a prime, but that condition is not sufficient: also the "modulo" polynomial must be irreducible.
Definition at line 548 of file vnl_finite.h.
static vcl_vector<Scalar>& vnl_finite_int_poly< N, M >::modulo_polynomial | ( | vcl_vector< Scalar > | p = vcl_vector<Scalar>() | ) | [inline, static] |
get/set the (irreducible) modulo polynomial of degree M.
Note that this polynomial has to be set only once, i.e., once set, it applies to all vnl_finite_int_polys with the same N and M.
Definition at line 511 of file vnl_finite.h.
unsigned int vnl_finite_int_poly< N, M >::multiplicative_order | ( | ) | const [inline] |
Return the multiplicative order of this polynomial.
Definition at line 538 of file vnl_finite.h.
static unsigned int vnl_finite_int_poly< N, M >::Ntothe | ( | unsigned int | m | ) | [inline, static, private] |
Definition at line 430 of file vnl_finite.h.
bool vnl_finite_int_poly< N, M >::operator! | ( | ) | const [inline] |
Unary not - returns true if finite int poly is equal to zero.
Definition at line 480 of file vnl_finite.h.
bool vnl_finite_int_poly< N, M >::operator!= | ( | Base const & | x | ) | const [inline] |
Definition at line 467 of file vnl_finite.h.
bool vnl_finite_int_poly< N, M >::operator!= | ( | Scalar const & | x | ) | const [inline] |
Definition at line 473 of file vnl_finite.h.
Base& vnl_finite_int_poly< N, M >::operator*= | ( | Scalar const & | n | ) | [inline] |
Scalar multiple of this.
Definition at line 498 of file vnl_finite.h.
Base& vnl_finite_int_poly< N, M >::operator*= | ( | Base const & | r | ) | [inline] |
Multiply&assign: replace lhs by lhs * rhs, modulo the "modulo" polynomial.
Definition at line 528 of file vnl_finite.h.
Base vnl_finite_int_poly< N, M >::operator+ | ( | ) | const [inline] |
Unary plus - returns the current polynomial.
Definition at line 478 of file vnl_finite.h.
Base& vnl_finite_int_poly< N, M >::operator+= | ( | Base const & | r | ) | [inline] |
Plus&assign: replace lhs by lhs + rhs.
Definition at line 483 of file vnl_finite.h.
Base vnl_finite_int_poly< N, M >::operator- | ( | ) | const [inline] |
Unary minus - returns the additive inverse.
Definition at line 476 of file vnl_finite.h.
Base& vnl_finite_int_poly< N, M >::operator-= | ( | Base const & | r | ) | [inline] |
Minus&assign: replace lhs by lhs - rhs.
Definition at line 490 of file vnl_finite.h.
Base& vnl_finite_int_poly< N, M >::operator= | ( | Base const & | x | ) | [inline] |
Assignment.
Definition at line 456 of file vnl_finite.h.
Base& vnl_finite_int_poly< N, M >::operator= | ( | Scalar const & | n | ) | [inline] |
Definition at line 457 of file vnl_finite.h.
bool vnl_finite_int_poly< N, M >::operator== | ( | Base const & | x | ) | const [inline] |
Comparison of finite int polys.
Definition at line 460 of file vnl_finite.h.
bool vnl_finite_int_poly< N, M >::operator== | ( | Scalar const & | x | ) | const [inline] |
Definition at line 468 of file vnl_finite.h.
Scalar vnl_finite_int_poly< N, M >::operator[] | ( | unsigned int | i | ) | const [inline] |
Access to individual coefficients.
Definition at line 453 of file vnl_finite.h.
static Base vnl_finite_int_poly< N, M >::smallest_generator | ( | ) | [inline, static] |
Return the smallest multiplicative generator of the units in this ring.
This is only possible if the units form a cyclic group for multiplication. If not, smallest_generator() returns 1 to indicate this fact. Note that the multiplication group of a finite field is always cyclic.
Definition at line 560 of file vnl_finite.h.
vnl_finite_int_poly< N, M > operator* | ( | vnl_finite_int_poly< N, M > const & | r1, |
vnl_finite_int< N > const & | r2 | ||
) | [related] |
Returns a scalar multiple of a finite int polynomial.
Definition at line 599 of file vnl_finite.h.
vnl_finite_int_poly< N, M > operator* | ( | vnl_finite_int< N > const & | r2, |
vnl_finite_int_poly< N, M > const & | r1 | ||
) | [related] |
Returns a scalar multiple of a finite int polynomial.
Definition at line 608 of file vnl_finite.h.
vnl_finite_int_poly< N, M > operator* | ( | vnl_finite_int_poly< N, M > const & | r1, |
vnl_finite_int_poly< N, M > const & | r2 | ||
) | [related] |
Multiplies two finite int polynomials.
NOTE: this requires the "modulo" polynomial to be set. Do this by calling modulo_polynomial(p), where p is a vector of length M+1.
Definition at line 618 of file vnl_finite.h.
vnl_finite_int_poly< N, M > operator+ | ( | vnl_finite_int_poly< N, M > const & | r1, |
vnl_finite_int_poly< N, M > const & | r2 | ||
) | [related] |
Returns the sum of two finite int polynomials.
Definition at line 582 of file vnl_finite.h.
vnl_finite_int_poly< N, M > operator- | ( | vnl_finite_int_poly< N, M > const & | r1, |
vnl_finite_int_poly< N, M > const & | r2 | ||
) | [related] |
Returns the difference of two finite int polynomials.
Definition at line 590 of file vnl_finite.h.
vcl_ostream & operator<< | ( | vcl_ostream & | s, |
vnl_finite_int_poly< N, M > const & | r | ||
) | [related] |
formatted output.
Definition at line 626 of file vnl_finite.h.
vcl_vector<Scalar> vnl_finite_int_poly< N, M >::val_ [private] |
M-tuple (or degree M-1 polynomial) representing this.
Definition at line 427 of file vnl_finite.h.