NTL Backend API

This page exposes OpenFHE’s extensions in namespace NTL. These classes are only compiled when OpenFHE is configured with WITH_NTL, and the documentation build defines that macro so Doxygen can extract the guarded declarations.

Page Contents

Namespace

namespace NTL

The namespace of this code

The namespace of NTL

Typedefs

using BigVector = myVecP<BigInteger>
template<typename IntType>
using ModulusRoot = std::pair<IntType, IntType>
template<typename IntType>
using ModulusRootPair = std::pair<ModulusRoot<IntType>, ModulusRoot<IntType>>
using BigInteger = myZZ

Functions

std::ostream &operator<<(std::ostream &os, const myZZ &ptr_obj)
template<typename myT>
class myVecP : public NTL::Vec<myT>, public lbcrypto::BigVectorInterface<myVecP<myT>, myT>, public lbcrypto::Serializable
#include <mubintvecntl.h>

The class for representing vectors of ubint with associated modulo math.

template<typename VecType>
class NumberTheoreticTransformNtl
#include <transformntl.h>

Number Theoretic Transform implementation.

template<typename VecType>
class ChineseRemainderTransformFTTNtl : public lbcrypto::ChineseRemainderTransformFTTInterface<VecType>
#include <transformntl.h>

Golden Chinese Remainder Transform FFT implementation.

template<typename VecType>
class BluesteinFFTNtl
#include <transformntl.h>

Bluestein Fast Fourier Transform implementation.

template<typename VecType>
class ChineseRemainderTransformArbNtl : public lbcrypto::ChineseRemainderTransformArbInterface<VecType>
#include <transformntl.h>

Chinese Remainder Transform for arbitrary cyclotomics.

template<uint32_t N>
struct Log2
#include <ubintntl.h>

Struct to find log value of N. Needed in the preprocessing step of ubint to determine bitwidth.

Template Parameters

N – bitwidth.

template<>
struct Log2<2>
#include <ubintntl.h>

Struct to find log 2 value of N. Base case for recursion. Needed in the preprocessing step of ubint to determine bitwidth.

class myZZ : public NTL::ZZ, public lbcrypto::BigIntegerInterface<myZZ>

Integer and Vector Types

class NTL::myZZ : public NTL::ZZ, public lbcrypto::BigIntegerInterface<myZZ>

Public Functions

myZZ()

Default constructor.

myZZ(const NTL::ZZ &val)

Copy constructor.

Parameters

val – is the ZZ to be copied.

myZZ(NTL::ZZ &&val)

Move constructor.

Parameters

val – is the ZZ to be moved.

explicit myZZ(const std::string &strval)

Constructor from a string.

Parameters

strval – is the initial integer represented as a string.

inline explicit myZZ(const char *strval)
myZZ(uint64_t val)

Constructor from an unsigned integer.

Parameters

val – is the initial integer represented as a uint64_t.

inline myZZ(int val)

Constructors from smaller basic types

Parameters

val – is the initial integer represented as a basic integer type.

inline myZZ(uint32_t val)
inline myZZ(long val)
inline myZZ(long long val)
template<typename T, typename std::enable_if<!std::is_same<T, int>::value && !std::is_same<T, uint32_t>::value && !std::is_same<T, uint64_t>::value && !std::is_same<T, long>::value && !std::is_same<T, long long>::value && !std::is_same<T, const std::string>::value && !std::is_same<T, const char*>::value && !std::is_same<T, const char>::value && !std::is_same<T, myZZ>::value && !std::is_same<T, double>::value, bool>::type = true>
inline myZZ(const T &val)

Constructor from a NativeInteger

Parameters

val – is the initial integer represented as a native integer.

myZZ(double val) __attribute__((deprecated("Cannot const ruct from a double")))

Constructor from double is not permitted

Parameters

val –

myZZ &operator=(const myZZ &val)

Copy assignment operator

Parameters

val – is the myZZ to be assigned from.

Returns

assigned myZZ ref.

inline const myZZ &operator=(std::string strval)

Assignment operator from string

Parameters

strval – is the string to be assigned from

Returns

the assigned myZZ ref.

inline myZZ &operator=(uint64_t val)

Assignment operator from unsigned integer

Parameters

val – is the unsigned integer to be assigned from.

Returns

the assigned myZZ ref.

void SetValue(const std::string &strval)

Basic set method for setting the value of a myZZ

Parameters

strval – is the string representation of the myZZ to be copied.

void SetValue(const myZZ &val)

Basic set method for setting the value of a myZZ

Parameters

val – is the myZZ whose value is to be assigned.

inline void SetIdentity()
inline myZZ Add(const myZZ &b) const

Addition operation.

Parameters

b – is the value to add.

Returns

result of the addition operation.

inline myZZ &AddEq(const myZZ &b)

Addition operation. In-place variant.

Parameters

b – is the value to add.

