name space for MTToolBox More...

Data Structures
class	AbstractGenerator
	pseudo random number generator. More...

class	AlgorithmBestBits
	Algorithm which searches tempering parameters. More...

class	AlgorithmCalculateParity
	Calculate the parity check vector of reducible generator. More...

class	AlgorithmEquidistribution
	Calculate dimension of equi-distribution of output of pseudo random number generators. More...

class	AlgorithmPartialBitPattern
	Algorithm that search tempering parameters to improve dimension of equi-distribution of output of pseudo random number generator. More...

class	AlgorithmPrimitivity
	Algorithm which check if given polynomial is primitive. More...

class	AlgorithmRecursionAndTempering

class	AlgorithmRecursionSearch
	Search parameters of state transition function of pseudo random number generator so that the characteristic polynomial of the function will have max degree and will be primitive. More...

class	AlgorithmReducibleEquidistribution
	Calculate dimension of equi-distribution of reducible generator in worst case. More...

class	AlgorithmReducibleRecursionAndTempering

class	AlgorithmReducibleRecursionSearch
	Search parameters of state transition function of pseudo random number generator so that the characteristic polynomial of the function will have max degree and will be primitive. More...

class	AlgorithmTempering
	Algorithm that search tempering parameters to improve dimension of equi-distribution of output of pseudo random number generator. More...

class	EquidistributionCalculatable
	This class is an Abstract class for calculating dimension of equi-distribution for GF(2)-linear pseudo random number generators. More...

class	linear_generator_vector
	GF(2) pseudo random number generator as a GF(2) vector. More...

class	MersenneTwister
	Mersenne Twister pseudo random number generator. More...

class	MersenneTwister64
	Mersenne Twister pseudo random number generator. More...

class	RecursionSearchable

class	ReducibleGenerator
	This class is an Abstract class for reducible generator. More...

class	ReducibleTemperingCalculatable

class	Sequential
	Counting down number generator. More...

class	temper_params
	class which keeps tempering parameters More...

class	TemperingCalculatable
	Users can search tempering parameters by making GF(2)-linear pseudo random generator class which inherits from this class. More...

class	TestLinearity
	Checks if a pseudo random number generator is GF(2)-linear. More...

Functions
template<typename U , typename V = U>
void	calcCharacteristicPolynomial (RecursionSearchable< U, V > *rand, NTL::GF2X &poly)

template<typename U , typename V = U>
void	calcCharacteristicPolynomial (ReducibleGenerator< U, V > *rand, NTL::GF2X &poly)
	Calculate the characteristic polynomial of reducible generator. More...

template<typename U >
void	minpoly (NTL::GF2X &poly, AbstractGenerator< U > &generator, int pos=0, int stateSize=0)
	Calculate minimal polynomial of output sequence. More...

bool	isMexp (uint32_t degree)
	Returns if 2^degree-1 is prime number. More...

bool	isIrreducible (const NTL::GF2X &poly)
	Check if polynomial is irreducible. More...

bool	isPrime (const NTL::GF2X &poly)
	Check if polynomial is primitive. More...

bool	isPrime (const NTL::GF2X &poly, int degree, const NTL::Vec< NTL::ZZ > &prime_factors)
	Check if polynomial is primitive. More...

bool	isPrime (const NTL::GF2X &poly, int degree, const char *prime_factors[])
	Check if polynomial is primitive. More...

bool	hasFactorOfDegree (NTL::GF2X &poly, long degree)
	Check if primitive polynomial of given degree appears in factorization of poly. More...

template<typename U , typename V = U>
void	annihilate (EquidistributionCalculatable< U, V > *rg, const NTL::GF2X &poly)
	Annihilate internal state of generator by given polynomial. More...

static int	count_bit (uint16_t x)
	Counts number of 1s. More...

static int	count_bit (uint32_t x)
	Counts number of 1s. More...

static int	count_bit (uint64_t x)
	Counts number of 1s. More...

static uint32_t	reverse_bit (uint32_t x)
	Reverse bits. More...

