modulo-N arithmetic (finite ring Z_N and Z_N[X]) More...

#include <vcl_iostream.h>
#include <vcl_cassert.h>
#include <vcl_vector.h>
#include <vcl_cstddef.h>

Classes
class	vnl_finite_int< N >
	finite modulo-N arithmetic. More...
class	vnl_finite_int_poly< N, M >
	finite modulo-N arithmetic with polynomials of degree < M. More...
Functions
template<int N>
vcl_ostream &	operator<< (vcl_ostream &s, vnl_finite_int< N > const &r)
	formatted output.
template<int N>
vcl_istream &	operator>> (vcl_istream &s, vnl_finite_int< N > &r)
	simple input.
template<int N>
vnl_finite_int< N >	operator+ (vnl_finite_int< N > const &r1, vnl_finite_int< N > const &r2)
	Returns the sum of two finite int numbers.
template<int N>
vnl_finite_int< N >	operator+ (vnl_finite_int< N > const &r1, int r2)
	Returns the sum of two finite int numbers.
template<int N>
vnl_finite_int< N >	operator+ (int r2, vnl_finite_int< N > const &r1)
	Returns the sum of two finite int numbers.
template<int N>
vnl_finite_int< N >	operator- (vnl_finite_int< N > const &r1, vnl_finite_int< N > const &r2)
	Returns the difference of two finite int numbers.
template<int N>
vnl_finite_int< N >	operator- (vnl_finite_int< N > const &r1, int r2)
	Returns the difference of two finite int numbers.
template<int N>
vnl_finite_int< N >	operator- (int r2, vnl_finite_int< N > const &r1)
	Returns the difference of two finite int numbers.
template<int N>
vnl_finite_int< N >	operator* (vnl_finite_int< N > const &r1, vnl_finite_int< N > const &r2)
	Returns the product of two finite int numbers.
template<int N>
vnl_finite_int< N >	operator* (vnl_finite_int< N > const &r1, int r2)
	Returns the product of two finite int numbers.
template<int N>
vnl_finite_int< N >	operator* (int r2, vnl_finite_int< N > const &r1)
	Returns the product of two finite int numbers.
template<int N>
vnl_finite_int< N >	operator/ (vnl_finite_int< N > const &r1, vnl_finite_int< N > const &r2)
	Returns the quotient of two finite int numbers.
template<int N>
vnl_finite_int< N >	operator/ (vnl_finite_int< N > const &r1, int r2)
	Returns the quotient of two finite int numbers.
template<int N>
vnl_finite_int< N >	operator/ (int r1, vnl_finite_int< N > const &r2)
	Returns the quotient of two finite int numbers.
template<int N>
bool	operator== (int r1, vnl_finite_int< N > const &r2)
template<int N>
bool	operator!= (int r1, vnl_finite_int< N > const &r2)
template<int N>
vnl_finite_int< N >	vnl_math_squared_magnitude (vnl_finite_int< N > const &x)
template<int N>
vnl_finite_int< N >	vnl_math_sqr (vnl_finite_int< N > const &x)
template<int N>
bool	vnl_math_isnan (vnl_finite_int< N > const &)
template<int N>
bool	vnl_math_isfinite (vnl_finite_int< N > const &x)
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

modulo-N arithmetic (finite ring Z_N and Z_N[X])

The templated vnl_finite_int<N> provides arithmetic "modulo N", i.e., arithmetic in the finite (Galois) field GF(N) in case N is a prime or just in the finite ring (or semi-field) of integers modulo N otherwise. In that case division makes no sense (unless no zero divisor is involved), but all other operations remain valid.

Note that this does not cover finite fields with non-prime sizes (4,8,9,...). These are covered by the vnl_finite_int_poly<N,M> class, which implements arithmetic with polynomials of degree < M over vnl_finite_int<N>. Multiplication is defined modulo a degree M polynomial.

For N prime, and when the "modulo" polynomial is irreducible, vnl_finite_int_poly<N,M> implements the finite field GF(N^M).

Author:: Peter Vanroose, K.U.Leuven, ESAT/PSI.

Date:: 5 May 2002.

   Modifications
    1 June 2002 - Peter Vanroose - added totient(), decompose(), is_unit(), order(), log(), exp().
    4 June 2002 - Peter Vanroose - renamed class and file name
    8 June 2002 - Peter Vanroose - added vnl_finite_int_poly<N,M>
    16 Dec 2007 - Peter Vanroose - more efficient implementation of Ntothe()

