Performs negacyclic forward and inverse number-theoretic transform (NTT), commonly used in RLWE cryptography. More...

#include <ntt.hpp>

Classes
struct	AllocatorAdapter
	Helper class for custom memory allocation. More...

Public Member Functions
	NTT ()=default
	Initializes an empty NTT object. More...

	~NTT ()=default
	Destructs the NTT object. More...

	NTT (uint64_t degree, uint64_t q, std::shared_ptr< AllocatorBase > alloc_ptr={})
	Initializes an NTT object with degree `degree` and modulus `q`. More...

template<class Allocator , class... AllocatorArgs>
	NTT (uint64_t degree, uint64_t q, Allocator &&a, AllocatorArgs &&... args)

	NTT (uint64_t degree, uint64_t q, uint64_t root_of_unity, std::shared_ptr< AllocatorBase > alloc_ptr={})
	Initializes an NTT object with degree `degree` and modulus `q`. More...

template<class Allocator , class... AllocatorArgs>
	NTT (uint64_t degree, uint64_t q, uint64_t root_of_unity, Allocator &&a, AllocatorArgs &&... args)

void	ComputeForward (uint64_t result, const uint64_t operand, uint64_t input_mod_factor, uint64_t output_mod_factor)
	Compute forward NTT. Results are bit-reversed. More...

void	ComputeInverse (uint64_t result, const uint64_t operand, uint64_t input_mod_factor, uint64_t output_mod_factor)

uint64_t	GetMinimalRootOfUnity () const
	Returns the minimal 2N'th root of unity. More...

uint64_t	GetDegree () const
	Returns the degree N. More...

uint64_t	GetModulus () const
	Returns the word-sized prime modulus. More...

const AlignedVector64< uint64_t > &	GetRootOfUnityPowers () const
	Returns the root of unity powers in bit-reversed order. More...

uint64_t	GetRootOfUnityPower (size_t i)
	Returns the root of unity power at bit-reversed index i. More...

const AlignedVector64< uint64_t > &	GetPrecon32RootOfUnityPowers () const
	Returns 32-bit pre-conditioned root of unity powers in bit-reversed order. More...

const AlignedVector64< uint64_t > &	GetPrecon64RootOfUnityPowers () const
	Returns 64-bit pre-conditioned root of unity powers in bit-reversed order. More...

const AlignedVector64< uint64_t > &	GetAVX512RootOfUnityPowers () const
	Returns the root of unity powers in bit-reversed order with modifications for use by AVX512 implementation. More...

const AlignedVector64< uint64_t > &	GetAVX512Precon32RootOfUnityPowers () const
	Returns 32-bit pre-conditioned AVX512 root of unity powers in bit-reversed order. More...

const AlignedVector64< uint64_t > &	GetAVX512Precon52RootOfUnityPowers () const
	Returns 52-bit pre-conditioned AVX512 root of unity powers in bit-reversed order. More...

const AlignedVector64< uint64_t > &	GetAVX512Precon64RootOfUnityPowers () const
	Returns 64-bit pre-conditioned AVX512 root of unity powers in bit-reversed order. More...

const AlignedVector64< uint64_t > &	GetInvRootOfUnityPowers () const
	Returns the inverse root of unity powers in bit-reversed order. More...

uint64_t	GetInvRootOfUnityPower (size_t i)
	Returns the inverse root of unity power at bit-reversed index i. More...

const AlignedVector64< uint64_t > &	GetPrecon32InvRootOfUnityPowers () const
	Returns the vector of 32-bit pre-conditioned pre-computed root of unity. More...

const AlignedVector64< uint64_t > &	GetPrecon52InvRootOfUnityPowers () const
	Returns the vector of 52-bit pre-conditioned pre-computed root of unity. More...

const AlignedVector64< uint64_t > &	GetPrecon64InvRootOfUnityPowers () const
	Returns the vector of 64-bit pre-conditioned pre-computed root of unity. More...

Static Public Member Functions
static bool	CheckArguments (uint64_t degree, uint64_t modulus)
	Returns true if arguments satisfy constraints for negacyclic NTT. More...