static uint64_t	reverse_bit (uint64_t x)
	Counts number of 1s. More...

template<typename T >
int	bit_size ()
	Returns bit size of T. More...

static void	UNUSED_VARIABLE (void *x)
	Stop warning of unused variable. More...

template<typename T >
T	floor2p (T n)
	Return greatest power of two not greater than n. More...

static void	print_binary (std::ostream &os, NTL::GF2X &poly, bool breakline=true)
	Outputs coefficients of poly to os. More...

template<typename T >
int	get_range (T input, int start, int end)
	Changes input to number between start and end. More...

template<typename T >
void	fill_table (T dist_tbl[], T src_tbl[], int size)
	Makes a fast and redundant lookup table from a tabale of GF(2) vectors. More...

static int	calc_1pos (uint16_t x)
	Returns the position of 1 which appears lowest (most right side) in x, where the position of MSB becomes zero. More...

static int	calc_1pos (uint32_t x)
	Returns the position of 1 which appears lowest (most right side) in x, where the position of MSB becomes zero. More...

static int	calc_1pos (uint64_t x)
	Returns the position of 1 which appears lowest (most right side) in x, where the position of MSB becomes zero. More...

static void	LCM (NTL::GF2X &lcm, const NTL::GF2X &x, const NTL::GF2X &y)
	Calculate the Least Common Multiple of x and y. More...

template<typename U >
static void	toGF2Vec (NTL::vec_GF2 &result, U value)
	convert unsigned integer to GF(2) vector MSB of unsigned integer becomes first element of the vector. More...

template<typename U >
U	getOne ()
	return one of specified type More...

template<typename U >
void	setZero (U &x)
	set zero More...

template<typename U >
unsigned int	getBitOfPos (U bits, int pos)
	set zero More...

template<typename U >
void	setBitOfPos (U *bits, int pos, unsigned int b)
	set zero or 1 to specified bit of specified type variable. More...

template<typename U >
static U	fromGF2Vec (NTL::vec_GF2 &value)
	convert GF(2) vector to unsigned integer the first element of vector becomes the MSB of the result integer. More...

template<typename U >
bool	isZero (U x)
	check if varible is zero or not More...

template<typename U , typename V >
U	convert (V x)
	convert to type U from type V More...

const char *	get_mttoolbox_version ()
	returns library version More...

Variables
const AlgorithmPrimitivity	MersennePrimitivity
	An algorithm which checks if given polynomial is a primitive polynomial of given degree for pseudo random number generator whose internal state size is Mersenne exponent. More...

const char *	prime_factors2_128_1 []
	List of prime numbers appear in the factorization of 2¹²⁸-1. More...

const char *	prime_factors2_160_1 []
	List of prime numbers appear in the factorization of 2¹⁶⁰-1. More...

const char *	prime_factors2_192_1 []
	List of prime numbers appear in the factorization of 2¹⁹²-1. More...

const char *	prime_factors2_224_1 []
	List of prime numbers appear in the factorization of 2²²⁴-1. More...

const char *	prime_factors2_256_1 []
	List of prime numbers appear in the factorization of 2²⁵⁶-1. More...

const char *	prime_factors2_288_1 []
	List of prime numbers appear in the factorization of 2²⁸⁸-1. More...

const char *	prime_factors2_320_1 []
	List of prime numbers appear in the factorization of 2³²⁰-1. More...

const char *	prime_factors2_352_1 []
	List of prime numbers appear in the factorization of 2³⁵²-1. More...

const char *	prime_factors2_384_1 []
	List of prime numbers appear in the factorization of 2³⁸⁴-1. More...

const char *	prime_factors2_416_1 []
	List of prime numbers appear in the factorization of 2⁴¹⁶-1. More...

const char *	prime_factors2_448_1 []
	List of prime numbers appear in the factorization of 2⁴⁴⁸-1. More...

const char *	prime_factors2_480_1 []
	List of prime numbers appear in the factorization of 2⁴⁸⁰-1. More...

