Public Member Functions | Static Public Member Functions | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes | Related Functions
vnl_finite_int_poly< N, M > Class Template Reference

finite modulo-N arithmetic with polynomials of degree < M. More...

#include <vnl_finite.h>

List of all members.

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.
Baseoperator= (Base const &x)
 Assignment.
Baseoperator= (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.
Baseoperator+= (Base const &r)
 Plus&assign: replace lhs by lhs + rhs.
Baseoperator-= (Base const &r)
 Minus&assign: replace lhs by lhs - rhs.
Baseoperator*= (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.
Baseoperator*= (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< Scalarval_
 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.

Detailed Description

template<int N, int M>
class vnl_finite_int_poly< N, M >

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.


Member Typedef Documentation

template<int N, int M>
typedef vnl_finite_int_poly<N,M> vnl_finite_int_poly< N, M >::Base [private]

Definition at line 424 of file vnl_finite.h.

template<int N, int M>
typedef vnl_finite_int<N> vnl_finite_int_poly< N, M >::Scalar [private]

Definition at line 425 of file vnl_finite.h.


Constructor & Destructor Documentation

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
vnl_finite_int_poly< N, M >::vnl_finite_int_poly ( Base const &  x) [inline]

Definition at line 442 of file vnl_finite.h.

template<int N, int M>
vnl_finite_int_poly< N, M >::~vnl_finite_int_poly ( ) [inline]

Definition at line 444 of file vnl_finite.h.


Member Function Documentation

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
bool vnl_finite_int_poly< N, M >::operator!= ( Base const &  x) const [inline]

Definition at line 467 of file vnl_finite.h.

template<int N, int M>
bool vnl_finite_int_poly< N, M >::operator!= ( Scalar const &  x) const [inline]

Definition at line 473 of file vnl_finite.h.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
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.

template<int N, int M>
Base& vnl_finite_int_poly< N, M >::operator= ( Base const &  x) [inline]

Assignment.

Definition at line 456 of file vnl_finite.h.

template<int N, int M>
Base& vnl_finite_int_poly< N, M >::operator= ( Scalar const &  n) [inline]

Definition at line 457 of file vnl_finite.h.

template<int N, int M>
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.

template<int N, int M>
bool vnl_finite_int_poly< N, M >::operator== ( Scalar const &  x) const [inline]

Definition at line 468 of file vnl_finite.h.

template<int N, int M>
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.

template<int N, int M>
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.


Friends And Related Function Documentation

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 
) [related]

Returns a scalar multiple of a finite int polynomial.

Definition at line 599 of file vnl_finite.h.

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 
) [related]

Returns a scalar multiple of a finite int polynomial.

Definition at line 608 of file vnl_finite.h.

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

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 
) [related]

Returns the sum of two finite int polynomials.

Definition at line 582 of file vnl_finite.h.

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 
) [related]

Returns the difference of two finite int polynomials.

Definition at line 590 of file vnl_finite.h.

template<int N, int M>
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.


Member Data Documentation

template<int N, int M>
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.


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