static size_t	MaxDegreeBits ()
	Maximum power of 2 in degree. More...

static size_t	MaxModulusBits ()
	Maximum number of bits in modulus;. More...

Static Public Attributes
static const size_t	s_default_shift_bits {64}
	Default bit shift used in Barrett precomputation. More...

static const size_t	s_ifma_shift_bits {52}
	Bit shift used in Barrett precomputation when AVX512-IFMA acceleration is enabled. More...

static const size_t	s_max_fwd_32_modulus {1ULL << (32 - 2)}
	Maximum modulus to use 32-bit AVX512-DQ acceleration for the forward transform. More...

static const size_t	s_max_inv_32_modulus {1ULL << (32 - 1)}
	Maximum modulus to use 32-bit AVX512-DQ acceleration for the inverse transform. More...

static const size_t	s_max_fwd_ifma_modulus {1ULL << (s_ifma_shift_bits - 2)}
	Maximum modulus to use AVX512-IFMA acceleration for the forward transform. More...

static const size_t	s_max_inv_ifma_modulus {1ULL << (s_ifma_shift_bits - 1)}
	Maximum modulus to use AVX512-IFMA acceleration for the inverse transform. More...

Detailed Description

Performs negacyclic forward and inverse number-theoretic transform (NTT), commonly used in RLWE cryptography.

The number-theoretic transform (NTT) specializes the discrete Fourier transform (DFT) to the finite field \( \mathbb{Z}_q[X] / (X^N + 1) \).

Constructor & Destructor Documentation

◆ NTT() [1/5]

intel::hexl::NTT::NTT ( )

default

Initializes an empty NTT object.

◆ ~NTT()

intel::hexl::NTT::~NTT ( )

default

Destructs the NTT object.

◆ NTT() [2/5]

intel::hexl::NTT::NTT	(	uint64_t	degree,
		uint64_t	q,
		std::shared_ptr< AllocatorBase >	alloc_ptr = `{}`
	)

Initializes an NTT object with degree degree and modulus q.

Parameters

[in]	degree	also known as N. Size of the NTT transform. Must be a power of 2
[in]	q	Prime modulus. Must satisfy \( q == 1 \mod 2N \)
[in]	alloc_ptr	Custom memory allocator used for intermediate calculations Performs pre-computation necessary for forward and inverse transforms

◆ NTT() [3/5]

template<class Allocator , class... AllocatorArgs>

intel::hexl::NTT::NTT	(	uint64_t	degree,
		uint64_t	q,
		Allocator &&	a,
		AllocatorArgs &&...	args
	)

inline

◆ NTT() [4/5]

intel::hexl::NTT::NTT	(	uint64_t	degree,
		uint64_t	q,
		uint64_t	root_of_unity,
		std::shared_ptr< AllocatorBase >	alloc_ptr = `{}`
	)

Initializes an NTT object with degree degree and modulus q.

Parameters

[in]	degree	also known as N. Size of the NTT transform. Must be a power of 2
[in]	q	Prime modulus. Must satisfy \( q == 1 \mod 2N \)
[in]	root_of_unity	2N'th root of unity in \( \mathbb{Z_q} \).
[in]	alloc_ptr	Custom memory allocator used for intermediate calculations

Performs pre-computation necessary for forward and inverse transforms

◆ NTT() [5/5]

template<class Allocator , class... AllocatorArgs>

intel::hexl::NTT::NTT	(	uint64_t	degree,
		uint64_t	q,
		uint64_t	root_of_unity,
		Allocator &&	a,
		AllocatorArgs &&...	args
	)

inline

Member Function Documentation

◆ CheckArguments()

static bool intel::hexl::NTT::CheckArguments	(	uint64_t	degree,
		uint64_t	modulus
	)

static

Returns true if arguments satisfy constraints for negacyclic NTT.

Parameters

[in]	degree	N. Size of the transform, i.e. the polynomial degree. Must be a power of two.
[in]	modulus	Prime modulus q. Must satisfy q mod 2N = 1

◆ ComputeForward()