const char *	prime_factors2_512_1 []
	List of prime numbers appear in the factorization of 2⁵¹²-1. More...

const char *	prime_factors2_544_1 []
	List of prime numbers appear in the factorization of 2⁵⁴⁴-1. More...

Detailed Description

name space for MTToolBox

Function Documentation

template<typename U , typename V = U>

void MTToolBox::annihilate	(	EquidistributionCalculatable< U, V > *	rg,
		const NTL::GF2X &	poly
	)

Annihilate internal state of generator by given polynomial.

Template Parameters

U	output type of the generator.
V	output type of the generator used for parameter generating.

Parameters

[in,out]	rg	reducible generator
[in]	poly	annihilator polynomial

References MTToolBox::EquidistributionCalculatable< U, V >::add(), MTToolBox::EquidistributionCalculatable< U, V >::clone(), MTToolBox::EquidistributionCalculatable< U, V >::generate(), and MTToolBox::EquidistributionCalculatable< U, V >::setZero().

Referenced by MTToolBox::AlgorithmReducibleRecursionAndTempering< U, G >::search().

template<typename T >

int MTToolBox::bit_size ( )

Returns bit size of T.

This is not correct because just multiply sizeof(T) by eight.

Template Parameters

T type

Returns: bit size of T

static int MTToolBox::calc_1pos ( uint16_t x )

inlinestatic

Returns the position of 1 which appears lowest (most right side) in x, where the position of MSB becomes zero.

Algorithm to search position of 1 is from this page;

See also: http://aggregate.org/MAGIC/#Trailing Zero Count

Parameters

[in] x input

Returns: the position of 1 which appears lowest (most right side) in x, where the position of MSB becomes zero.

References count_bit().

static int MTToolBox::calc_1pos ( uint32_t x )

inlinestatic

Returns the position of 1 which appears lowest (most right side) in x, where the position of MSB becomes zero.

Algorithm to search position of 1 is from this page;

See also: http://aggregate.org/MAGIC/#Trailing Zero Count

Parameters

[in] x input

Returns

the position of 1 which appears lowest (most right side) in x, where the position of MSB becomes zero. Example

calc_1pos(0x80000000U) returns 0.
calc_1pos(0x80000002U) returns 30.
calc_1pos(0) returns -1.

Parameters

[in] x input

Returns: the position of 1 which appears lowest (most right side) in x, where the position of MSB becomes zero.

References count_bit().

static int MTToolBox::calc_1pos ( uint64_t x )

inlinestatic

Returns the position of 1 which appears lowest (most right side) in x, where the position of MSB becomes zero.

Algorithm to search position of 1 is from this page;

See also: http://aggregate.org/MAGIC/#Trailing Zero Count

Parameters

[in] x input

Returns

the position of 1 which appears lowest (most right side) in x, where the position of MSB becomes zero. Example

calc_1pos(UINT64_C(0x8000000000000000)) returns 0.
calc_1pos(UINT64_C(0x8000000000000002)) returns 62.
calc_1pos(0) returns -1.

Parameters

[in] x input

Returns: the position of 1 which appears lowest (most right side) in x, where the position of MSB becomes zero.

References count_bit().

template<typename U , typename V = U>

void MTToolBox::calcCharacteristicPolynomial	(	RecursionSearchable< U, V > *	rand,
		NTL::GF2X &	poly
	)

Referenced by MTToolBox::AlgorithmReducibleEquidistribution< U, G, V >::AlgorithmReducibleEquidistribution(), and MTToolBox::AlgorithmReducibleRecursionAndTempering< U, G >::search().

template<typename U , typename V = U>

void MTToolBox::calcCharacteristicPolynomial	(	ReducibleGenerator< U, V > *	rand,
		NTL::GF2X &	poly
	)

Calculate the characteristic polynomial of reducible generator.

Template Parameters

U	type of return value of random number generator.
V	type of return value of parameter generator.

Parameters