Returns

result of the addition operation.

inline myZZ Sub(const myZZ &b) const

Subtraction operation. Note that in Sub we return 0, if a<b

Parameters

b – is the value to subtract.

Returns

is the result of the subtraction operation.

inline myZZ &SubEq(const myZZ &b)

Subtraction operation. In-place variant. Note that in Sub we return 0, if a<b

Parameters

b – is the value to subtract.

Returns

is the result of the subtraction operation.

inline myZZ Mul(const myZZ &b) const

Multiplication operation.

Parameters

b – is the value to multiply with.

Returns

is the result of the multiplication operation.

inline myZZ &MulEq(const myZZ &b)

Multiplication operation. In-place variant.

Parameters

b – is the value to multiply with.

Returns

is the result of the multiplication operation.

inline myZZ DividedBy(const myZZ &b) const

Division operation.

Parameters

b – is the value to divide by.

Returns

is the result of the division operation.

inline myZZ &DividedByEq(const myZZ &b)

Division operation. In-place variant.

Parameters

b – is the value to divide by.

Returns

is the result of the division operation.

inline myZZ Exp(const uint32_t p) const

Exponentiation operation. Returns x^p.

Parameters

p – the exponent.

Returns

is the result of the exponentiation operation.

inline myZZ &ExpEq(const uint32_t p)

Exponentiation operation. Returns x^p. In-place variant.

Parameters

p – the exponent.

Returns

is the result of the exponentiation operation.

myZZ MultiplyAndRound(const myZZ &p, const myZZ &q) const

Multiply and Rounding operation. Returns [x*p/q] where [] is the rounding operation.

Parameters

  • p – is the numerator to be multiplied.

  • q – is the denominator to be divided.

Returns

is the result of multiply and round operation.

myZZ &MultiplyAndRoundEq(const myZZ &p, const myZZ &q)

Multiply and Rounding operation. Returns [x*p/q] where [] is the rounding operation. In-place variant.

Parameters

  • p – is the numerator to be multiplied.

  • q – is the denominator to be divided.

Returns

is the result of multiply and round operation.

myZZ DivideAndRound(const myZZ &q) const

Divide and Rounding operation. Returns [x/q] where [] is the rounding operation.

Parameters

q – is the denominator to be divided.

Returns

is the result of divide and round operation.

myZZ &DivideAndRoundEq(const myZZ &q)

Divide and Rounding operation. Returns [x/q] where [] is the rounding operation. In-place variant.

Parameters

q – is the denominator to be divided.

Returns

is the result of divide and round operation.

inline myZZ Mod(const myZZ &modulus) const

Naive modulus operation.

Parameters

modulus – is the modulus to perform.

Returns

is the result of the modulus operation.

inline myZZ &ModEq(const myZZ &modulus)

Naive modulus operation. In-place variant.

Parameters

modulus – is the modulus to perform.

Returns

is the result of the modulus operation.

inline myZZ ComputeMu() const

Pre-computes the mu factor that is used in Barrett modulo reduction

Returns

the value of mu

inline myZZ Mod(const myZZ &modulus, const myZZ &mu) const

Barrett modulus operation. Implements generalized Barrett modular reduction algorithm. Uses one precomputed value of mu.

Parameters

  • modulus – is the modulus to perform.

  • mu – is the Barrett value.

Returns

is the result of the modulus operation.

inline myZZ &ModEq(const myZZ &modulus, const myZZ &mu)

Barrett modulus operation. In-place variant. Implements generalized Barrett modular reduction algorithm. Uses one precomputed value of mu.

Parameters

  • modulus – is the modulus to perform.

  • mu – is the Barrett value.

Returns

is the result of the modulus operation.

inline myZZ ModAdd(const myZZ &b, const myZZ &modulus) const

Modulus addition operation.

Parameters

  • b – is the scalar to add.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus addition operation.

inline myZZ &ModAddEq(const myZZ &b, const myZZ &modulus)

Modulus addition operation. In-place variant.

Parameters

  • b – is the scalar to add.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus addition operation.

inline myZZ ModAddFast(const myZZ &b, const myZZ &modulus) const

Modulus addition where operands are < modulus.

Parameters

  • b – is the scalar to add.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus addition operation.

inline myZZ &ModAddFastEq(const myZZ &b, const myZZ &modulus)

Modulus addition where operands are < modulus. In-place variant.

Parameters

  • b – is the scalar to add.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus addition operation.

inline myZZ ModAdd(const myZZ &b, const myZZ &modulus, const myZZ &mu) const

Barrett modulus addition operation.

Parameters

  • b – is the scalar to add.

  • modulus – is the modulus to perform operations with.

  • mu – is the Barrett value.

Returns

is the result of the modulus addition operation.

inline myZZ &ModAddEq(const myZZ &b, const myZZ &modulus, const myZZ &mu)

