Template Class ChineseRemainderTransformFTTNat

Page Contents

Inheritance Relationships

Base Type

Template Parameter Order

  1. typename VecType

Class Documentation

template<typename VecType>
class intnat::ChineseRemainderTransformFTTNat : public lbcrypto::ChineseRemainderTransformFTTInterface<VecType>

Inheritence diagram for intnat::ChineseRemainderTransformFTTNat:

digraph { graph [bgcolor="#00000000"] node [shape=rectangle style=filled fillcolor="#FFFFFF" font=Helvetica padding=2] edge [color="#1414CE"] "1" [label="intnat::ChineseRemainderTransformFTTNat< VecType >" tooltip="intnat::ChineseRemainderTransformFTTNat< VecType >" fillcolor="#BFBFBF"] "2" [label="lbcrypto::ChineseRemainderTransformFTTInterface< VecType >" tooltip="lbcrypto::ChineseRemainderTransformFTTInterface< VecType >"] "1" -> "2" [dir=forward tooltip="public-inheritance"] }

Collaboration diagram for intnat::ChineseRemainderTransformFTTNat:

digraph { graph [bgcolor="#00000000"] node [shape=rectangle style=filled fillcolor="#FFFFFF" font=Helvetica padding=2] edge [color="#1414CE"] "1" [label="intnat::ChineseRemainderTransformFTTNat< VecType >" tooltip="intnat::ChineseRemainderTransformFTTNat< VecType >" fillcolor="#BFBFBF"] "2" [label="lbcrypto::ChineseRemainderTransformFTTInterface< VecType >" tooltip="lbcrypto::ChineseRemainderTransformFTTInterface< VecType >"] "1" -> "2" [dir=forward tooltip="public-inheritance"] }

Golden Chinese Remainder Transform FFT implementation.

Public Functions

virtual void ForwardTransformToBitReverse(const VecType &element, const IntType &rootOfUnity, const usint CycloOrder, VecType *result)

Copies element into result and calls NumberTheoreticTransform::ForwardTransformToBitReverseInPlace()

Forward Transform in the ring Z_q[X]/(X^n+1) with prime q and power-of-two n s.t. 2n|q-1. Bit reversing indexes.

See also

NumberTheoreticTransform::ForwardTransformToBitReverseInPlace()

Parameters

  • &element – [in] is the input to the transform of type VecType and length n.

  • &rootOfUnity – is the 2n-th root of unity in Z_q. Used to precompute the root of unity tables if needed. If rootOfUnity == 0 or 1, then the result == input.

  • CycloOrder – is 2n, should be a power-of-two or a throw if an error occurs.

  • *result – [out] is the result of the transform, a VecType should be of the same size as input or a throw of error occurs.

virtual void ForwardTransformToBitReverseInPlace(const IntType &rootOfUnity, const usint CycloOrder, VecType *element)

In-place Forward Transform in the ring Z_q[X]/(X^n+1) with prime q and power-of-two n s.t. 2n|q-1. Bit reversing indexes.

See also

NumberTheoreticTransform::ForwardTransformToBitReverseInPlace()

Parameters

  • &rootOfUnity – is the 2n-th root of unity in Z_q. Used to precompute the root of unity tables if needed. If rootOfUnity == 0 or 1, then the result == input.

  • CycloOrder – is 2n, should be a power-of-two or a throw if an error occurs.

  • &element – [inout] is the input to the transform of type VecType and length n.

Returns

none

virtual void InverseTransformFromBitReverse(const VecType &element, const IntType &rootOfUnity, const usint CycloOrder, VecType *result)

Copies element into result and calls NumberTheoreticTransform::InverseTransformFromBitReverseInPlace()

Inverse Transform in the ring Z_q[X]/(X^n+1) with prime q and power-of-two n s.t. 2n|q-1. Bit reversing indexes.

See also

NumberTheoreticTransform::InverseTransformFromBitReverseInPlace()

Parameters

  • &element[in] – is the input to the transform of type VecType and length n.

  • &rootOfUnity – is the 2n-th root of unity in Z_q. Used to precompute the root of unity tables if needed. If rootOfUnity == 0 or 1, then the result == input.

  • CycloOrder – is 2n, should be a power-of-two or a throw if an error occurs.

  • *result – [out] is the result of the transform, a VecType should be of the same size as input or a throw if an error occurs.

Returns

none

virtual void InverseTransformFromBitReverseInPlace(const IntType &rootOfUnity, const usint CycloOrder, VecType *element)

In-place Inverse Transform in the ring Z_q[X]/(X^n+1) with prime q and power-of-two n s.t. 2n|q-1. Bit reversing indexes.

See also

NumberTheoreticTransform::InverseTransformFromBitReverseInPlace()

Parameters

  • &rootOfUnity – is the 2n-th root of unity in Z_q. Used to precompute the root of unity tables if needed. If rootOfUnity == 0 or 1, then the result == input.

  • CycloOrder – is 2n, should be a power-of-two or a throw if an error occurs.

  • &element – [inout] is the input/output of the transform of type VecType and length n.

Returns

none

virtual void PreCompute(const IntType &rootOfUnity, const usint CycloOrder, const IntType &modulus)

Precomputation of root of unity tables for transforms in the ring Z_q[X]/(X^n+1)

Parameters

  • &rootOfUnity – is the 2n-th root of unity in Z_q. Used to precompute the root of unity tables if needed. If rootOfUnity == 0 or 1, then the result == input.

  • CycloOrder – is a power-of-two, equal to 2n.

  • modulus – is q, the prime modulus

virtual void PreCompute(std::vector<IntType> &rootOfUnity, const usint CycloOrder, std::vector<IntType> &moduliChain)

Precomputation of root of unity tables for transforms in the ring Z_q[X]/(X^n+1)

Parameters

  • &rootOfUnity – is the 2n-th root of unity in Z_q. Used to precompute the root of unity tables if needed. If rootOfUnity == 0 or 1, then the result == input.

  • CycloOrder – is a power-of-two, equal to 2n.

  • &moduliChain – is the vector of prime moduli qi such that 2n|qi-1

virtual void Reset()

Reset cached values for the root of unity tables to empty.

Public Static Attributes

static std::map<IntType, VecType> m_cycloOrderInverseTableByModulus

map to store the cyclo order inverse with modulus as a key For inverse FTT, we also need m_cycloOrderInversePreconTableByModulus (this is to use an N-size NTT for FTT instead of 2N-size NTT).

static std::map<IntType, VecType> m_cycloOrderInversePreconTableByModulus

map to store the cyclo order inverse preconditioned with modulus as a key Shoup’s precomputation of above m_cycloOrderInverseTableByModulus

static std::map<IntType, VecType> m_rootOfUnityReverseTableByModulus

map to store the forward roots of Unity for NTT, with bits reversed, with modulus as a key (aka twiddle factors)

static std::map<IntType, VecType> m_rootOfUnityInverseReverseTableByModulus

map to store inverse roots of unity for iNTT, with bits reversed, with modulus as a key (aka inverse twiddle factors)

static std::map<IntType, VecType> m_rootOfUnityPreconReverseTableByModulus

map to store Shoup’s precomputations of forward roots of unity for NTT, with bits reversed, with modulus as a key

static std::map<IntType, VecType> m_rootOfUnityInversePreconReverseTableByModulus

map to store Shoup’s precomputations of inverse rou for iNTT, with bits reversed, with modulus as a key