[in,out]	rand	pseudo random number generator.
[in,out]	poly	calculated characteristic polynomial.

References MTToolBox::AbstractGenerator< U >::bitSize(), LCM(), and minpoly().

template<typename U , typename V >

U MTToolBox::convert ( V x )

inline

convert to type U from type V

Template Parameters

U	type convert to
V	type convert from

Parameters

[in] x variable

Returns: value of type U

static int MTToolBox::count_bit ( uint16_t x )

inlinestatic

Counts number of 1s.

SIMD within a Register algorithm citing from a website http://aggregate.org/MAGIC/

Parameters

[in] x bit pattern

Returns: number of 1s in x.

Referenced by calc_1pos().

static int MTToolBox::count_bit ( uint32_t x )

inlinestatic

Counts number of 1s.

SIMD within a Register algorithm citing from a website http://aggregate.org/MAGIC/

Parameters

[in] x bit pattern

Returns: number of 1s in x.

Parameters

[in] x bit pattern

Returns: number of 1s in x.

static int MTToolBox::count_bit ( uint64_t x )

inlinestatic

Counts number of 1s.

SIMD within a Register algorithm citing from a website http://aggregate.org/MAGIC/

Parameters

[in] x bit pattern

Returns: number of 1s in x.

Parameters

[in] x bit pattern

Returns: number of 1s in x.

template<typename T >

void MTToolBox::fill_table	(	T	dist_tbl[],
		T	src_tbl[],
		int	size
	)

Makes a fast and redundant lookup table from a tabale of GF(2) vectors.

Template Parameters

T	type of elements in tables.

Parameters

[out]	dist_tbl	a lookup table to be made
[in]	src_tbl	table of GF(2) vectors.
[in]	size	size of dist_tbl

template<typename T >

T MTToolBox::floor2p ( T n )

Return greatest power of two not greater than n.

Template Parameters

T type of n

Parameters

[in] n integer

Returns: greatest 2^x < = n

template<typename U >

static U MTToolBox::fromGF2Vec ( NTL::vec_GF2 & value )

inlinestatic

convert GF(2) vector to unsigned integer the first element of vector becomes the MSB of the result integer.

Parameters

[in] value source vector

Returns: resulted integer

References setBitOfPos(), and setZero().

const char* MTToolBox::get_mttoolbox_version ( )

returns library version

Returns: library version string

template<typename T >

int MTToolBox::get_range	(	T	input,
		int	start,
		int	end
	)

Changes input to number between start and end.

This conversion may not be uniformly distributed.

Parameters

[in]	input	input
[in]	start	start of range
[in]	end	end of range

Returns: r satisfies that start <= r <= end

template<typename U >

unsigned int MTToolBox::getBitOfPos	(	U	bits,
		int	pos
	)

inline

set zero

Template Parameters

U	type to get bit

Parameters

[in]	bits	variable to get bit
[in]	pos	bit position

Returns: bit of position, zero or one.

Referenced by minpoly().

template<typename U >

U MTToolBox::getOne ( )

inline

return one of specified type

Template Parameters

U	type of one

Returns: one of specified type

bool MTToolBox::hasFactorOfDegree	(	NTL::GF2X &	poly,
		long	degree
	)

Check if primitive polynomial of given degree appears in factorization of poly.

This function will be used by SFMT and dSFMT.

Parameters

[in,out]	poly	polynomial over GF(2)
[in]	degree	if poly has primitive polynomial with degree in its factors.

Returns: true if poly has primitive polynomial with degree.

Referenced by MTToolBox::AlgorithmReducibleRecursionSearch< U, V >::start().

bool MTToolBox::isIrreducible ( const NTL::GF2X & poly )

Check if polynomial is irreducible.

Parameters

[in] poly polynomial whose coefficients are GF(2)

Returns: true if poly is irreducible

bool MTToolBox::isMexp ( uint32_t degree )

Returns if 2^degree-1 is prime number.

This is checked by fixed list of exponents of Mersenne Prime, therefore this check is not complete.