Barrett modulus addition operation. In-place variant.

Parameters

  • b – is the scalar to add.

  • modulus – is the modulus to perform operations with.

  • mu – is the Barrett value.

Returns

is the result of the modulus addition operation.

inline myZZ ModSub(const myZZ &b, const myZZ &modulus) const

Modulus subtraction operation. NOTE ModSub needs to return signed modulus (i.e. -1/2..q/2) in order to be consistent with BE 2

Parameters

  • b – is the scalar to subtract.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus subtraction operation.

inline myZZ &ModSubEq(const myZZ &b, const myZZ &modulus)

Modulus subtraction operation. In-place variant. NOTE ModSub needs to return signed modulus (i.e. -1/2..q/2) in order to be consistent with BE 2

Parameters

  • b – is the scalar to subtract.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus subtraction operation.

inline myZZ ModSubFast(const myZZ &b, const myZZ &modulus) const

Modulus subtraction where operands are < modulus.

Parameters

  • b – is the scalar to subtract.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus subtraction operation.

inline myZZ &ModSubFastEq(const myZZ &b, const myZZ &modulus)

Modulus subtraction where operands are < modulus. In-place variant.

Parameters

  • b – is the scalar to subtract.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus subtraction operation.

inline myZZ ModSub(const myZZ &b, const myZZ &modulus, const myZZ &mu) const

Barrett modulus subtraction operation.

Parameters

  • b – is the scalar to subtract.

  • modulus – is the modulus to perform operations with.

  • mu – is the Barrett value.

Returns

is the result of the modulus subtraction operation.

inline myZZ &ModSubEq(const myZZ &b, const myZZ &modulus, const myZZ &mu)

Barrett modulus subtraction operation. In-place variant.

Parameters

  • b – is the scalar to subtract.

  • modulus – is the modulus to perform operations with.

  • mu – is the Barrett value.

Returns

is the result of the modulus subtraction operation.

inline myZZ ModMul(const myZZ &b, const myZZ &modulus) const

Modulus multiplication operation.

Parameters

  • b – is the scalar to multiply.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus multiplication operation.

inline myZZ &ModMulEq(const myZZ &b, const myZZ &modulus)

Modulus multiplication operation. In-place variant.

Parameters

  • b – is the scalar to multiply.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus multiplication operation.

inline myZZ ModMul(const myZZ &b, const myZZ &modulus, const myZZ &mu) const

Barrett modulus multiplication.

Parameters

  • b – is the scalar to multiply.

  • modulus – is the modulus to perform operations with.

  • mu – is the Barrett value.

Returns

is the result of the modulus multiplication operation.

inline myZZ &ModMulEq(const myZZ &b, const myZZ &modulus, const myZZ &mu)

Barrett modulus multiplication. In-place variant.

Parameters

  • b – is the scalar to multiply.

  • modulus – is the modulus to perform operations with.

  • mu – is the Barrett value.

Returns

is the result of the modulus multiplication operation.

inline myZZ ModMulFast(const myZZ &b, const myZZ &modulus) const

Modulus multiplication that assumes the operands are < modulus.

Parameters

  • b – is the scalar to multiply.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus multiplication operation.

inline myZZ &ModMulFastEq(const myZZ &b, const myZZ &modulus)

Modulus multiplication that assumes the operands are < modulus. In-place variant.

Parameters

  • b – is the scalar to multiply.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus multiplication operation.

inline myZZ ModMulFast(const myZZ &b, const myZZ &modulus, const myZZ &mu) const

Barrett modulus multiplication that assumes the operands are < modulus.

Parameters

  • b – is the scalar to multiply.

  • modulus – is the modulus to perform operations with.

  • mu – is the Barrett value.

Returns

is the result of the modulus multiplication operation.

inline myZZ &ModMulFastEq(const myZZ &b, const myZZ &modulus, const myZZ &mu)

Barrett modulus multiplication that assumes the operands are < modulus. In-place variant.

Parameters

  • b – is the scalar to multiply.

  • modulus – is the modulus to perform operations with.

  • mu – is the Barrett value.

Returns

is the result of the modulus multiplication operation.

inline myZZ ModMulFastConst(const myZZ &b, const myZZ &modulus, const myZZ &bInv) const
inline myZZ &ModMulFastConstEq(const myZZ &b, const myZZ &modulus, const myZZ &bInv)
inline myZZ ModExp(const myZZ &b, const myZZ &modulus) const

Modulus exponentiation operation.

Parameters

  • b – is the exponent.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus exponentiation operation.

inline myZZ &ModExpEq(const myZZ &b, const myZZ &modulus)

Modulus exponentiation operation. In-place variant.

Parameters

  • b – is the exponent.

  • modulus – is the modulus to perform operations with.

Returns

is the result of the modulus exponentiation operation.

inline myZZ ModInverse(const myZZ &modulus) const

Modulus inverse operation.