Definition in file vnl_finite.h.

Function Documentation

template<int N>

bool operator!=	(	int	r1,
		vnl_finite_int< N > const &	r2
	)		`[inline]`

Definition at line 385 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > operator*	(	vnl_finite_int< N > const &	r1,
		vnl_finite_int< N > const &	r2
	)		`[inline]`

Returns the product of two finite int numbers.

Definition at line 331 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > operator*	(	vnl_finite_int< N > const &	r1,
		int	r2
	)		`[inline]`

Returns the product of two finite int numbers.

Definition at line 339 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > operator*	(	int	r2,
		vnl_finite_int< N > const &	r1
	)		`[inline]`

Returns the product of two finite int numbers.

Definition at line 347 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< N > const &	r2
	)		`[inline]`

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
	)		`[inline]`

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
	)		`[inline]`

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>

vnl_finite_int< N > operator+	(	vnl_finite_int< N > const &	r1,
		vnl_finite_int< N > const &	r2
	)		`[inline]`

Returns the sum of two finite int numbers.

Definition at line 283 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > operator+	(	vnl_finite_int< N > const &	r1,
		int	r2
	)		`[inline]`

Returns the sum of two finite int numbers.

Definition at line 291 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > operator+	(	int	r2,
		vnl_finite_int< N > const &	r1
	)		`[inline]`

Returns the sum of two finite int numbers.

Definition at line 299 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
	)		`[inline]`

Returns the sum of two finite int polynomials.

Definition at line 582 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > operator-	(	vnl_finite_int< N > const &	r1,
		vnl_finite_int< N > const &	r2
	)		`[inline]`

Returns the difference of two finite int numbers.

Definition at line 307 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > operator-	(	vnl_finite_int< N > const &	r1,
		int	r2
	)		`[inline]`

Returns the difference of two finite int numbers.

Definition at line 315 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > operator-	(	int	r2,
		vnl_finite_int< N > const &	r1
	)		`[inline]`

Returns the difference of two finite int numbers.

Definition at line 323 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
	)		`[inline]`

Returns the difference of two finite int polynomials.

Definition at line 590 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > operator/	(	vnl_finite_int< N > const &	r1,
		vnl_finite_int< N > const &	r2
	)		`[inline]`

Returns the quotient of two finite int numbers.

Uses r2.reciproc() for efficient computation.

Definition at line 356 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > operator/	(	vnl_finite_int< N > const &	r1,
		int	r2
	)		`[inline]`

Returns the quotient of two finite int numbers.

Definition at line 364 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > operator/	(	int	r1,
		vnl_finite_int< N > const &	r2
	)		`[inline]`

Returns the quotient of two finite int numbers.

Definition at line 372 of file vnl_finite.h.

template<int N>

vcl_ostream & operator<<	(	vcl_ostream &	s,
		vnl_finite_int< N > const &	r
	)		`[inline]`

formatted output.

Definition at line 267 of file vnl_finite.h.

template<int N, int M>

vcl_ostream & operator<<	(	vcl_ostream &	s,
		vnl_finite_int_poly< N, M > const &	r
	)		`[inline]`

formatted output.

Definition at line 626 of file vnl_finite.h.

template<int N>

bool operator==	(	int	r1,
		vnl_finite_int< N > const &	r2
	)		`[inline]`

Definition at line 380 of file vnl_finite.h.

template<int N>

vcl_istream & operator>>	(	vcl_istream &	s,
		vnl_finite_int< N > &	r
	)		`[inline]`

simple input.

Definition at line 275 of file vnl_finite.h.

template<int N>

bool vnl_math_isfinite ( vnl_finite_int< N > const & x ) [inline]

Definition at line 405 of file vnl_finite.h.

template<int N>

bool vnl_math_isnan ( vnl_finite_int< N > const & ) [inline]

Definition at line 400 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > vnl_math_sqr ( vnl_finite_int< N > const & x ) [inline]

Definition at line 395 of file vnl_finite.h.

template<int N>

vnl_finite_int< N > vnl_math_squared_magnitude ( vnl_finite_int< N > const & x ) [inline]

Definition at line 390 of file vnl_finite.h.

Classes

Functions

Detailed Description

Function Documentation