The Number Theoretic Transform functions. More...

Functions
NTTW_DLL_SYM void	rearrange (nttw_integer *data, const size_t n)
	Bit-reversal of Data of size n. n should be dyadic.
NTTW_DLL_SYM int	bigshr (nttw_integer d, nttw_integer s, const size_t n)
	Shifts s right one bit to d, returns carry bit.
NTTW_DLL_SYM nttw_integer	pow_mod (nttw_integer base, nttw_integer exp)
	Computers the power of the base modulo the defined MODULUS.
NTTW_DLL_SYM nttw_integer	pow_mod2 (nttw_integer base, nttw_integer exp, nttw_integer modulus)
	Computers the power of the base modulo the given modulus.
NTTW_DLL_SYM nttw_integer	pow_mod2_long (nttw_integer base, nttw_integer exp, nttw_integer modulus)
	Computers the power of the base modulo the given modulus. Force unsigned long long's in calculations.
NTTW_DLL_SYM nttw_integer	pow_mod_long (nttw_integer base, nttw_integer exp)
	Computers the power of the base modulo the given modulus. Big Integer version.
NTTW_DLL_SYM void	fntt (nttw_integer *data, const size_t nn, const nttw_integer pr, const int isign)
	Computes the 1D Fast Number Theoretic Transform (FNTT) using the Cooley-Tukey algorithm.
NTTW_DLL_SYM void	fntt_2D (nttw_integer data, nttw_integer result, const size_t nn, const int isign)
	Computes the 2D Fast Number Theoretic Transform (FNTT) using the Cooley-Tukey algorithm.
NTTW_DLL_SYM void	fntt_prime (const nttw_integer inData, nttw_integer outData, const size_t p, const nttw_integer root, const nttw_integer primeDash, const nttw_integer proot, int isign, const int norm)
	Computes the Prime Length Fast Number Theoretic Transform (FNTT) using Rader's algorithm.
NTTW_DLL_SYM void	fntt_2D_prime (nttw_integer data, nttw_integer result, const size_t n, const nttw_integer root, const nttw_integer primeDash, const nttw_integer proot, const int isign, const int norm)
	Computes the 2D Prime Length Fast Number Theoretic Transform (FNTT) using Rader's algorithm.
NTTW_DLL_SYM nttw_integer *	padData_Rader (nttw_integer *data, const size_t p, const size_t newSize, const nttw_integer primeDash)
	Pads the data to the nearest highly composite length as needed by Rader's algorithm.
NTTW_DLL_SYM nttw_integer *	padTransformMatrix_Rader (nttw_integer *transData, const size_t p, const size_t newSize)
	Pads the transform matrix to the nearest highly composite length as needed by Rader's algorithm.
NTTW_DLL_SYM void	extractResult_Rader (nttw_integer paddedData, nttw_integer data, const size_t p)
	Extracts the data for the result from the padded result.
NTTW_DLL_SYM void	ntt_norm (nttw_integer *data, const size_t n)
	Normalises data of length n in the number field of MODULUS.

Detailed Description

The Number Theoretic Transform functions.

The main function for NTTs is fntt() and it requires that the sequence be dyadic in length. Two dimensional transform is also assumed to be dyadic and can be done via fntt_2D().

Function Documentation

bigshr	(	nttw_integer *	d,
		nttw_integer *	s,
		const size_t	n
	)

Shifts s right one bit to d, returns carry bit.

Author:: Mikko Tommila et al., APFloat Library 2005.

Definition at line 57 of file number32.c.

extractResult_Rader	(	nttw_integer *	paddedData,
		nttw_integer *	data,
		const size_t	p
	)

Extracts the data for the result from the padded result.

Copy data from the first N-1 elements

Definition at line 440 of file number32.c.

fntt	(	nttw_integer *	data,
		const size_t	nn,
		const nttw_integer	pr,
		const int	isign
	)

Computes the 1D Fast Number Theoretic Transform (FNTT) using the Cooley-Tukey algorithm.

Computes the 1D Fast Number Theoretic Transform (FNTT). The result is NOT normalised within the function. The transform is done inplace, destroying the input. Use the ntt_norm() function for normalisation.

Definition at line 169 of file number32.c.