Parameters

modulus – is the modulus to perform.

Returns

is the result of the modulus inverse operation.

inline myZZ &ModInverseEq(const myZZ &modulus)

Modulus inverse operation. In-place variant.

Parameters

modulus – is the modulus to perform.

Returns

is the result of the modulus inverse operation.

inline myZZ LShift(uint16_t shift) const

Left shift operation.

Parameters

shift – # of bits.

Returns

result of the shift operation.

inline myZZ &LShiftEq(uint16_t shift)

Left shift operation. In-place variant.

Parameters

shift – # of bits.

Returns

result of the shift operation.

inline myZZ RShift(uint16_t shift) const

Right shift operation.

Parameters

shift – # of bits.

Returns

result of the shift operation.

inline myZZ &RShiftEq(uint16_t shift)

Right shift operation. In-place variant.

Parameters

shift – # of bits.

Returns

result of the shift operation.

inline int Compare(const myZZ &a) const
template<typename T = BasicInteger>
inline T ConvertToInt() const
uint64_t ConvertToUint64() const
double ConvertToDouble() const
uint32_t GetMSB() const
inline uint32_t GetLengthForBase(uint32_t base) const

Get the number of digits using a specific base - support for arbitrary base may be needed.

Parameters

base – is the base with which to determine length in.

Returns

the length of the representation in a specific base.

uint32_t GetDigitAtIndexForBase(uint32_t index, uint32_t base) const

Get the integer value of the of a subfield of bits. Where the length of the field is specifice by a power of two base Warning: only power-of-2 bases are currently supported. Example: for number 83, index 2 and base 4 we have: 

                    index:0,1,2,3
83 &#8212;base 4 decomposition–> (3,0,1,1) &#8212;at index 2–> 1

The return number is 1.

Parameters

  • index – is the bit location (lsb)

  • base – such that log2(base)+1 is the bitwidth of the subfield

Returns

the unsigned integer value of the subfield

uint32_t GetBitRangeAtIndex(uint32_t index, uint32_t length) const

Gets a subset of bits of a given length with LSB at specified index. optimized for speed in backend 6

Parameters

  • index – of the set of bit to get. LSB=1

  • length – of the set of bits to get. LSB=1

Returns

resulting unsigned in formed by set of bits.

uint8_t GetBitAtIndex(uint32_t index) const

Gets the bit at the specified index.

Parameters

index – of the bit to get. LSB=1

Returns

resulting bit.

const std::string ToString() const
inline std::string GetInternalRepresentation(void) const

Gets a copy of the internal limb storage Used primarily for debugging

Returns

string with the space-separated limb values, least significant limb first

template<class Archive>
inline std::enable_if<!cereal::traits::is_text_archive<Archive>::value, void>::type save(Archive &ar, std::uint32_t const version) const

SERIALIZATION.

template<class Archive>
inline std::enable_if<cereal::traits::is_text_archive<Archive>::value, void>::type save(Archive &ar, std::uint32_t const version) const
template<class Archive>
inline std::enable_if<!cereal::traits::is_text_archive<Archive>::value, void>::type load(Archive &ar, std::uint32_t const version)
template<class Archive>
inline std::enable_if<cereal::traits::is_text_archive<Archive>::value, void>::type load(Archive &ar, std::uint32_t const version)
inline std::string SerializedObjectName() const

Public Static Functions

static myZZ FromBinaryString(const std::string &bitString)

Convert a string representation of a binary number to a myZZ. Note: needs renaming to a generic form since the variable type name is embedded in the function name. Suggest FromBinaryString()

Parameters

bitString – the binary num in string.

Returns

the number represented as a myZZ.

static const myZZ &zero()
static inline myZZ Allocator()

A zero allocator that is called by the Matrix class. It is used to initialize a Matrix of myZZ objects.

static inline const std::string IntegerTypeName()
static inline uint32_t SerializedVersion()

Public Static Attributes

static const uint32_t m_log2LimbBitLength = Log2<NTL_ZZ_NBITS>::value

Friends

friend std::ostream &operator<<(std::ostream &os, const myZZ &ptr_obj)
template<typename myT>
class NTL::myVecP : public NTL::Vec<myT>, public lbcrypto::BigVectorInterface<myVecP<myT>, myT>, public lbcrypto::Serializable

The class for representing vectors of ubint with associated modulo math.

Public Functions