Parameters

[in] degree number to be checked

Returns: true if 2^degree -1 is prime number.

bool MTToolBox::isPrime ( const NTL::GF2X & poly )

Check if polynomial is primitive.

This check is lazy check. Only if degree of polynomial is Mersenne Exponent, the result is correct. This check should not be used, when bit size of internal state is not Mersenne Exponent.

Parameters

[in] poly polynomial over GF(2)

Returns: true if polynomial is primitive

Referenced by MTToolBox::AlgorithmRecursionSearch< U, V >::AlgorithmRecursionSearch(), MTToolBox::AlgorithmRecursionAndTempering< U, V >::search(), and MTToolBox::AlgorithmRecursionSearch< U, V >::start().

bool MTToolBox::isPrime	(	const NTL::GF2X &	poly,
		int	degree,
		const NTL::Vec< NTL::ZZ > &	prime_factors
	)

Check if polynomial is primitive.

This function returns false if degree of polynomial is not degree. Users should give a list of primes which appear in integer factorization of 2^degree-1.

Parameters

[in]	poly	polynomial over GF(2)
[in]	degree	poly expected to have degree.
[in]	prime_factors	a list of primes which appear in integer factorization of 2^degree-1.

bool MTToolBox::isPrime	(	const NTL::GF2X &	poly,
		int	degree,
		const char *	prime_factors[]
	)

Check if polynomial is primitive.

This function returns false if degree of polynomial is not degree. Users should give a list of primes which app-er in integer factorization of 2^degree-1.

Parameters

[in]	poly	polynomial over GF(2)
[in]	degree	poly expected to have degree.
[in]	prime_factors	a list of primes which appear in integer factorization of 2^degree-1.

template<typename U >

bool MTToolBox::isZero ( U x )

inline

check if varible is zero or not

Template Parameters

U	type of variable

Parameters

[in] x variable to be checked

Returns: ture if x is zero

Referenced by MTToolBox::linear_generator_vector< U, V >::next_state(), and MTToolBox::AlgorithmCalculateParity< U, G >::searchParity().

static void MTToolBox::LCM	(	NTL::GF2X &	lcm,
		const NTL::GF2X &	x,
		const NTL::GF2X &	y
	)

inlinestatic

Calculate the Least Common Multiple of x and y.

Parameters

[out]	lcm	the Least Common Multiple of x and y.
[in]	x	a polynomial
[in]	y	a polynomial

Referenced by calcCharacteristicPolynomial().

template<typename U >

void MTToolBox::minpoly	(	NTL::GF2X &	poly,
		AbstractGenerator< U > &	generator,
		int	pos = `0`,
		int	stateSize = `0`
	)

Calculate minimal polynomial of output sequence.

Template Parameters

U	type of output of pseudo random number generator

Parameters

[out]	poly	minimal polynomial
[in]	generator	GF(2)-linear pseudo random number generator
[in]	pos	specifies how manieth bit from LSB is checked, zero means LSB.
[in]	stateSize	bit size of internal state.

References MTToolBox::AbstractGenerator< U >::bitSize(), MTToolBox::AbstractGenerator< U >::generate(), and getBitOfPos().

Referenced by calcCharacteristicPolynomial(), MTToolBox::AlgorithmReducibleRecursionSearch< U, V >::start(), and MTToolBox::AlgorithmRecursionSearch< U, V >::start().

static void MTToolBox::print_binary	(	std::ostream &	os,
		NTL::GF2X &	poly,
		bool	breakline = `true`
	)

inlinestatic

Outputs coefficients of poly to os.

Coefficients of low degree terms are outputted first.

Parameters

[in,out]	os	output stream
[in]	poly	polynomial to be outputted
[in]	breakline	if true, line break after every 32 terms.

static uint32_t MTToolBox::reverse_bit ( uint32_t x )

inlinestatic

Reverse bits.

Reverse upper side and lower side in input. The MSB bocomes the LSB. SIMD within a Register algorithm citing from a website http://aggregate.org/MAGIC/

