Template Class BluesteinFFTNat

Page Contents

Template Parameter Order

  1. typename VecType

Class Documentation

template<typename VecType>
class intnat::BluesteinFFTNat

Bluestein Fast Fourier Transform implementation.

Public Functions

VecType ForwardTransform(const VecType &element, const IntType &root, const uint32_t cycloOrder)

Forward transform.

Parameters

  • element – is the element to perform the transform on.

  • root – is the root of unity w.r.t. the modulus of element used to compute the power table.

  • cycloOrder – is the cyclotomic order.

Returns

is the output result of the transform.

VecType ForwardTransform(const VecType &element, const IntType &root, const uint32_t cycloOrder, const ModulusRoot<IntType> &nttModulusRoot)

Forward transform with an explicit NTT modulus and root; all tables for (modulus of element, root), nttModulusRoot and their pair must have been precomputed by the PreCompute* methods.

Parameters

  • element – is the element to perform the transform on; its length must equal cycloOrder.

  • root – is the root of unity w.r.t. the modulus of element used to compute the power table.

  • cycloOrder – is the cyclotomic order.

  • nttModulusRoot – is the (modulus, root of unity) pair of the NTT used internally.

Returns

is the output result of the transform.

VecType PadZeros(const VecType &a, const uint32_t finalSize)
Parameters

  • a – is the input vector to be padded with zeros.

  • finalSize – is the length of the output vector.

Returns

output vector padded with (finalSize - initial size)additional zeros.

VecType Resize(const VecType &a, uint32_t lo, uint32_t hi)
Parameters

  • a – is the input vector to be resized.

  • lo – is lower coefficient index.

  • hi – is higher coefficient index.

Returns

output vector s.t output vector = a[lo]…a[hi].

void PreComputeDefaultNTTModulusRoot(uint32_t cycloOrder, const IntType &modulus)

Precomputes the modulus needed for NTT operation in forward Bluestein transform.

Parameters

  • cycloOrder – is the cyclotomic order of the polynomial.

  • modulus – is the modulus of the polynomial.

void PreComputeRootTableForNTT(uint32_t cycloOrder, const ModulusRoot<IntType> &nttModulusRoot)

Precomputes the root of unity table needed for NTT operation in forward Bluestein transform.

Parameters

  • cycloOrder – is the cyclotomic order of the polynomial ring.

  • nttModulusRoot – is the (modulus, root of unity) pair used for the NTT operation.

void PreComputePowers(uint32_t cycloOrder, const ModulusRoot<IntType> &modulusRoot)

precomputes the powers of root used in forward Bluestein transform.

Parameters

  • cycloOrder – is the cyclotomic order of the polynomial ring.

  • modulusRoot – is the pair (modulus, root) of the polynomial ring’s modulus and a root of unity s.t. root^2m = 1.

void PreComputeRBTable(uint32_t cycloOrder, const ModulusRootPair<IntType> &modulusRootPair)

precomputes the NTT transform of the power of root of unity used in the Bluestein transform.

Parameters

  • cycloOrder – is the cyclotomic order of the polynomial ring.

  • modulusRootPair – is the pair ((modulus, root), (bigMod, bigRoot)), where modulus is the modulus of the polynomial ring, root is the root of unity s.t. root^2m = 1, and bigMod and bigRoot are the modulus and root of unity required for the NTT transform.

void Reset()

Reset cached values for the transform to empty.

Public Static Functions

static inline std::recursive_mutex &CacheMutex()

Mutex guarding every Bluestein/arbitrary-cyclotomic static cache: fills are lazy and the tower loops run in parallel, so lookups must lock as well (references into a std::map stay valid after the lock is released; the map structure does not).

Returns

the shared recursive mutex.

Public Static Attributes

static std::map<ModulusRoot<IntType>, VecType> m_rootOfUnityTableByModulusRoot

map to store the root of unity table with modulus as key.

static std::map<ModulusRoot<IntType>, VecType> m_rootOfUnityInverseTableByModulusRoot

map to store the root of unity inverse table with modulus as key.

static std::map<ModulusRoot<IntType>, VecType> m_powersTableByModulusRoot

map to store the power of roots as a table with modulus + root of unity as key.

static std::map<ModulusRootPair<IntType>, VecType> m_RBTableByModulusRootPair

map to store the forward transform of power table with modulus + root of unity as key.

static std::map<ModulusRoot<IntType>, VecType> m_preconRootOfUnityTableByModulusRoot

Shoup precomputations matching m_rootOfUnityTableByModulusRoot.

static std::map<ModulusRoot<IntType>, VecType> m_preconRootOfUnityInverseTableByModulusRoot

Shoup precomputations matching m_rootOfUnityInverseTableByModulusRoot.