inline myVecP()
inline explicit myVecP(const size_t length)
inline myVecP(INIT_SIZE_TYPE, const long length)
explicit myVecP(const myVecP<myT> &a)
myVecP(myVecP<myT> &&a)
myVecP(const long n, const myT &q)
inline myVecP(uint32_t n, const myT &q, const myT &v)
myVecP(const long n, const myT &q, std::initializer_list<std::string> rhs)
myVecP(const long n, const myT &q, std::initializer_list<uint64_t> rhs)
myVecP(const myVecP<myT> &a, const myT &q)
myVecP(size_t n, const std::string &sq)
myVecP(const myVecP<myT> &a, const std::string &sq)
myVecP(size_t n, uint64_t q)
myVecP(const myVecP<myT> &a, const uint64_t q)
explicit myVecP(std::vector<std::string> &s)
myVecP(std::vector<std::string> &s, const myT &q)
myVecP(std::vector<std::string> &s, const char *sq)
myVecP(std::vector<std::string> &s, const uint64_t q)
void clear(myVecP &x)
inline ~myVecP()
myVecP &operator=(const myVecP &a)
myVecP &operator=(myVecP &&a)
myVecP &operator=(std::initializer_list<uint64_t> rhs)
myVecP &operator=(std::initializer_list<int32_t> rhs)
myVecP &operator=(std::initializer_list<std::string> rhs)
myVecP &operator=(uint64_t rhs)
inline myT &at(size_t i)
inline const myT &at(size_t i) const
inline myT &operator[](size_t idx)
inline const myT &operator[](size_t idx) const
inline void push_back(const myT &a)
void SwitchModulus(const myT &newModulus)
void LazySwitchModulus(const myT &newModulus)
inline myVecP &MultAccEqNoCheck(const myVecP &a, const myVecP &b)
inline myT &MultAccEqNoCheck(const myVecP &v, const myT &i)
inline bool isModulusSet(void) const
inline bool SameModulus(const myVecP &a) const
inline void SetModulus(uint64_t value)
inline void SetModulus(const myT &value)
inline void SetModulus(const std::string &value)
inline void SetModulus(const myVecP &value)
inline const myT &GetModulus() const
inline int CopyModulus(const myVecP &rhs)
inline size_t GetLength(void) const
inline void resize(size_t n)
myVecP Mod(const myT &b) const

Vector modulus operator.

Parameters

b – is the modulus to perform on the current vector entries.

Returns

is the result of the modulus operation on current vector.

myVecP &ModEq(const myT &b)

Vector modulus operator. In-place variant.

Parameters

b – is the modulus to perform on the current vector entries.

Returns

is the result of the modulus operation on current vector.

inline myVecP ModAdd(const myT &b) const

Scalar-to-vector modulus addition operation.

Parameters

b – is the scalar to perform operation with.

Returns

is the result of the modulus addition operation.

inline myVecP &ModAddEq(const myT &b)

Scalar-to-vector modulus addition operation. In-place variant.

Parameters

b – is the scalar to perform operation with.

Returns

is the result of the modulus addition operation.

myVecP ModAddAtIndex(size_t i, const myT &b) const

Scalar modulus addition at a particular index.

Parameters

  • i – is the index of the entry to add.

  • b – is the scalar to add.

Returns

is the result of the modulus addition operation.

myVecP &ModAddAtIndexEq(size_t i, const myT &b)

Scalar modulus addition at a particular index. In-place variant.

Parameters

  • i – is the index of the entry to add.

  • b – is the scalar to add.

Returns

is the result of the modulus addition operation.

inline myVecP ModAdd(const myVecP &b) const

Vector component wise modulus addition.

Parameters

b – is the vector to perform operation with.

Returns

is the result of the component wise modulus addition operation.

inline myVecP &ModAddEq(const myVecP &b)

Vector component wise modulus addition. In-place variant.

Parameters

b – is the vector to perform operation with.

Returns

is the result of the component wise modulus addition operation.

inline myVecP &ModAddNoCheckEq(const myVecP &b)
inline void modadd_p(myVecP &x, const myVecP &a, const myVecP &b) const

procedural version for the vector component wise modulus addition operation.

inline myVecP ModSub(const myT &b) const

Scalar-from-vector modulus subtraction operation.

Parameters

b – is the scalar to perform operation with.

Returns

is the result of the modulus subtraction operation.

inline myVecP &ModSubEq(const myT &b)

Scalar-from-vector modulus subtraction operation. In-place variant.

Parameters

b – is the scalar to perform operation with.

Returns

is the result of the modulus subtraction operation.

inline myVecP ModSub(const myVecP &b) const

Vector component wise modulus subtraction.

Parameters

b – is the vector to perform operation with.

Returns

is the result of the component wise modulus subtraction operation.

inline myVecP &ModSubEq(const myVecP &b)

Vector component wise modulus subtraction. In-place variant.

Parameters

b – is the vector to perform operation with.

Returns

is the result of the component wise modulus subtraction operation.

void modsub_p(myVecP &x, const myVecP &a, const myVecP &b) const

procedural version for the vector component wise modulus subtraction operation.

inline myVecP ModMul(const myT &b) const

Scalar-to-vector modulus multiplication operation.

Parameters

b – is the scalar to perform operation with.

Returns

is the result of the modulus multiplication operation.

