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 usint cycloOrder)

Forward transform.

Parameters

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

  • rootOfUnityTable – the root of unity table.

  • cycloOrder – is the cyclotomic order.

Returns

is the output result of the transform.

VecType ForwardTransform(const VecType &element, const IntType &root, const usint cycloOrder, const ModulusRoot<IntType> &nttModulusRoot)
VecType PadZeros(const VecType &a, const usint 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, usint lo, usint 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(usint 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(usint 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.

  • modulus – is the modulus of the polynomial.

void PreComputePowers(usint 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.

  • modulus – is the modulus of the polynomial ring.

  • root – is the root of unity s.t. root^2m = 1.

void PreComputeRBTable(usint 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.

  • modulus – is the modulus of the polynomial ring.

  • root – is the root of unity s.t. root^2m = 1.

  • bigMod – is the modulus required for the NTT transform.

  • bigRoot – is the root of unity required for the NTT transform.

void Reset()

Reset cached values for the transform to empty.

Public Static Attributes

static std::map<ModulusRoot<IntType>, VecType> m_rootOfUnityTableByModulusRoot
static std::map<ModulusRoot<IntType>, VecType> m_rootOfUnityInverseTableByModulusRoot
static std::map<ModulusRoot<IntType>, VecType> m_powersTableByModulusRoot
static std::map<ModulusRootPair<IntType>, VecType> m_RBTableByModulusRootPair