fntt_2D	(	nttw_integer *	data,
		nttw_integer *	result,
		const size_t	nn,
		const int	isign
	)

Computes the 2D Fast Number Theoretic Transform (FNTT) using the Cooley-Tukey algorithm.

Computes the 2D Fast Number Theoretic Transform (FNTT). The result is normalised within the function. The transform is done inplace, destroying the input but copied to result. The data is assumed to be a square array.

Cooley-Tukey data is corrupted in the process (for performance)

Pointers used where-ever possible, norm when copying

NT Rows

NT Columns

Stops modulo overrun, div by N early

Inverse so Copy and Norm

Definition at line 213 of file number32.c.

fntt_2D_prime	(	nttw_integer *	data,
		nttw_integer *	result,
		const size_t	n,
		const nttw_integer	root,
		const nttw_integer	primeDash,
		const nttw_integer	proot,
		const int	isign,
		const int	norm
	)

Computes the 2D Prime Length Fast Number Theoretic Transform (FNTT) using Rader's algorithm.

Computes the 2D Prime Length Fast Number Theoretic Transform (FNTT). The result is normalised given the Boolean. The transform is copied to result (outData). The data is assumed to be a square array.

NT Rows

NT Columns

Inverse so Copy and Norm

Copy

Definition at line 369 of file number32.c.

fntt_prime	(	const nttw_integer *	inData,
		nttw_integer *	outData,
		const size_t	p,
		const nttw_integer	root,
		const nttw_integer	primeDash,
		const nttw_integer	proot,
		int	isign,
		const int	norm
	)

Computes the Prime Length Fast Number Theoretic Transform (FNTT) using Rader's algorithm.

Computes the Prime Length Fast Number Theoretic Transform (FNTT). The result is normalised given the Boolean. The transform is copied to result (outData).

Indices

Reorder data and W matrix

Todo:: Check casting here

Ensure convolution will be highly composite If not then pad sequences

Convolution Inv's

Data Eigenvalues

W Eigenvalues

Convolve

Convolution from Convolution Eigenvalues

Norm NTTs and add zeroth element

Compute DC

Reorder Result

Copy padded result

Norm

Definition at line 248 of file number32.c.

ntt_norm	(	nttw_integer *	data,
		const size_t	n
	)

Normalises data of length n in the number field of MODULUS.

Definition at line 448 of file number32.c.

padData_Rader	(	nttw_integer *	data,
		const size_t	p,
		const size_t	newSize,
		const nttw_integer	primeDash
	)

Pads the data to the nearest highly composite length as needed by Rader's algorithm.

Copy data leaving N'- p + 1 zeros between zeroth and first element

Definition at line 411 of file number32.c.

padTransformMatrix_Rader	(	nttw_integer *	transData,
		const size_t	p,
		const size_t	newSize
	)

Pads the transform matrix to the nearest highly composite length as needed by Rader's algorithm.

Copy data leaving N'- p + 1 zeros between zeroth and first element

Definition at line 427 of file number32.c.

pow_mod	(	nttw_integer	base,
		nttw_integer	exp
	)

Computers the power of the base modulo the defined MODULUS.

Author:: Mikko Tommila et al., APFloat Library 2005.

Definition at line 83 of file number32.c.

pow_mod2	(	nttw_integer	base,
		nttw_integer	exp,
		nttw_integer	modulus
	)

Computers the power of the base modulo the given modulus.

Definition at line 104 of file number32.c.

pow_mod2_long	(	nttw_integer	base,
		nttw_integer	exp,
		nttw_integer	modulus
	)

Computers the power of the base modulo the given modulus. Force unsigned long long's in calculations.

Definition at line 125 of file number32.c.

pow_mod_long	(	nttw_integer	base,
		nttw_integer	exp
	)

Computers the power of the base modulo the given modulus. Big Integer version.

Definition at line 146 of file number32.c.

rearrange	(	nttw_integer *	data,
		const size_t	n
	)

Bit-reversal of Data of size n. n should be dyadic.

For all of input signal

Ignore swapped entries

Swap

Bit mask

While bit is set

Drop bit

The current bit is 0 - set it

Definition at line 31 of file number32.c.

Number Theoretic Transforms (NTTs) and Helpers

Functions

Detailed Description

Function Documentation