inline myVecP &ModMulEq(const myT &b)

Scalar-to-vector modulus multiplication operation. In-place variant.

Parameters

b – is the scalar to perform operation with.

Returns

is the result of the modulus multiplication operation.

inline myVecP ModMul(const myVecP &b) const

Vector component wise modulus multiplication.

Parameters

b – is the vector to perform operation with.

Returns

is the result of the component wise modulus multiplication operation.

inline myVecP &ModMulEq(const myVecP &b)

Vector component wise modulus multiplication. In-place variant.

Parameters

b – is the vector to perform operation with.

Returns

is the result of the component wise modulus multiplication operation.

inline myVecP &ModMulNoCheckEq(const myVecP &b)
inline void modmul_p(myVecP &x, const myVecP &a, const myVecP &b) const

procedural version for the vector component wise modulus multiplication operation.

myVecP ModExp(const myT &b) const

Scalar modulus exponentiation operation.

Parameters

b – is the scalar to perform operation with.

Returns

is the result of the modulus exponentiation operation.

myVecP &ModExpEq(const myT &b)

Scalar modulus exponentiation operation. In-place variant.

Parameters

b – is the scalar to perform operation with.

Returns

is the result of the modulus exponentiation operation.

myVecP ModInverse() const

Modulus inverse operation.

Returns

is the result of the component wise modulus inverse operation.

myVecP &ModInverseEq()

Modulus inverse operation. In-place variant.

Returns

is the result of the component wise modulus inverse operation.

myVecP ModByTwo() const

Modulus 2 operation, also a least significant bit.

Returns

is the result of the component wise modulus 2 operation, also a least significant bit.

myVecP &ModByTwoEq()

Modulus 2 operation, also a least significant bit. In-place variant.

Returns

is the result of the component wise modulus 2 operation, also a least significant bit.

myVecP MultiplyAndRound(const myT &p, const myT &q) const

Multiply and Rounding operation. Returns [x*p/q] where [] is the rounding operation.

Parameters

  • p – is the numerator to be multiplied.

  • q – is the denominator to be divided.

Returns

is the result of multiply and round operation.

myVecP &MultiplyAndRoundEq(const myT &p, const myT &q)

Multiply and Rounding operation. Returns [x*p/q] where [] is the rounding operation. In-place variant.

Parameters

  • p – is the numerator to be multiplied.

  • q – is the denominator to be divided.

Returns

is the result of multiply and round operation.

myVecP DivideAndRound(const myT &q) const

Divide and Rounding operation. Returns [x/q] where [] is the rounding operation.

Parameters

q – is the denominator to be divided.

Returns

is the result of divide and round operation.

myVecP &DivideAndRoundEq(const myT &q)

Divide and Rounding operation. Returns [x/q] where [] is the rounding operation. In-place variant.

Parameters

q – is the denominator to be divided.

Returns

is the result of divide and round operation.

myVecP GetDigitAtIndexForBase(size_t index, uint32_t base) const

Digit vector at a specific index for all entries for a given number base. Warning: only power-of-2 bases are currently supported. Example: for vector (83, 1, 45), index 2 and base 4 we have: 

                      index:0,1,2,3
|83| |3,0,1,1| |1| |1 | &#8212;base 4 decomposition–> |1,0,0,0| &#8212;at index 2–> |0| |45| |1,3,2,0| |2|

The return vector is (1,0,2)

Parameters

  • index – is the index to return the digit from in all entries.

  • base – is the base to use for the operation.

Returns

is the digit at a specific index for all entries for a given number base

template<class Archive>
inline std::enable_if<!cereal::traits::is_text_archive<Archive>::value, void>::type save(Archive &ar, std::uint32_t const version) const
template<class Archive>
inline std::enable_if<cereal::traits::is_text_archive<Archive>::value, void>::type save(Archive &ar, std::uint32_t const version) const
template<class Archive>
inline std::enable_if<!cereal::traits::is_text_archive<Archive>::value, void>::type load(Archive &ar, std::uint32_t const version)
template<class Archive>
inline std::enable_if<cereal::traits::is_text_archive<Archive>::value, void>::type load(Archive &ar, std::uint32_t const version)
inline virtual std::string SerializedObjectName() const

Returns the name identifying the derived class in serialized form; every serializable class provides it.

Returns

the serialized object name

Public Static Functions

static inline myVecP Single(const myT &val, const myT &modulus)
static inline uint32_t SerializedVersion()

Protected Functions

inline bool IndexCheck(size_t index) const

Friends

inline friend std::ostream &operator<<(std::ostream &os, const myVecP<myT> &ptr_obj)

ostream operator to output vector values to console

Parameters

  • os – is the std ostream object.

  • ptr_obj – is the myVecP object to be printed.

Returns

std ostream object which captures the vector values.

Number Theoretic Transform Types

template<typename VecType>
class NTL::NumberTheoreticTransformNtl