Parameters

[in] x bit pattern

Returns: reverse of x

static uint64_t MTToolBox::reverse_bit ( uint64_t x )

inlinestatic

Counts number of 1s.

SIMD within a Register algorithm citing from a website http://aggregate.org/MAGIC/

Parameters

[in] x bit pattern

Returns: number of 1s in x.

Parameters

[in] x bit pattern

Returns: number of 1s in x.

Parameters

[in] x bit pattern

Returns: reverse of x

template<typename U >

void MTToolBox::setBitOfPos	(	U *	bits,
		int	pos,
		unsigned int	b
	)

inline

set zero or 1 to specified bit of specified type variable.

Template Parameters

U	type of variable

Parameters

[in,out]	bits	variable
[in]	pos	position of bit, LSB is 0
[in]	b	bit to set

Referenced by fromGF2Vec().

template<typename U >

void MTToolBox::setZero ( U & x )

inline

set zero

Template Parameters

U	type to set zero

Parameters

[out] x variable set to be zero

Referenced by fromGF2Vec(), MTToolBox::linear_generator_vector< U, V >::linear_generator_vector(), and MTToolBox::AlgorithmCalculateParity< U, G >::searchParity().

template<typename U >

static void MTToolBox::toGF2Vec	(	NTL::vec_GF2 &	result,
		U	value
	)

inlinestatic

convert unsigned integer to GF(2) vector MSB of unsigned integer becomes first element of the vector.

Template Parameters

U	type of conversion source

Parameters

[out]	result	The result vector
[in]	value	source integer

static void MTToolBox::UNUSED_VARIABLE ( void * x )

inlinestatic

Stop warning of unused variable.

Parameters

[in] x pointer to unused variable

Variable Documentation

const AlgorithmPrimitivity MTToolBox::MersennePrimitivity

An algorithm which checks if given polynomial is a primitive polynomial of given degree for pseudo random number generator whose internal state size is Mersenne exponent.

Referenced by MTToolBox::AlgorithmRecursionSearch< U, V >::AlgorithmRecursionSearch().

const char* MTToolBox::prime_factors2_128_1[]

List of prime numbers appear in the factorization of 2¹²⁸-1.

const char* MTToolBox::prime_factors2_160_1[]

List of prime numbers appear in the factorization of 2¹⁶⁰-1.

const char* MTToolBox::prime_factors2_192_1[]

List of prime numbers appear in the factorization of 2¹⁹²-1.

const char* MTToolBox::prime_factors2_224_1[]

List of prime numbers appear in the factorization of 2²²⁴-1.

const char* MTToolBox::prime_factors2_256_1[]

List of prime numbers appear in the factorization of 2²⁵⁶-1.

const char* MTToolBox::prime_factors2_288_1[]

List of prime numbers appear in the factorization of 2²⁸⁸-1.

const char* MTToolBox::prime_factors2_320_1[]

List of prime numbers appear in the factorization of 2³²⁰-1.

const char* MTToolBox::prime_factors2_352_1[]

List of prime numbers appear in the factorization of 2³⁵²-1.

const char* MTToolBox::prime_factors2_384_1[]

List of prime numbers appear in the factorization of 2³⁸⁴-1.

const char* MTToolBox::prime_factors2_416_1[]

List of prime numbers appear in the factorization of 2⁴¹⁶-1.

const char* MTToolBox::prime_factors2_448_1[]

List of prime numbers appear in the factorization of 2⁴⁴⁸-1.

const char* MTToolBox::prime_factors2_480_1[]

List of prime numbers appear in the factorization of 2⁴⁸⁰-1.

const char* MTToolBox::prime_factors2_512_1[]

List of prime numbers appear in the factorization of 2⁵¹²-1.

const char* MTToolBox::prime_factors2_544_1[]

List of prime numbers appear in the factorization of 2⁵⁴⁴-1.

Data Structures

Functions

Variables

Detailed Description

Function Documentation

Variable Documentation