void intel::hexl::NTT::ComputeForward	(	uint64_t *	result,
		const uint64_t *	operand,
		uint64_t	input_mod_factor,
		uint64_t	output_mod_factor
	)

Compute forward NTT. Results are bit-reversed.

Parameters

[out]	result	Stores the result
[in]	operand	Data on which to compute the NTT
[in]	input_mod_factor	Assume input `operand` are in [0, input_mod_factor * q). Must be 1, 2 or 4.
[in]	output_mod_factor	Returns output `result` in [0, output_mod_factor * q). Must be 1 or 4.

◆ ComputeInverse()

void intel::hexl::NTT::ComputeInverse	(	uint64_t *	result,
		const uint64_t *	operand,
		uint64_t	input_mod_factor,
		uint64_t	output_mod_factor
	)

Compute inverse NTT. Results are bit-reversed.

Parameters

[out]	result	Stores the result
[in]	operand	Data on which to compute the NTT
[in]	input_mod_factor	Assume input `operand` are in [0, input_mod_factor * q). Must be 1 or 2.
[in]	output_mod_factor	Returns output `result` in [0, output_mod_factor * q). Must be 1 or 2.

◆ GetAVX512Precon32RootOfUnityPowers()

const AlignedVector64<uint64_t>& intel::hexl::NTT::GetAVX512Precon32RootOfUnityPowers ( ) const

inline

Returns 32-bit pre-conditioned AVX512 root of unity powers in bit-reversed order.

◆ GetAVX512Precon52RootOfUnityPowers()

const AlignedVector64<uint64_t>& intel::hexl::NTT::GetAVX512Precon52RootOfUnityPowers ( ) const

inline

Returns 52-bit pre-conditioned AVX512 root of unity powers in bit-reversed order.

◆ GetAVX512Precon64RootOfUnityPowers()

const AlignedVector64<uint64_t>& intel::hexl::NTT::GetAVX512Precon64RootOfUnityPowers ( ) const

inline

Returns 64-bit pre-conditioned AVX512 root of unity powers in bit-reversed order.

◆ GetAVX512RootOfUnityPowers()

const AlignedVector64<uint64_t>& intel::hexl::NTT::GetAVX512RootOfUnityPowers ( ) const

inline

Returns the root of unity powers in bit-reversed order with modifications for use by AVX512 implementation.

◆ GetDegree()

uint64_t intel::hexl::NTT::GetDegree ( ) const

inline

Returns the degree N.

◆ GetInvRootOfUnityPower()

uint64_t intel::hexl::NTT::GetInvRootOfUnityPower ( size_t i )

inline

Returns the inverse root of unity power at bit-reversed index i.

◆ GetInvRootOfUnityPowers()

const AlignedVector64<uint64_t>& intel::hexl::NTT::GetInvRootOfUnityPowers ( ) const

inline

Returns the inverse root of unity powers in bit-reversed order.

◆ GetMinimalRootOfUnity()

uint64_t intel::hexl::NTT::GetMinimalRootOfUnity ( ) const

inline

Returns the minimal 2N'th root of unity.

◆ GetModulus()

uint64_t intel::hexl::NTT::GetModulus ( ) const

inline

Returns the word-sized prime modulus.

◆ GetPrecon32InvRootOfUnityPowers()

const AlignedVector64<uint64_t>& intel::hexl::NTT::GetPrecon32InvRootOfUnityPowers ( ) const

inline

Returns the vector of 32-bit pre-conditioned pre-computed root of unity.

◆ GetPrecon32RootOfUnityPowers()

const AlignedVector64<uint64_t>& intel::hexl::NTT::GetPrecon32RootOfUnityPowers ( ) const

inline

Returns 32-bit pre-conditioned root of unity powers in bit-reversed order.

◆ GetPrecon52InvRootOfUnityPowers()

const AlignedVector64<uint64_t>& intel::hexl::NTT::GetPrecon52InvRootOfUnityPowers ( ) const

inline

Returns the vector of 52-bit pre-conditioned pre-computed root of unity.

◆ GetPrecon64InvRootOfUnityPowers()