Number Theoretic Transform implementation.

Public Functions

void ForwardTransformIterative(const VecType &element, const VecType &rootOfUnityTable, VecType *result)

Forward transform in the ring Z_q[X]/(X^n-1).

Parameters

  • element – is the input to the transform of type VecType and length n s.t. n|q-1.

  • rootOfUnityTable – is the table with the root of unity powers.

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

void InverseTransformIterative(const VecType &element, const VecType &rootOfUnityInverseTable, VecType *result)

Inverse transform in the ring Z_q[X]/(X^n-1) with prime q and power-of-two n s.t. n|q-1.

Parameters

  • element – is the input to the transform of type VecType and length n.

  • rootOfUnityInverseTable – is the table with the inverse n-th root of unity powers.

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

void ForwardTransformToBitReverse(const VecType &element, const VecType &rootOfUnityTable, VecType *result)

Copies element into result and calls 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. [Algorithm 1 in https://eprint.iacr.org/2016/504.pdf]

See also

ForwardTransformToBitReverseInPlace()

Parameters

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

  • rootOfUnityTable – is the table with the n-th root of unity powers in bit reverse order.

  • 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.

void ForwardTransformToBitReverseInPlace(const VecType &rootOfUnityTable, 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. [Algorithm 1 in https://eprint.iacr.org/2016/504.pdf]

Parameters

  • rootOfUnityTable – is the table with the n-th root of unity powers in bit reverse order.

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

void ForwardTransformToBitReverse(const VecType &element, const VecType &rootOfUnityTable, const VecType &preconRootOfUnityTable, VecType *result)

Copies element into result and calls 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. The method works for the NativeInteger case based on NTL’s modular multiplication. [Algorithm 1 in https://eprint.iacr.org/2016/504.pdf]

See also

ForwardTransformToBitReverseInPlace()

Parameters

  • element – is the input to the transform of type VecType and length n.

  • rootOfUnityTable – is the table with the root of unity powers in bit reverse order.

  • preconRootOfUnityTable – is NTL-specific precomputations for optimized NativeInteger modulo multiplications.

  • 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.

void ForwardTransformToBitReverseInPlace(const VecType &rootOfUnityTable, const VecType &preconRootOfUnityTable, 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. The method works for the NativeInteger case based on NTL’s modular multiplication. [Algorithm 1 in https://eprint.iacr.org/2016/504.pdf]

Parameters

  • rootOfUnityTable – is the table with the root of unity powers in bit reverse order.

  • preconRootOfUnityTable – is NTL-specific precomputations for optimized NativeInteger modulo multiplications.

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

void InverseTransformFromBitReverse(const VecType &element, const VecType &rootOfUnityInverseTable, const IntType &cycloOrderInv, VecType *result)

Copies element into result and calls 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. [Algorithm 2 in https://eprint.iacr.org/2016/504.pdf]

See also

InverseTransformFromBitReverseInPlace()

Parameters

  • element – is the input to the transform of type VecType and length n.

  • rootOfUnityInverseTable – is the table with the inverse 2n-th root of unity powers in bit reverse order.

  • cycloOrderInv – is inverse of n modulo q

  • 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.

void InverseTransformFromBitReverseInPlace(const VecType &rootOfUnityInverseTable, const IntType &cycloOrderInv, 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. [Algorithm 2 in https://eprint.iacr.org/2016/504.pdf]

Parameters

  • rootOfUnityInverseTable – is the table with the inverse 2n-th root of unity powers in bit reverse order.

  • cycloOrderInv – is inverse of n modulo q

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

void InverseTransformFromBitReverse(const VecType &element, const VecType &rootOfUnityInverseTable, const VecType &preconRootOfUnityInverseTable, const IntType &cycloOrderInv, const IntType &preconCycloOrderInv, VecType *result)

Copies element into result and calls 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. The method works for the NativeInteger case based on NTL’s modular multiplication. [Algorithm 2 in https://eprint.iacr.org/2016/504.pdf]

See also

InverseTransformFromBitReverseInPlace()

Parameters

  • element – is the input to the transform of type VecType and length n.

  • rootOfUnityInverseTable – is the table with the inverse 2n-th root of unity powers in bit reverse order.

  • preconRootOfUnityInverseTable – is NTL-specific precomputations for optimized NativeInteger modulo multiplications.

  • cycloOrderInv – is inverse of n modulo q

  • preconCycloOrderInv – is NTL-specific precomputations for optimized NativeInteger modulo multiplications.

  • 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.

void InverseTransformFromBitReverseInPlace(const VecType &rootOfUnityInverseTable, const VecType &preconRootOfUnityInverseTable, const IntType &cycloOrderInv, const IntType &preconCycloOrderInv, 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. The method works for the NativeInteger case based on NTL’s modular multiplication. [Algorithm 2 in https://eprint.iacr.org/2016/504.pdf]

Parameters

  • rootOfUnityInverseTable – is the table with the inverse 2n-th root of unity powers in bit reverse order.

  • preconRootOfUnityInverseTable – is NTL-specific precomputations for optimized NativeInteger modulo multiplications.

  • cycloOrderInv – is inverse of n modulo q

  • preconCycloOrderInv – is NTL-specific precomputations for optimized NativeInteger modulo multiplications.

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

template<typename VecType>
class NTL::ChineseRemainderTransformFTTNtl : public lbcrypto::ChineseRemainderTransformFTTInterface<VecType>

Golden Chinese Remainder Transform FFT implementation.

Public Functions

virtual void ForwardTransformToBitReverse(const VecType &element, const IntType &rootOfUnity, const uint32_t 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 uint32_t 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/output of the transform of type VecType and length n.

virtual void InverseTransformFromBitReverse(const VecType &element, const IntType &rootOfUnity, const uint32_t 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.

virtual void InverseTransformFromBitReverseInPlace(const IntType &rootOfUnity, const uint32_t 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.

virtual void PreCompute(const IntType &rootOfUnity, const uint32_t 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 compute the root of unity tables.

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

  • modulus – is q, the prime modulus

virtual void PreCompute(std::vector<IntType> &rootOfUnity, const uint32_t 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 vector of 2n-th roots of unity, one per modulus in moduliChain, used to compute the root of unity tables.

  • 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

template<typename VecType>
class NTL::ChineseRemainderTransformArbNtl : public lbcrypto::ChineseRemainderTransformArbInterface<VecType>

Chinese Remainder Transform for arbitrary cyclotomics.

Public Functions

virtual void SetCylotomicPolynomial(const VecType &poly, const IntType &mod)

Sets the cyclotomic polynomial.

Parameters

  • poly – is the cyclotomic polynomial.

  • mod – is the modulus of the polynomial ring; used as the key under which poly is stored.

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

Forward transform.

Parameters

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

  • root – is the 2mth root of unity w.r.t the ring modulus.

  • bigMod – is the addtional modulus needed for NTT operation.

  • bigRoot – is the addtional root of unity w.r.t bigMod needed for NTT operation.

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

Returns

is the output result of the transform.

virtual VecType InverseTransform(const VecType &element, const IntType &root, const IntType &bigMod, const IntType &bigRoot, const uint32_t cycloOrder)

Inverse transform.

Parameters

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

  • root – is the 2mth root of unity w.r.t the ring modulus.

  • bigMod – is the addtional modulus needed for NTT operation.

  • bigRoot – is the addtional root of unity w.r.t bigMod needed for NTT operation.

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

Returns

is the output result of the transform.

virtual void Reset()

Reset cached values for the transform to empty.

virtual void PreCompute(const uint32_t cyclotoOrder, const IntType &modulus)

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

Parameters

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

  • modulus – is the modulus of the polynomial ring.

virtual void SetPreComputedNTTModulus(uint32_t cyclotoOrder, const IntType &modulus, const IntType &nttMod, const IntType &nttRoot)

Sets the precomputed root of unity and modulus needed for NTT operation in forward Bluestein transform.

Parameters

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

  • modulus – is the modulus of the polynomial ring.

  • nttMod – is the modulus needed for the NTT operation in forward Bluestein transform.

  • nttRoot – is the root of unity needed for the NTT operation in forward Bluestein transform.

virtual void SetPreComputedNTTDivisionModulus(uint32_t cyclotoOrder, const IntType &modulus, const IntType &nttMod, const IntType &nttRoot)

Sets the precomputed root of unity and modulus needed for NTT operation and computes m_cyclotomicPolyReveseNTTMap,m_cyclotomicPolyNTTMap. Always called after setting the cyclotomic polynomial.

Parameters

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

  • modulus – is the modulus of the polynomial ring.

  • nttMod – is the modulus needed for the NTT operation in forward Bluestein transform.

  • nttRoot – is the root of unity needed for the NTT operation in forward Bluestein transform.

virtual VecType InversePolyMod(const VecType &cycloPoly, const IntType &modulus, uint32_t power)

Computes the inverse of the cyclotomic polynomial using Newton-Iteration method.

Parameters

  • cycloPoly – is the cyclotomic polynomial.

  • modulus – is the modulus of the polynomial ring.

  • power – is the number of coefficients of the inverse, i.e., the inverse is computed modulo x^power.

Returns

inverse polynomial.

template<typename VecType>
class NTL::BluesteinFFTNtl

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 2mth root of unity w.r.t. the modulus of element, where m is the cyclotomic order.

  • 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)
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 (modulus, root) pair, where modulus is the modulus of the polynomial ring and root is the 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 of (modulus, root) pairs: the first holds the modulus of the polynomial ring and the root of unity s.t. root^2m = 1; the second holds the modulus and 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