const AlignedVector64<uint64_t>& intel::hexl::NTT::GetPrecon64InvRootOfUnityPowers ( ) const

inline

Returns the vector of 64-bit pre-conditioned pre-computed root of unity.

◆ GetPrecon64RootOfUnityPowers()

const AlignedVector64<uint64_t>& intel::hexl::NTT::GetPrecon64RootOfUnityPowers ( ) const

inline

Returns 64-bit pre-conditioned root of unity powers in bit-reversed order.

◆ GetRootOfUnityPower()

uint64_t intel::hexl::NTT::GetRootOfUnityPower ( size_t i )

inline

Returns the root of unity power at bit-reversed index i.

◆ GetRootOfUnityPowers()

const AlignedVector64<uint64_t>& intel::hexl::NTT::GetRootOfUnityPowers ( ) const

inline

Returns the root of unity powers in bit-reversed order.

◆ MaxDegreeBits()

static size_t intel::hexl::NTT::MaxDegreeBits ( )

inlinestatic

Maximum power of 2 in degree.

◆ MaxModulusBits()

static size_t intel::hexl::NTT::MaxModulusBits ( )

inlinestatic

Maximum number of bits in modulus;.

Member Data Documentation

◆ s_default_shift_bits

const size_t intel::hexl::NTT::s_default_shift_bits {64}

static

Default bit shift used in Barrett precomputation.

◆ s_ifma_shift_bits

const size_t intel::hexl::NTT::s_ifma_shift_bits {52}

static

Bit shift used in Barrett precomputation when AVX512-IFMA acceleration is enabled.

◆ s_max_fwd_32_modulus

const size_t intel::hexl::NTT::s_max_fwd_32_modulus {1ULL << (32 - 2)}

static

Maximum modulus to use 32-bit AVX512-DQ acceleration for the forward transform.

◆ s_max_fwd_ifma_modulus

const size_t intel::hexl::NTT::s_max_fwd_ifma_modulus {1ULL << (s_ifma_shift_bits - 2)}

static

Maximum modulus to use AVX512-IFMA acceleration for the forward transform.

◆ s_max_inv_32_modulus

const size_t intel::hexl::NTT::s_max_inv_32_modulus {1ULL << (32 - 1)}

static

Maximum modulus to use 32-bit AVX512-DQ acceleration for the inverse transform.

◆ s_max_inv_ifma_modulus

const size_t intel::hexl::NTT::s_max_inv_ifma_modulus {1ULL << (s_ifma_shift_bits - 1)}

static

Maximum modulus to use AVX512-IFMA acceleration for the inverse transform.

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

ntt.hpp

Classes

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ NTT() [1/5]

◆ ~NTT()

◆ NTT() [2/5]

◆ NTT() [3/5]

◆ NTT() [4/5]

◆ NTT() [5/5]

Member Function Documentation

◆ CheckArguments()

◆ ComputeForward()

◆ ComputeInverse()

◆ GetAVX512Precon32RootOfUnityPowers()

◆ GetAVX512Precon52RootOfUnityPowers()

◆ GetAVX512Precon64RootOfUnityPowers()

◆ GetAVX512RootOfUnityPowers()

◆ GetDegree()

◆ GetInvRootOfUnityPower()

◆ GetInvRootOfUnityPowers()

◆ GetMinimalRootOfUnity()

◆ GetModulus()

◆ GetPrecon32InvRootOfUnityPowers()

◆ GetPrecon32RootOfUnityPowers()

◆ GetPrecon52InvRootOfUnityPowers()

◆ GetPrecon64InvRootOfUnityPowers()

◆ GetPrecon64RootOfUnityPowers()

◆ GetRootOfUnityPower()

◆ GetRootOfUnityPowers()

◆ MaxDegreeBits()

◆ MaxModulusBits()

Member Data Documentation

◆ s_default_shift_bits

◆ s_ifma_shift_bits

◆ s_max_fwd_32_modulus

◆ s_max_fwd_ifma_modulus

◆ s_max_inv_32_modulus

◆ s_max_inv_ifma_modulus