ring

package
v2.4.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 15, 2023 License: Apache-2.0 Imports: 12 Imported by: 26

Documentation

Overview

Package ring implements RNS-accelerated modular arithmetic operations for polynomials, including: RNS basis extension; RNS rescaling; number theoretic transform (NTT); uniform, Gaussian and ternary sampling.

Index

Constants

View Source 
const (
	Standard           = Type(0) // Z[X]/(X^N + 1) (Default)
	ConjugateInvariant = Type(1) // Z[X+X^-1]/(X^2N + 1)
)

RingStandard and RingConjugateInvariant are two types of Rings.

View Source 
const SimpleScalerFloatPrecision = 80

SimpleScalerFloatPrecision is the precision in bits for the big.Float in the scaling by t/Q.

Variables

View Source 
var DefaultParams = []Parameters{
	{12, Qi60[len(Qi60)-2:], Pi60[len(Pi60)-2:]},
	{13, Qi60[len(Qi60)-4:], Pi60[len(Pi60)-4:]},
	{14, Qi60[len(Qi60)-7:], Pi60[len(Pi60)-7:]},
	{15, Qi60[len(Qi60)-14:], Pi60[len(Pi60)-14:]},
	{16, Qi60[len(Qi60)-29:], Pi60[len(Pi60)-29:]},
}

DefaultParams is a struct storing default test parameters of the Qi and Pi moduli for the package Ring.

View Source 
var Pi60 = []uint64{0x1ffffffff6c80001, 0x1ffffffff6140001, 0x1ffffffff5f40001, 0x1ffffffff5700001,
	0x1ffffffff4bc0001, 0x1ffffffff4380001, 0x1ffffffff3240001, 0x1ffffffff2dc0001,
	0x1ffffffff1a40001, 0x1ffffffff11c0001, 0x1ffffffff0fc0001, 0x1ffffffff0d80001,
	0x1ffffffff0c80001, 0x1ffffffff08c0001, 0x1fffffffefd00001, 0x1fffffffef9c0001,
	0x1fffffffef600001, 0x1fffffffeef40001, 0x1fffffffeed40001, 0x1fffffffeed00001,
	0x1fffffffeebc0001, 0x1fffffffed540001, 0x1fffffffed440001, 0x1fffffffed2c0001,
	0x1fffffffed200001, 0x1fffffffec940001, 0x1fffffffec6c0001, 0x1fffffffebe80001,
	0x1fffffffebac0001, 0x1fffffffeba40001, 0x1fffffffeb4c0001, 0x1fffffffeb280001}

Pi60 are the next [32:64] 61-bit close to 2^{62} NTT-friendly primes for N up to 2^{17}

View Source 
var Qi60 = []uint64{0x1fffffffffe00001, 0x1fffffffffc80001, 0x1fffffffffb40001, 0x1fffffffff500001,
	0x1fffffffff380001, 0x1fffffffff000001, 0x1ffffffffef00001, 0x1ffffffffee80001,
	0x1ffffffffeb40001, 0x1ffffffffe780001, 0x1ffffffffe600001, 0x1ffffffffe4c0001,
	0x1ffffffffdf40001, 0x1ffffffffdac0001, 0x1ffffffffda40001, 0x1ffffffffc680001,
	0x1ffffffffc000001, 0x1ffffffffb880001, 0x1ffffffffb7c0001, 0x1ffffffffb300001,
	0x1ffffffffb1c0001, 0x1ffffffffadc0001, 0x1ffffffffa400001, 0x1ffffffffa140001,
	0x1ffffffff9d80001, 0x1ffffffff9140001, 0x1ffffffff8ac0001, 0x1ffffffff8a80001,
	0x1ffffffff81c0001, 0x1ffffffff7800001, 0x1ffffffff7680001, 0x1ffffffff7080001}

Qi60 are the first [0:32] 61-bit close to 2^{62} NTT-friendly primes for N up to 2^{17}

Functions

func AddScalarNoModAndNegTwoQiNoModVec added in v2.4.0 

func AddScalarNoModAndNegTwoQiNoModVec(p1, p2 []uint64, scalar, qi uint64)

AddScalarNoModAndNegTwoQiNoModVec returns p2 = 2*qi - p1 + scalar.

func AddScalarNoModVec added in v2.4.0 

func AddScalarNoModVec(p1, p2 []uint64, scalar uint64)

AddScalarNoModVec returns p2 = p1 + scalar.

func AddScalarVec added in v2.4.0 

func AddScalarVec(p1, p2 []uint64, scalar, qi uint64)

AddScalarVec returns p2 = p1 + scalar mod qi.

func AddVec added in v2.4.0 

func AddVec(p1, p2, p3 []uint64, qi uint64)

AddVec returns p3 = p1 + p2 mod qi.

func AddVecNoMod added in v2.4.0 

func AddVecNoMod(p1, p2, p3 []uint64)

AddVecNoMod returns p3 = p1 + p2.

func AddVecNoModAndMulScalarMontgomeryVec added in v2.4.0 

func AddVecNoModAndMulScalarMontgomeryVec(p1, p2, p3 []uint64, scalarMont, qi, mredParams uint64)

AddVecNoModAndMulScalarMontgomeryVec returns p3 = (p1+p2)*scalarMont mod qi.

func BRed 

func BRed(x, y, q uint64, u []uint64) (r uint64)

BRed computes x*y mod q.

func BRedAdd 

func BRedAdd(a, q uint64, u []uint64) (r uint64)

BRedAdd computes a mod q.

func BRedAddConstant 

func BRedAddConstant(x, q uint64, u []uint64) uint64

BRedAddConstant computes a mod q in constant time. The result is between 0 and 2*q-1.

func BRedConstant 

func BRedConstant(x, y, q uint64, u []uint64) (r uint64)

BRedConstant computes x*y mod q in constant time. The result is between 0 and 2*q-1.

func BRedParams 

func BRedParams(q uint64) (params []uint64)

BRedParams computes the parameters for the BRed algorithm. Returns ((2^128)/q)/(2^64) and (2^128)/q mod 2^64.

func CRed 

func CRed(a, q uint64) uint64

CRed reduce returns a mod q where a is between 0 and 2*q-1.

func Copy added in v2.2.0 

func Copy(p0, p1 *Poly)

Copy copies the coefficients of p0 on p1 within the given Ring. It requires p1 to be at least as big p0. Expects the degree of both polynomials to be identical. Transfers the IsNTT and IsMForm flags.

func CopyLvl added in v2.2.0 

func CopyLvl(level int, p0, p1 *Poly)

CopyLvl copies the coefficients of p0 on p1 within the given Ring for the moduli from 0 to level. Expects the degree of both polynomials to be identical. Transfers the IsNTT and IsMForm flags.

func CopyValues added in v2.2.0 

func CopyValues(p0, p1 *Poly)

CopyValues copies the coefficients of p0 on p1 within the given Ring. It requires p1 to be at least as big p0. Expects the degree of both polynomials to be identical. Does not transfer the IsNTT and IsMForm flags.

func CopyValuesLvl added in v2.2.0 

func CopyValuesLvl(level int, p0, p1 *Poly)

CopyValuesLvl copies the coefficients of p0 on p1 within the given Ring for the moduli from 0 to level. Expects the degree of both polynomials to be identical. Does not transfer the IsNTT and IsMForm flags.

func Cos 

func Cos(x *big.Float) (cosx *big.Float)

Cos implements the arbitrary precision computation of Cos(x) Iterative process with an error of ~10^{−0.60206*k} after k iterations. ref: Johansson, B. Tomas, An elementary algorithm to evaluate trigonometric functions to high precision, 2018

func DecodeCoeffs 

func DecodeCoeffs(pointer, N, numberModuli int, coeffs [][]uint64, data []byte) (int, error)

DecodeCoeffs converts a byte array to a matrix of coefficients.

func DecodeCoeffsNew 

func DecodeCoeffsNew(pointer, N, numberModuli int, coeffs [][]uint64, data []byte) (int, error)

DecodeCoeffsNew converts a byte array to a matrix of coefficients.

func DecodeCoeffsNew32 

func DecodeCoeffsNew32(pointer, N, numberModuli int, coeffs [][]uint64, data []byte) (int, error)

DecodeCoeffsNew32 converts a byte array to a matrix of coefficients.

func DivRound 

func DivRound(a, b, i *big.Int)

DivRound sets the target i to round(a/b).

func GenGaloisParams 

func GenGaloisParams(n, gen uint64) (galElRotCol []uint64)

GenGaloisParams generates the generators for the Galois endomorphisms.

func GenerateNTTPrimes 

func GenerateNTTPrimes(logQ, NthRoot, n int) (primes []uint64)

GenerateNTTPrimes generates n NthRoot NTT friendly primes given logQ = size of the primes. It will return all the appropriate primes, up to the number of n, with the best available deviation from the base power of 2 for the given n.

func GenerateNTTPrimesP 

func GenerateNTTPrimesP(logP, NthRoot, n int) (primes []uint64)

GenerateNTTPrimesP generates "levels" different NthRoot NTT-friendly primes starting from 2**LogP and downward. Special case were primes close to 2^{LogP} but with a smaller bit-size than LogP are sought.

func GenerateNTTPrimesQ 

func GenerateNTTPrimesQ(logQ, NthRoot, levels int) (primes []uint64)

GenerateNTTPrimesQ generates "levels" different NthRoot NTT-friendly primes starting from 2**LogQ and alternating between upward and downward.

func InvMForm 

func InvMForm(a, q, qInv uint64) (r uint64)

InvMForm switches a from the Montgomery domain back to the standard domain by computing a*(1/2^64) mod q.

func InvMFormConstant 

func InvMFormConstant(a, q, qInv uint64) (r uint64)

InvMFormConstant switches a from the Montgomery domain back to the standard domain by computing a*(1/2^64) mod q in constant time. The result is between 0 and 2*q-1.

func InvMFormVec added in v2.4.0 

func InvMFormVec(p1, p2 []uint64, qi, mredParams uint64)

InvMFormVec returns p2 = p1 * (2^64)^-1 mod qi.

func InvNTT 

func InvNTT(coeffsIn, coeffsOut []uint64, N int, nttPsiInv []uint64, nttNInv, Q, QInv uint64)

InvNTT computes the InvNTT transformation on the input coefficients using the input parameters.

func InvNTTConjugateInvariant added in v2.4.0 

func InvNTTConjugateInvariant(coeffsIn, coeffsOut []uint64, N int, nttPsiInv []uint64, nttNInv, Q, QInv uint64)

InvNTTConjugateInvariant computes the InvNTT in the closed sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1).

func InvNTTConjugateInvariantLazy added in v2.4.0 

func InvNTTConjugateInvariantLazy(coeffsIn, coeffsOut []uint64, N int, nttPsiInv []uint64, nttNInv, Q, QInv uint64)

InvNTTConjugateInvariantLazy computes the InvNTT in the closed sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1) with output values in the range [0, 2q-1].

func InvNTTLazy added in v2.1.0 

func InvNTTLazy(coeffsIn, coeffsOut []uint64, N int, nttPsiInv []uint64, nttNInv, Q, QInv uint64)

InvNTTLazy computes the InvNTT transformation on the input coefficients using the input parameters with output values in the range [0, 2q-1].

func IsPrime 

func IsPrime(x uint64) bool

IsPrime applies the Baillie-PSW, which is 100% accurate for numbers bellow 2^64.

func MForm 

func MForm(a, q uint64, u []uint64) (r uint64)

MForm switches a to the Montgomery domain by computing a*2^64 mod q.

func MFormConstant 

func MFormConstant(a, q uint64, u []uint64) (r uint64)

MFormConstant switches a to the Montgomery domain by computing a*2^64 mod q in constant time. The result is between 0 and 2*q-1.

func MFormConstantVec added in v2.4.0 

func MFormConstantVec(p1, p2 []uint64, qi uint64, bredParams []uint64)

MFormConstantVec returns p2 = p1 * 2^64 mod qi with result in the range [0, 2q-1]

func MFormVec added in v2.3.0 

func MFormVec(p1, p2 []uint64, qi uint64, bredParams []uint64)

MFormVec returns p2 = p1 * 2^64 mod qi.

func MRed 

func MRed(x, y, q, qInv uint64) (r uint64)

MRed computes x * y * (1/2^64) mod q.

func MRedConstant 

func MRedConstant(x, y, q, qInv uint64) (r uint64)

MRedConstant computes x * y * (1/2^64) mod q in constant time. The result is between 0 and 2*q-1.

func MRedParams 

func MRedParams(q uint64) (qInv uint64)

MRedParams computes the parameter qInv = (q^-1) mod 2^64, required for MRed.

func MapSmallDimensionToLargerDimensionNTT added in v2.3.0 

func MapSmallDimensionToLargerDimensionNTT(polSmall, polLarge *Poly)

MapSmallDimensionToLargerDimensionNTT maps Y = X^{N/n} -> X directly in the NTT domain

func Min 

func Min(x, y int) int

Min returns the minimum between to int

func ModExp 

func ModExp(x, e, p uint64) (result uint64)

ModExp performs the modular exponentiation x^e mod p, x and p are required to be at most 64 bits to avoid an overflow.

func ModVec added in v2.4.0 

func ModVec(p1, p2 []uint64, m uint64, bredParams []uint64)

ModVec returns p2 = p1 mod m.

func ModexpMontgomery added in v2.3.0 

func ModexpMontgomery(x uint64, e int, q, qInv uint64, bredParams []uint64) (result uint64)

ModexpMontgomery performs the modular exponentiation x^e mod p, where x is in Montgomery form, and returns x^e in Montgomery form.

func MulByPow2Vec added in v2.4.0 

func MulByPow2Vec(p1, p2 []uint64, pow2 int, qi, mredParams uint64)

MulByPow2Vec returns p2 = p1 * 2^pow2 mod qi.

func MulCoeffsAndAddNoModVec added in v2.4.0 

func MulCoeffsAndAddNoModVec(p1, p2, p3 []uint64, qi uint64, bredParams []uint64)

MulCoeffsAndAddNoModVec returns p3 = p3 + (p1*p2 mod qi).

func MulCoeffsAndAddVec added in v2.4.0 

func MulCoeffsAndAddVec(p1, p2, p3 []uint64, qi uint64, bredParams []uint64)

MulCoeffsAndAddVec returns p3 = p3 + (p1*p2) mod qi.

func MulCoeffsConstantVec added in v2.4.0 

func MulCoeffsConstantVec(p1, p2, p3 []uint64, qi uint64, bredParams []uint64)

MulCoeffsConstantVec returns p3 = p1*p2 mod qi with output coefficients in range [0, 2qi-1].

func MulCoeffsMontgomeryAndAddNoModVec added in v2.4.0 

func MulCoeffsMontgomeryAndAddNoModVec(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryAndAddNoModVec returns p3 = p3 + (p1*p2 mod qi).

func MulCoeffsMontgomeryAndAddVec added in v2.4.0 

func MulCoeffsMontgomeryAndAddVec(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryAndAddVec returns p3 = p3 + (p1*p2) mod qi.

func MulCoeffsMontgomeryAndSubNoMod added in v2.4.0 

func MulCoeffsMontgomeryAndSubNoMod(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryAndSubNoMod returns p3 = p3 - p1*p2 mod qi with output coefficients in range [0, 2qi-2].

func MulCoeffsMontgomeryAndSubVec added in v2.4.0 

func MulCoeffsMontgomeryAndSubVec(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryAndSubVec returns p3 = p3 - p1*p2 mod qi.

func MulCoeffsMontgomeryConstantAndAddNoModVec added in v2.4.0 

func MulCoeffsMontgomeryConstantAndAddNoModVec(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryConstantAndAddNoModVec returns p3 = p3 + p1*p2 mod qi with output coefficients in range [0, 3qi-2].

func MulCoeffsMontgomeryConstantAndNeg added in v2.4.0 

func MulCoeffsMontgomeryConstantAndNeg(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryConstantAndNeg returns p3 = - p1*p2 mod qi with output coefficients in range [0, 2qi-2].

func MulCoeffsMontgomeryConstantAndSubNoMod added in v2.4.0 

func MulCoeffsMontgomeryConstantAndSubNoMod(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryConstantAndSubNoMod returns p3 = p3 - p1*p2 mod qi with output coefficients in range [0, 3qi-2].

func MulCoeffsMontgomeryConstantVec added in v2.4.0 

func MulCoeffsMontgomeryConstantVec(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryConstantVec returns p3 = p1*p2 mod qi with output coefficients in range [0, 2qi-1].

func MulCoeffsMontgomeryVec added in v2.4.0 

func MulCoeffsMontgomeryVec(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryVec returns p3 = p1*p2 mod qi.

func MulCoeffsVec added in v2.4.0 

func MulCoeffsVec(p1, p2, p3 []uint64, qi uint64, bredParams []uint64)

MulCoeffsVec returns p3 = p1*p2 mod qi.

func MulScalarMontgomeryAndAddVec added in v2.4.0 

func MulScalarMontgomeryAndAddVec(p1, p2 []uint64, scalarMont, qi, mredParams uint64)

MulScalarMontgomeryAndAddVec returns p2 = p2 + p1*scalarMont mod qi.

func MulScalarMontgomeryConstantVec added in v2.4.0 

func MulScalarMontgomeryConstantVec(p1, p2 []uint64, scalarMont, qi, mredParams uint64)

MulScalarMontgomeryConstantVec returns p2 = p1*scalarMont mod qi with output coefficients in range [0, 2qi-1].

func MulScalarMontgomeryVec added in v2.4.0 

func MulScalarMontgomeryVec(p1, p2 []uint64, scalarMont, qi, mredParams uint64)

MulScalarMontgomeryVec returns p2 = p1*scalarMont mod qi.

func NTT 

func NTT(coeffsIn, coeffsOut []uint64, N int, nttPsi []uint64, Q, mredParams uint64, bredParams []uint64)

NTT computes the NTT on the input coefficients using the input parameters.

func NTTConjugateInvariant added in v2.4.0 

func NTTConjugateInvariant(coeffsIn, coeffsOut []uint64, N int, nttPsi []uint64, Q, QInv uint64, bredParams []uint64)

NTTConjugateInvariant computes the NTT in the closed sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1).

func NTTConjugateInvariantLazy added in v2.4.0 

func NTTConjugateInvariantLazy(coeffsIn, coeffsOut []uint64, N int, nttPsi []uint64, Q, QInv uint64, bredParams []uint64)

NTTConjugateInvariantLazy computes the NTT in the closed sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1) with output values in the range [0, 2q-1].

func NTTLazy added in v2.1.0 

func NTTLazy(coeffsIn, coeffsOut []uint64, N int, nttPsi []uint64, Q, QInv uint64, bredParams []uint64)

NTTLazy computes the NTT on the input coefficients using the input parameters with output values in the range [0, 2q-1].

func NegVec added in v2.4.0 

func NegVec(p1, p2 []uint64, qi uint64)

NegVec returns p2 = -p1 mod qi.

func NewFloat 

func NewFloat(x float64, logPrecision int) (y *big.Float)

NewFloat creates a new big.Float element with "logPrecision" bits of precision

func NewInt 

func NewInt(v int64) *big.Int

NewInt creates a new Int with a given int64 value.

func NewIntFromString 

func NewIntFromString(s string) *big.Int

NewIntFromString creates a new Int from a string. A prefix of “0x” or “0X” selects base 16; the “0” prefix selects base 8, and a “0b” or “0B” prefix selects base 2. Otherwise, the selected base is 10.

func NewUint 

func NewUint(v uint64) *big.Int

NewUint creates a new Int with a given uint64 value.

func NextNTTPrime added in v2.1.0 

func NextNTTPrime(q uint64, NthRoot int) (qNext uint64, err error)

NextNTTPrime returns the next NthRoot NTT prime after q. The input q must be itself an NTT prime for the given NthRoot.

func PadDefaultRingToConjuateInvariant added in v2.4.0 

func PadDefaultRingToConjuateInvariant(p1 *Poly, ringQ *Ring, p2 *Poly)

PadDefaultRingToConjuateInvariant converts a polynomial in Z[X]/(X^N +1) to a polynomial in Z[X+X^-1]/(X^2N+1). Conversion will check the .IsNTT flag of the polynomial p1.

func PowerOf2 

func PowerOf2(x uint64, n int, q, qInv uint64) (r uint64)

PowerOf2 returns (x*2^n)%q where x is in Montgomery form

func PreviousNTTPrime added in v2.1.0 

func PreviousNTTPrime(q uint64, NthRoot int) (qPrev uint64, err error)

PreviousNTTPrime returns the previous NthRoot NTT prime after q. The input q must be itself an NTT prime for the given NthRoot.

func RandInt 

func RandInt(max *big.Int) (n *big.Int)

RandInt generates a random Int in [0, max-1].

func RandUniform 

func RandUniform(prng utils.PRNG, v uint64, mask uint64) (randomInt uint64)

RandUniform samples a uniform randomInt variable in the range [0, mask] until randomInt is in the range [0, v-1]. mask needs to be of the form 2^n -1.

func ReduceConstantVec added in v2.4.0 

func ReduceConstantVec(p1, p2 []uint64, qi uint64, bredParams []uint64)

ReduceConstantVec returns p2 = p1 mod qi with output coefficients range [0, 2qi-1].

func ReduceVec added in v2.4.0 

func ReduceVec(p1, p2 []uint64, qi uint64, bredParams []uint64)

ReduceVec returns p2 = p1 mod qi.

func SubScalarVec added in v2.4.0 

func SubScalarVec(p1, p2 []uint64, scalar, qi uint64)

SubScalarVec returns p2 = p1 - scalar mod qi.

func SubVec added in v2.4.0 

func SubVec(p1, p2, p3 []uint64, qi uint64)

SubVec returns p3 = p1 - p2 mod qi.

func SubVecAndMulScalarMontgomeryTwoQiVec added in v2.4.0 

func SubVecAndMulScalarMontgomeryTwoQiVec(p1, p2, p3 []uint64, scalarMont, qi, mredParams uint64)

SubVecAndMulScalarMontgomeryTwoQiVec returns p3 = (p1 + twoqi - p2) * scalarMont mod qi.

func SubVecNomod added in v2.4.0 

func SubVecNomod(p1, p2, p3 []uint64, qi uint64)

SubVecNomod returns p3 = p1 + qi - p2.

func WriteCoeffsTo 

func WriteCoeffsTo(pointer, N, numberModuli int, coeffs [][]uint64, data []byte) (int, error)

WriteCoeffsTo converts a matrix of coefficients to a byte array.

func WriteCoeffsTo32 

func WriteCoeffsTo32(pointer, N, numberModuli int, coeffs [][]uint64, data []byte) (int, error)

WriteCoeffsTo32 converts a matrix of coefficients to a byte array.

Types

type Complex 

type Complex [2]*big.Float

Complex is a type for arbitrary precision complex number

func NewComplex 

func NewComplex(a, b *big.Float) (c *Complex)

NewComplex creates a new arbitrary precision complex number

func (*Complex) Add 

func (c *Complex) Add(a, b *Complex)

Add adds two arbitrary precision complex numbers together

func (*Complex) Copy 

func (c *Complex) Copy() *Complex

Copy returns a new copy of the target arbitrary precision complex number

func (*Complex) Float64 

func (c *Complex) Float64() complex128

Float64 returns the arbitrary precision complex number as a complex128

func (*Complex) Imag 

func (c *Complex) Imag() *big.Float

Imag returns the imaginary part as a big.Float

func (*Complex) Real 

func (c *Complex) Real() *big.Float

Real returns the real part as a big.Float

func (*Complex) Set 

func (c *Complex) Set(a *Complex)

Set sets a arbitrary precision complex number

func (*Complex) Sub 

func (c *Complex) Sub(a, b *Complex)

Sub subtracts two arbitrary precision complex numbers together

type ComplexMultiplier 

type ComplexMultiplier struct {
	// contains filtered or unexported fields
}

ComplexMultiplier is a struct for the multiplication or division of two arbitrary precision complex numbers

func NewComplexMultiplier 

func NewComplexMultiplier() (cEval *ComplexMultiplier)

NewComplexMultiplier creates a new ComplexMultiplier

func (*ComplexMultiplier) Div 

func (cEval *ComplexMultiplier) Div(a, b, c *Complex)

Div divides two arbitrary precision complex numbers together

func (*ComplexMultiplier) Mul 

func (cEval *ComplexMultiplier) Mul(a, b, c *Complex)

Mul multiplies two arbitrary precision complex numbers together

type Decomposer 

type Decomposer struct {
	// contains filtered or unexported fields
}

Decomposer is a structure that stores the parameters of the arbitrary decomposer. This decomposer takes a p(x)_Q (in basis Q) and returns p(x) mod qi in basis QP, where qi = prod(Q_i) for 0<=i<=L, where L is the number of factors in P.

func NewDecomposer 

func NewDecomposer(ringQ, ringP *Ring) (decomposer *Decomposer)

NewDecomposer creates a new Decomposer.

func (*Decomposer) DecomposeAndSplit 

func (decomposer *Decomposer) DecomposeAndSplit(levelQ, levelP, alpha, beta int, p0Q, p1Q, p1P *Poly)

DecomposeAndSplit decomposes a polynomial p(x) in basis Q, reduces it modulo qi, and returns the result in basis QP separately.

type FastBasisExtender 

type FastBasisExtender struct {
	// contains filtered or unexported fields
}

FastBasisExtender stores the necessary parameters for RNS basis extension. The used algorithm is from https://eprint.iacr.org/2018/117.pdf.

func NewFastBasisExtender 

func NewFastBasisExtender(ringQ, ringP *Ring) *FastBasisExtender

NewFastBasisExtender creates a new FastBasisExtender, enabling RNS basis extension from Q to P and P to Q.

func (*FastBasisExtender) ModDownQPtoP added in v2.3.0 

func (be *FastBasisExtender) ModDownQPtoP(levelQ, levelP int, p1Q, p1P, p2P *Poly)

ModDownQPtoP reduces the basis of a polynomial. Given a polynomial with coefficients in basis {Q0,Q1....QlevelQ} and {P0,P1...PlevelP}, it reduces its basis from {Q0,Q1....QlevelQ} and {P0,P1...PlevelP} to {P0,P1...PlevelP} and does a floored integer division of the result by Q.

func (*FastBasisExtender) ModDownQPtoQ added in v2.3.0 

func (be *FastBasisExtender) ModDownQPtoQ(levelQ, levelP int, p1Q, p1P, p2Q *Poly)

ModDownQPtoQ reduces the basis of a polynomial. Given a polynomial with coefficients in basis {Q0,Q1....Qlevel} and {P0,P1...Pj}, it reduces its basis from {Q0,Q1....Qlevel} and {P0,P1...Pj} to {Q0,Q1....Qlevel} and does a rounded integer division of the result by P.

func (*FastBasisExtender) ModDownQPtoQNTT added in v2.3.0 

func (be *FastBasisExtender) ModDownQPtoQNTT(levelQ, levelP int, p1Q, p1P, p2Q *Poly)

ModDownQPtoQNTT reduces the basis of a polynomial. Given a polynomial with coefficients in basis {Q0,Q1....Qi} and {P0,P1...Pj}, it reduces its basis from {Q0,Q1....Qi} and {P0,P1...Pj} to {Q0,Q1....Qi} and does a rounded integer division of the result by P. Inputs must be in the NTT domain.

func (*FastBasisExtender) ModUpPtoQ added in v2.3.0 

func (be *FastBasisExtender) ModUpPtoQ(levelP, levelQ int, polP, polQ *Poly)

ModUpPtoQ extends the RNS basis of a polynomial from P to PQ. Given a polynomial with coefficients in basis {P0,P1....Plevel}, it extends its basis from {P0,P1....Plevel} to {Q0,Q1...Qj}

func (*FastBasisExtender) ModUpQtoP added in v2.3.0 

func (be *FastBasisExtender) ModUpQtoP(levelQ, levelP int, polQ, polP *Poly)

ModUpQtoP extends the RNS basis of a polynomial from Q to QP. Given a polynomial with coefficients in basis {Q0,Q1....Qlevel}, it extends its basis from {Q0,Q1....Qlevel} to {Q0,Q1....Qlevel,P0,P1...Pj}

func (*FastBasisExtender) ShallowCopy added in v2.2.0 

func (be *FastBasisExtender) ShallowCopy() *FastBasisExtender

ShallowCopy creates a shallow copy of this basis extender in which the read-only data-structures are shared with the receiver.

type GaussianSampler 

type GaussianSampler struct {
	// contains filtered or unexported fields
}

GaussianSampler keeps the state of a truncated Gaussian polynomial sampler.

func NewGaussianSampler 

func NewGaussianSampler(prng utils.PRNG, baseRing *Ring, sigma float64, bound int) *GaussianSampler

NewGaussianSampler creates a new instance of GaussianSampler from a PRNG, a ring definition and the truncated Gaussian distribution parameters. Sigma is the desired standard deviation and bound is the maximum coefficient norm in absolute value.

func (*GaussianSampler) Read 

func (gaussianSampler *GaussianSampler) Read(pol *Poly)

Read samples a truncated Gaussian polynomial on "pol" at the maximum level in the default ring, standard deviation and bound.

func (*GaussianSampler) ReadAndAddFromDistLvl added in v2.2.0 

func (gaussianSampler *GaussianSampler) ReadAndAddFromDistLvl(level int, pol *Poly, ring *Ring, sigma float64, bound int)

ReadAndAddFromDistLvl samples a truncated Gaussian polynomial at the given level in the provided ring, standard deviation and bound and adds it on "pol".

func (*GaussianSampler) ReadAndAddLvl 

func (gaussianSampler *GaussianSampler) ReadAndAddLvl(level int, pol *Poly)

ReadAndAddLvl samples a truncated Gaussian polynomial at the given level for the receiver's default standard deviation and bound and adds it on "pol".

func (*GaussianSampler) ReadFromDistLvl added in v2.2.0 

func (gaussianSampler *GaussianSampler) ReadFromDistLvl(level int, pol *Poly, ring *Ring, sigma float64, bound int)

ReadFromDistLvl samples a truncated Gaussian polynomial at the given level in the provided ring, standard deviation and bound.

func (*GaussianSampler) ReadLvl 

func (gaussianSampler *GaussianSampler) ReadLvl(level int, pol *Poly)

ReadLvl samples a truncated Gaussian polynomial at the provided level, in the default ring, standard deviation and bound.

func (*GaussianSampler) ReadLvlNew added in v2.1.0 

func (gaussianSampler *GaussianSampler) ReadLvlNew(level int) (pol *Poly)

ReadLvlNew samples a new truncated Gaussian polynomial at the provided level, in the default ring, standard deviation and bound.

func (*GaussianSampler) ReadNew 

func (gaussianSampler *GaussianSampler) ReadNew() (pol *Poly)

ReadNew samples a new truncated Gaussian polynomial at the maximum level in the default ring, standard deviation and bound.

type NumberTheoreticTransformer added in v2.4.0 

type NumberTheoreticTransformer interface {
	Forward(r *Ring, p1, p2 *Poly)
	ForwardLvl(r *Ring, level int, p1, p2 *Poly)
	ForwardLazy(r *Ring, p1, p2 *Poly)
	ForwardLazyLvl(r *Ring, level int, p1, p2 *Poly)
	Backward(r *Ring, p1, p2 *Poly)
	BackwardLvl(r *Ring, level int, p1, p2 *Poly)
	BackwardLazy(r *Ring, p1, p2 *Poly)
	BackwardLazyLvl(r *Ring, level int, p1, p2 *Poly)
	ForwardVec(r *Ring, level int, p1, p2 []uint64)
	ForwardLazyVec(r *Ring, level int, p1, p2 []uint64)
	BackwardVec(r *Ring, level int, p1, p2 []uint64)
	BackwardLazyVec(r *Ring, level int, p1, p2 []uint64)
}

NumberTheoreticTransformer is an interface to provide flexibility on what type of NTT is used by the struct Ring.

type NumberTheoreticTransformerConjugateInvariant added in v2.4.0 

type NumberTheoreticTransformerConjugateInvariant struct {
}

NumberTheoreticTransformerConjugateInvariant computes the NTT in the ring Z[X+X^-1]/(X^2N+1). Z[X+X^-1]/(X^2N+1) is a closed sub-ring of Z[X]/(X^2N+1). Note that the input polynomial only needs to be size N since the right half does not provide any additional information. See "Approximate Homomorphic Encryption over the Conjugate-invariant Ring", https://eprint.iacr.org/2018/952. The implemented approach is more efficient than the one proposed in the referenced work. It avoids the linear map Z[X + X^-1]/(X^2N + 1) <-> Z[X]/(X^N - 1) by instead directly computing the left half of the NTT of Z[X + X^-1]/(X^2N + 1) since the right half provides no additional information, which allows to (re)use nega-cyclic NTT.

func (NumberTheoreticTransformerConjugateInvariant) Backward added in v2.4.0 

func (rntt NumberTheoreticTransformerConjugateInvariant) Backward(r *Ring, p1, p2 *Poly)

Backward writes the backward NTT in Z[X+X^-1]/(X^2N+1) on p2.

func (NumberTheoreticTransformerConjugateInvariant) BackwardLazy added in v2.4.0 

func (rntt NumberTheoreticTransformerConjugateInvariant) BackwardLazy(r *Ring, p1, p2 *Poly)

BackwardLazy writes the backward NTT in Z[X+X^-1]/(X^2N+1) on p2. Returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerConjugateInvariant) BackwardLazyLvl added in v2.4.0 

func (rntt NumberTheoreticTransformerConjugateInvariant) BackwardLazyLvl(r *Ring, level int, p1, p2 *Poly)

BackwardLazyLvl writes the backward NTT in Z[X+X^-1]/(X^2N+1) on p2. Only computes the NTT for the first level+1 moduli and returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerConjugateInvariant) BackwardLazyVec added in v2.4.0 

func (rntt NumberTheoreticTransformerConjugateInvariant) BackwardLazyVec(r *Ring, level int, p1, p2 []uint64)

BackwardLazyVec writes the backward NTT in Z[X+X^-1]/(X^2N+1) of the i-th level of p1 on the i-th level of p2. Returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerConjugateInvariant) BackwardLvl added in v2.4.0 

func (rntt NumberTheoreticTransformerConjugateInvariant) BackwardLvl(r *Ring, level int, p1, p2 *Poly)

BackwardLvl writes the backward NTT in Z[X+X^-1]/(X^2N+1) on p2. Only computes the NTT for the first level+1 moduli.

func (NumberTheoreticTransformerConjugateInvariant) BackwardVec added in v2.4.0 

func (rntt NumberTheoreticTransformerConjugateInvariant) BackwardVec(r *Ring, level int, p1, p2 []uint64)

BackwardVec writes the backward NTT in Z[X+X^-1]/(X^2N+1) of the i-th level of p1 on the i-th level of p2.

func (NumberTheoreticTransformerConjugateInvariant) Forward added in v2.4.0 

func (rntt NumberTheoreticTransformerConjugateInvariant) Forward(r *Ring, p1, p2 *Poly)

Forward writes the forward NTT in Z[X+X^-1]/(X^2N+1) on p2.

func (NumberTheoreticTransformerConjugateInvariant) ForwardLazy added in v2.4.0 

func (rntt NumberTheoreticTransformerConjugateInvariant) ForwardLazy(r *Ring, p1, p2 *Poly)

ForwardLazy writes the forward NTT in Z[X+X^-1]/(X^2N+1) on p2. Returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerConjugateInvariant) ForwardLazyLvl added in v2.4.0 

func (rntt NumberTheoreticTransformerConjugateInvariant) ForwardLazyLvl(r *Ring, level int, p1, p2 *Poly)

ForwardLazyLvl writes the forward NTT in Z[X+X^-1]/(X^2N+1) on p2. Only computes the NTT for the first level+1 moduli and returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerConjugateInvariant) ForwardLazyVec added in v2.4.0 

func (rntt NumberTheoreticTransformerConjugateInvariant) ForwardLazyVec(r *Ring, level int, p1, p2 []uint64)

ForwardLazyVec writes the forward NTT in Z[X+X^-1]/(X^2N+1) of the i-th level of p1 on the i-th level of p2. Returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerConjugateInvariant) ForwardLvl added in v2.4.0 

func (rntt NumberTheoreticTransformerConjugateInvariant) ForwardLvl(r *Ring, level int, p1, p2 *Poly)

ForwardLvl writes the forward NTT in Z[X+X^-1]/(X^2N+1) on p2. Only computes the NTT for the first level+1 moduli.

func (NumberTheoreticTransformerConjugateInvariant) ForwardVec added in v2.4.0 

func (rntt NumberTheoreticTransformerConjugateInvariant) ForwardVec(r *Ring, level int, p1, p2 []uint64)

ForwardVec writes the forward NTT in Z[X+X^-1]/(X^2N+1) of the i-th level of p1 on the i-th level of p2.

type NumberTheoreticTransformerStandard added in v2.4.0 

type NumberTheoreticTransformerStandard struct {
}

NumberTheoreticTransformerStandard computes the standard nega-cyclic NTT in the ring Z[X]/(X^N+1).

func (NumberTheoreticTransformerStandard) Backward added in v2.4.0 

func (rntt NumberTheoreticTransformerStandard) Backward(r *Ring, p1, p2 *Poly)

Backward writes the backward NTT in Z[X]/(X^N+1) on p2.

func (NumberTheoreticTransformerStandard) BackwardLazy added in v2.4.0 

func (rntt NumberTheoreticTransformerStandard) BackwardLazy(r *Ring, p1, p2 *Poly)

BackwardLazy writes the backward NTT in Z[X]/(X^N+1) on p2. Returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerStandard) BackwardLazyLvl added in v2.4.0 

func (rntt NumberTheoreticTransformerStandard) BackwardLazyLvl(r *Ring, level int, p1, p2 *Poly)

BackwardLazyLvl writes the backward NTT in Z[X]/(X^N+1) on p2. Only computes the NTT for the first level+1 moduli and returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerStandard) BackwardLazyVec added in v2.4.0 

func (rntt NumberTheoreticTransformerStandard) BackwardLazyVec(r *Ring, level int, p1, p2 []uint64)

BackwardLazyVec writes the backward NTT in Z[X]/(X^N+1) of the i-th level of p1 on the i-th level of p2. Returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerStandard) BackwardLvl added in v2.4.0 

func (rntt NumberTheoreticTransformerStandard) BackwardLvl(r *Ring, level int, p1, p2 *Poly)

BackwardLvl writes the backward NTT in Z[X]/(X^N+1) on p2. Only computes the NTT for the first level+1 moduli.

func (NumberTheoreticTransformerStandard) BackwardVec added in v2.4.0 

func (rntt NumberTheoreticTransformerStandard) BackwardVec(r *Ring, level int, p1, p2 []uint64)

BackwardVec writes the backward NTT in Z[X]/(X^N+1) of the i-th level of p1 on the i-th level of p2.

func (NumberTheoreticTransformerStandard) Forward added in v2.4.0 

func (rntt NumberTheoreticTransformerStandard) Forward(r *Ring, p1, p2 *Poly)

Forward writes the forward NTT in Z[X]/(X^N+1) of p1 on p2.

func (NumberTheoreticTransformerStandard) ForwardLazy added in v2.4.0 

func (rntt NumberTheoreticTransformerStandard) ForwardLazy(r *Ring, p1, p2 *Poly)

ForwardLazy writes the forward NTT in Z[X]/(X^N+1) of p1 on p2. Returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerStandard) ForwardLazyLvl added in v2.4.0 

func (rntt NumberTheoreticTransformerStandard) ForwardLazyLvl(r *Ring, level int, p1, p2 *Poly)

ForwardLazyLvl writes the forward NTT in Z[X]/(X^N+1) of p1 on p2. Only computes the NTT for the first level+1 moduli and returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerStandard) ForwardLazyVec added in v2.4.0 

func (rntt NumberTheoreticTransformerStandard) ForwardLazyVec(r *Ring, level int, p1, p2 []uint64)

ForwardLazyVec writes the forward NTT in Z[X]/(X^N+1) of the i-th level of p1 on the i-th level of p2. Returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerStandard) ForwardLvl added in v2.4.0 

func (rntt NumberTheoreticTransformerStandard) ForwardLvl(r *Ring, level int, p1, p2 *Poly)

ForwardLvl writes the forward NTT in Z[X]/(X^N+1) of p1 on p2. Only computes the NTT for the first level+1 moduli.

func (NumberTheoreticTransformerStandard) ForwardVec added in v2.4.0 

func (rntt NumberTheoreticTransformerStandard) ForwardVec(r *Ring, level int, p1, p2 []uint64)

ForwardVec writes the forward NTT in Z[X]/(X^N+1) of the i-th level of p1 on the i-th level of p2.

type Parameters 

type Parameters struct {
	// contains filtered or unexported fields
}

Parameters is a struct storing test parameters for the package Ring.

type Poly 

type Poly struct {
	Coeffs  [][]uint64 // Coefficients in CRT representation
	IsNTT   bool
	IsMForm bool
}

Poly is the structure that contains the coefficients of a polynomial.

func NewPoly 

func NewPoly(N, nbModuli int) (pol *Poly)

NewPoly creates a new polynomial with N coefficients set to zero and nbModuli moduli.

func (*Poly) Copy 

func (pol *Poly) Copy(p1 *Poly)

Copy copies the coefficients of p1 on the target polynomial. Onyl copies minLevel(pol, p1) levels. Transfers the IsNTT and IsMForm flags.

func (*Poly) CopyNew 

func (pol *Poly) CopyNew() (p1 *Poly)

CopyNew creates an exact copy of the target polynomial.

func (*Poly) CopyValues added in v2.2.0 

func (pol *Poly) CopyValues(p1 *Poly)

CopyValues copies the coefficients of p1 on the target polynomial. Onyl copies minLevel(pol, p1) levels. Expects the degree of both polynomials to be identical. Does not transfer the IsNTT and IsMForm flags.

func (*Poly) DecodePolyNew 

func (pol *Poly) DecodePolyNew(data []byte) (pointer int, err error)

DecodePolyNew decodes a slice of bytes in the target polynomial returns the number of bytes decoded.

func (*Poly) DecodePolyNew32 

func (pol *Poly) DecodePolyNew32(data []byte) (pointer int, err error)

DecodePolyNew32 decodes a slice of bytes in the target polynomial returns the number of bytes decoded.

func (*Poly) Degree added in v2.2.0 

func (pol *Poly) Degree() int

Degree returns the number of coefficients of the polynomial, which equals the degree of the Ring cyclotomic polynomial.

func (*Poly) Equals added in v2.2.0 

func (pol *Poly) Equals(other *Poly) bool

Equals returns true if the receiver Poly is equal to the provided other Poly. This function checks for strict equality between the polynomial coefficients (i.e., it does not consider congruence as equality within the ring like `Ring.Equals` does). Will not check if IsNTT and IsMForm flags are equal

func (*Poly) GetCoefficients 

func (pol *Poly) GetCoefficients() (coeffs [][]uint64)

GetCoefficients returns a new double slice that contains the coefficients of the polynomial.

func (*Poly) GetDataLen 

func (pol *Poly) GetDataLen(WithMetadata bool) (cnt int)

GetDataLen returns the number of bytes the polynomial will take when written to data. It can take into account meta data if necessary.

func (*Poly) GetDataLen32 

func (pol *Poly) GetDataLen32(WithMetadata bool) (cnt int)

GetDataLen32 returns the number of bytes the polynomial will take when written to data. It can take into account meta data if necessary.

func (*Poly) LenModuli added in v2.2.0 

func (pol *Poly) LenModuli() int

LenModuli returns the current number of moduli.

func (*Poly) Level added in v2.2.0 

func (pol *Poly) Level() int

Level returns the current number of moduli minus 1.

func (*Poly) MarshalBinary 

func (pol *Poly) MarshalBinary() (data []byte, err error)

MarshalBinary encodes the target polynomial on a slice of bytes.

func (*Poly) SetCoefficients 

func (pol *Poly) SetCoefficients(coeffs [][]uint64)

SetCoefficients sets the coefficients of the polynomial directly from a CRT format (double slice).

func (*Poly) UnmarshalBinary 

func (pol *Poly) UnmarshalBinary(data []byte) (err error)

UnmarshalBinary decodes a slice of byte on the target polynomial.

func (*Poly) WriteCoeffs 

func (pol *Poly) WriteCoeffs(data []byte) (int, error)

WriteCoeffs writes the coefficients to the given data array. It fails if the data array is not big enough to contain the ring.Poly

func (*Poly) WriteTo 

func (pol *Poly) WriteTo(data []byte) (int, error)

WriteTo writes the given poly to the data array. It returns the number of written bytes, and the corresponding error, if it occurred.

func (*Poly) WriteTo32 

func (pol *Poly) WriteTo32(data []byte) (int, error)

WriteTo32 writes the given poly to the data array. It returns the number of written bytes, and the corresponding error, if it occurred.

func (*Poly) Zero 

func (pol *Poly) Zero()

Zero sets all coefficients of the target polynomial to 0.

type RNSScaler 

type RNSScaler struct {
	// contains filtered or unexported fields
}

RNSScaler implements the Scaler interface by performing a scaling by t/Q in the RNS domain. This implementation of the Scaler interface is preferred over the SimpleScaler implementation.

func NewRNSScaler 

func NewRNSScaler(ringQ, ringT *Ring) (rnss *RNSScaler)

NewRNSScaler creates a new SimpleScaler from t, the modulus under which the reconstruction is returned, the Ring in which the polynomial to reconstruct is represented.

func (*RNSScaler) DivByQOverTRounded 

func (rnss *RNSScaler) DivByQOverTRounded(p1Q, p2T *Poly)

DivByQOverTRounded returns p1 scaled by a factor t/Q and mod t on the receiver p2.

type Ring 

type Ring struct {
	NumberTheoreticTransformer

	// Polynomial nb.Coefficients
	N int

	// Moduli
	Modulus []uint64

	// 2^bit_length(Qi) - 1
	Mask []uint64

	// Indicates whether NTT can be used with the current ring.
	AllowsNTT bool

	// Product of the Moduli
	ModulusBigint *big.Int

	// Fast reduction parameters
	BredParams [][]uint64
	MredParams []uint64

	RescaleParams [][]uint64

	//NTT Parameters
	NthRoot    uint64
	PsiMont    []uint64 //2N-th primitive root in Montgomery form
	PsiInvMont []uint64 //2N-th inverse primitive root in Montgomery form

	NttPsi    [][]uint64 //powers of the inverse of the 2N-th primitive root in Montgomery form (in bit-reversed order)
	NttPsiInv [][]uint64 //powers of the inverse of the 2N-th primitive root in Montgomery form (in bit-reversed order)
	NttNInv   []uint64   //[N^-1] mod Qi in Montgomery form
}

Ring is a structure that keeps all the variables required to operate on a polynomial represented in this ring.

func NewRing 

func NewRing(N int, Moduli []uint64) (r *Ring, err error)

NewRing creates a new RNS Ring with degree N and coefficient moduli Moduli with Standard NTT. N must be a power of two larger than 8. Moduli should be a non-empty []uint64 with distinct prime elements. All moduli must also be equal to 1 modulo 2*N. An error is returned with a nil *Ring in the case of non NTT-enabling parameters.

func NewRingConjugateInvariant added in v2.4.0 

func NewRingConjugateInvariant(N int, Moduli []uint64) (r *Ring, err error)

NewRingConjugateInvariant creates a new RNS Ring with degree N and coefficient moduli Moduli with Conjugate Invariant NTT. N must be a power of two larger than 8. Moduli should be a non-empty []uint64 with distinct prime elements. All moduli must also be equal to 1 modulo 4*N. An error is returned with a nil *Ring in the case of non NTT-enabling parameters.

func NewRingFromType added in v2.4.0 

func NewRingFromType(N int, Moduli []uint64, ringType Type) (r *Ring, err error)

NewRingFromType creates a new RNS Ring with degree N and coefficient moduli Moduli for which the type of NTT is determined by the ringType argument. If ringType==Standard, the ring is instantiated with standard NTT with the Nth root of unity 2*N. If ringType==ConjugateInvariant, the ring is instantiated with a ConjugateInvariant NTT with Nth root of unity 4*N. N must be a power of two larger than 8. Moduli should be a non-empty []uint64 with distinct prime elements. All moduli must also be equal to 1 modulo the root of unity. An error is returned with a nil *Ring in the case of non NTT-enabling parameters.

func NewRingWithCustomNTT added in v2.4.0 

func NewRingWithCustomNTT(N int, Moduli []uint64, ntt NumberTheoreticTransformer, NthRoot int) (r *Ring, err error)

NewRingWithCustomNTT creates a new RNS Ring with degree N and coefficient moduli Moduli with user-defined NTT transform and primitive Nth root of unity. Moduli should be a non-empty []uint64 with distinct prime elements. All moduli must also be equal to 1 modulo the root of unity. N must be a power of two larger than 8. An error is returned with a nil *Ring in the case of non NTT-enabling parameters.

func (*Ring) Add 

func (r *Ring) Add(p1, p2, p3 *Poly)

Add adds p1 to p2 coefficient-wise and writes the result on p3.

func (*Ring) AddLvl 

func (r *Ring) AddLvl(level int, p1, p2, p3 *Poly)

AddLvl adds p1 to p2 coefficient-wise for the moduli from q_0 up to q_level and writes the result on p3.

func (*Ring) AddNoMod 

func (r *Ring) AddNoMod(p1, p2, p3 *Poly)

AddNoMod adds p1 to p2 coefficient-wise without modular reduction and writes the result on p3.

func (*Ring) AddNoModLvl 

func (r *Ring) AddNoModLvl(level int, p1, p2, p3 *Poly)

AddNoModLvl adds p1 to p2 coefficient-wise without modular reduction for the moduli from q_0 up to q_level and writes the result on p3.

func (*Ring) AddScalar 

func (r *Ring) AddScalar(p1 *Poly, scalar uint64, p2 *Poly)

AddScalar adds a scalar to each coefficient of p1 and writes the result on p2.

func (*Ring) AddScalarBigint 

func (r *Ring) AddScalarBigint(p1 *Poly, scalar *big.Int, p2 *Poly)

AddScalarBigint adds a big.Int scalar to each coefficient of p1 and writes the result on p2.

func (*Ring) AddScalarBigintLvl added in v2.4.0 

func (r *Ring) AddScalarBigintLvl(level int, p1 *Poly, scalar *big.Int, p2 *Poly)

AddScalarBigintLvl adds a big.Int scalar to each coefficient of p1 and writes the result on p2.

func (*Ring) AddScalarLvl added in v2.4.0 

func (r *Ring) AddScalarLvl(level int, p1 *Poly, scalar uint64, p2 *Poly)

AddScalarLvl adds a scalar to each coefficient of p1 and writes the result on p2.

func (*Ring) BitReverse 

func (r *Ring) BitReverse(p1, p2 *Poly)

BitReverse applies a bit reverse permutation on the coefficients of p1 and writes the result on p2. In can safely be used for in-place permutation.

func (*Ring) ConjugateInvariantRing added in v2.4.0 

func (r *Ring) ConjugateInvariantRing() (*Ring, error)

ConjugateInvariantRing returns the conjugate invariant ring of the receiver ring. If `r.Type()==ConjugateInvariant`, then the method returns the receiver. if `r.Type()==Standard`, then the method returns a ring with ring degree N/2. The returned Ring is a shallow copy of the receiver.

func (*Ring) DivFloorByLastModulusLvl added in v2.3.0 

func (r *Ring) DivFloorByLastModulusLvl(level int, p0, p1 *Poly)

DivFloorByLastModulusLvl divides (floored) the polynomial by its last modulus. Output poly level must be equal or one less than input level.

func (*Ring) DivFloorByLastModulusManyLvl added in v2.3.0 

func (r *Ring) DivFloorByLastModulusManyLvl(level, nbRescales int, p0, pool, p1 *Poly)

DivFloorByLastModulusManyLvl divides (floored) sequentially nbRescales times the polynomial by its last modulus. Output poly level must be equal or nbRescales less than input level.

func (*Ring) DivFloorByLastModulusManyNTTLvl added in v2.3.0 

func (r *Ring) DivFloorByLastModulusManyNTTLvl(level, nbRescales int, p0, pool, p1 *Poly)

DivFloorByLastModulusManyNTTLvl divides (floored) sequentially nbRescales times the polynomial by its last modulus. Input must be in the NTT domain. Output poly level must be equal or nbRescales less than input level.

func (*Ring) DivFloorByLastModulusNTTLvl added in v2.3.0 

func (r *Ring) DivFloorByLastModulusNTTLvl(level int, p0, pool, p1 *Poly)

DivFloorByLastModulusNTTLvl divides (floored) the polynomial by its last modulus. The input must be in the NTT domain. Output poly level must be equal or one less than input level.

func (*Ring) DivRoundByLastModulusLvl added in v2.3.0 

func (r *Ring) DivRoundByLastModulusLvl(level int, p0, p1 *Poly)

DivRoundByLastModulusLvl divides (rounded) the polynomial by its last modulus. The input must be in the NTT domain. Output poly level must be equal or one less than input level.

func (*Ring) DivRoundByLastModulusManyLvl added in v2.3.0 

func (r *Ring) DivRoundByLastModulusManyLvl(level, nbRescales int, p0, pool, p1 *Poly)

DivRoundByLastModulusManyLvl divides (rounded) sequentially nbRescales times the polynomial by its last modulus. Output poly level must be equal or nbRescales less than input level.

func (*Ring) DivRoundByLastModulusManyNTTLvl added in v2.3.0 

func (r *Ring) DivRoundByLastModulusManyNTTLvl(level, nbRescales int, p0, pool, p1 *Poly)

DivRoundByLastModulusManyNTTLvl divides (rounded) sequentially nbRescales times the polynomial by its last modulus. The input must be in the NTT domain. Output poly level must be equal or nbRescales less than input level.

func (*Ring) DivRoundByLastModulusNTTLvl added in v2.3.0 

func (r *Ring) DivRoundByLastModulusNTTLvl(level int, p0, pool, p1 *Poly)

DivRoundByLastModulusNTTLvl divides (rounded) the polynomial by its last modulus. The input must be in the NTT domain. Output poly level must be equal or one less than input level.

func (*Ring) Equal 

func (r *Ring) Equal(p1, p2 *Poly) bool

Equal checks if p1 = p2 in the given Ring.

func (*Ring) EqualLvl 

func (r *Ring) EqualLvl(level int, p1, p2 *Poly) bool

EqualLvl checks if p1 = p2 in the given Ring, up to a given level.

func (*Ring) FoldStandardToConjugateInvariant added in v2.4.0 

func (r *Ring) FoldStandardToConjugateInvariant(level int, polyStandard *Poly, permuteNTTIndexInv []uint64, polyConjugateInvariant *Poly)

FoldStandardToConjugateInvariant folds [X]/(X^N+1) to [X+X^-1]/(X^N+1) in compressed form (N/2 coefficients). Requires degree(polyConjugateInvariant) = 2*degree(polyStd). Requires that polyStd and polyConjugateInvariant share the same moduli.

func (*Ring) InvMForm 

func (r *Ring) InvMForm(p1, p2 *Poly)

InvMForm switches back p1 from the Montgomery domain to the conventional domain and writes the result on p2.

func (*Ring) InvMFormLvl added in v2.1.0 

func (r *Ring) InvMFormLvl(level int, p1, p2 *Poly)

InvMFormLvl switches back p1 from the Montgomery domain to the conventional domain and writes the result on p2.

func (*Ring) InvNTT 

func (r *Ring) InvNTT(p1, p2 *Poly)

InvNTT computes the inverse-NTT of p1 and returns the result on p2.

func (*Ring) InvNTTLazy added in v2.1.0 

func (r *Ring) InvNTTLazy(p1, p2 *Poly)

InvNTTLazy computes the inverse-NTT of p1 and returns the result on p2. Output values are in the range [0, 2q-1]

func (*Ring) InvNTTLazyLvl added in v2.1.0 

func (r *Ring) InvNTTLazyLvl(level int, p1, p2 *Poly)

InvNTTLazyLvl computes the inverse-NTT of p1 and returns the result on p2. The value level defines the number of moduli of the input polynomials. Output values are in the range [0, 2q-1]

func (*Ring) InvNTTLvl 

func (r *Ring) InvNTTLvl(level int, p1, p2 *Poly)

InvNTTLvl computes the inverse-NTT of p1 and returns the result on p2. The value level defines the number of moduli of the input polynomials.

func (*Ring) InvNTTSingle added in v2.4.0 

func (r *Ring) InvNTTSingle(level int, p1, p2 []uint64)

InvNTTSingle computes the InvNTT of p1 and returns the result on p2. The level-th moduli of the ring InvNTT params are used. Only computes the InvNTT for the i-th level.

func (*Ring) InvNTTSingleLazy added in v2.4.0 

func (r *Ring) InvNTTSingleLazy(level int, p1, p2 []uint64)

InvNTTSingleLazy computes the InvNTT of p1 and returns the result on p2. The level-th moduli of the ring InvNTT params are used. Output values are in the range [0, 2q-1]

func (*Ring) MForm 

func (r *Ring) MForm(p1, p2 *Poly)

MForm switches p1 to the Montgomery domain and writes the result on p2.

func (*Ring) MFormConstantLvl added in v2.4.0 

func (r *Ring) MFormConstantLvl(level int, p1, p2 *Poly)

MFormConstantLvl switches p1 to the Montgomery domain for the moduli from q_0 up to q_level and writes the result on p2. Result is in the range [0, 2q-1]

func (*Ring) MFormLvl 

func (r *Ring) MFormLvl(level int, p1, p2 *Poly)

MFormLvl switches p1 to the Montgomery domain for the moduli from q_0 up to q_level and writes the result on p2.

func (*Ring) MarshalBinary 

func (r *Ring) MarshalBinary() ([]byte, error)

MarshalBinary encodes the target ring on a slice of bytes.

func (*Ring) Mod 

func (r *Ring) Mod(p1 *Poly, m uint64, p2 *Poly)

Mod applies a modular reduction by m on the coefficients of p1 and writes the result on p2.

func (*Ring) ModLvl added in v2.4.0 

func (r *Ring) ModLvl(level int, p1 *Poly, m uint64, p2 *Poly)

ModLvl applies a modular reduction by m on the coefficients of p1 and writes the result on p2.

func (*Ring) MulByPow2 

func (r *Ring) MulByPow2(p1 *Poly, pow2 int, p2 *Poly)

MulByPow2 multiplies p1 by 2^pow2 and writes the result on p2.

func (*Ring) MulByPow2Lvl 

func (r *Ring) MulByPow2Lvl(level int, p1 *Poly, pow2 int, p2 *Poly)

MulByPow2Lvl multiplies p1 by 2^pow2 for the moduli from q_0 up to q_level and writes the result on p2.

func (*Ring) MulByPow2New 

func (r *Ring) MulByPow2New(p1 *Poly, pow2 int) (p2 *Poly)

MulByPow2New multiplies p1 by 2^pow2 and returns the result in a new polynomial p2.

func (*Ring) MulByVectorMontgomery 

func (r *Ring) MulByVectorMontgomery(p1 *Poly, vector []uint64, p2 *Poly)

MulByVectorMontgomery multiplies p1 by a vector of uint64 coefficients and writes the result on p2.

func (*Ring) MulByVectorMontgomeryAndAddNoMod 

func (r *Ring) MulByVectorMontgomeryAndAddNoMod(p1 *Poly, vector []uint64, p2 *Poly)

MulByVectorMontgomeryAndAddNoMod multiplies p1 by a vector of uint64 coefficients and adds the result on p2 without modular reduction.

func (*Ring) MulByVectorMontgomeryAndAddNoModLvl added in v2.4.0 

func (r *Ring) MulByVectorMontgomeryAndAddNoModLvl(level int, p1 *Poly, vector []uint64, p2 *Poly)

MulByVectorMontgomeryAndAddNoModLvl multiplies p1 by a vector of uint64 coefficients and adds the result on p2 without modular reduction.

func (*Ring) MulByVectorMontgomeryLvl added in v2.4.0 

func (r *Ring) MulByVectorMontgomeryLvl(level int, p1 *Poly, vector []uint64, p2 *Poly)

MulByVectorMontgomeryLvl multiplies p1 by a vector of uint64 coefficients and writes the result on p2.

func (*Ring) MulCoeffs 

func (r *Ring) MulCoeffs(p1, p2, p3 *Poly)

MulCoeffs multiplies p1 by p2 coefficient-wise, performs a Barrett modular reduction and writes the result on p3.

func (*Ring) MulCoeffsAndAdd 

func (r *Ring) MulCoeffsAndAdd(p1, p2, p3 *Poly)

MulCoeffsAndAdd multiplies p1 by p2 coefficient-wise with a Barret modular reduction and adds the result to p3.

func (*Ring) MulCoeffsAndAddLvl added in v2.4.0 

func (r *Ring) MulCoeffsAndAddLvl(level int, p1, p2, p3 *Poly)

MulCoeffsAndAddLvl multiplies p1 by p2 coefficient-wise with a Barret modular reduction and adds the result to p3.

func (*Ring) MulCoeffsAndAddNoMod 

func (r *Ring) MulCoeffsAndAddNoMod(p1, p2, p3 *Poly)

MulCoeffsAndAddNoMod multiplies p1 by p2 coefficient-wise with a Barrett modular reduction and adds the result to p3 without modular reduction.

func (*Ring) MulCoeffsAndAddNoModLvl added in v2.4.0 

func (r *Ring) MulCoeffsAndAddNoModLvl(level int, p1, p2, p3 *Poly)

MulCoeffsAndAddNoModLvl multiplies p1 by p2 coefficient-wise with a Barrett modular reduction and adds the result to p3 without modular reduction.

func (*Ring) MulCoeffsConstant 

func (r *Ring) MulCoeffsConstant(p1, p2, p3 *Poly)

MulCoeffsConstant multiplies p1 by p2 coefficient-wise with a constant-time Barrett modular reduction and writes the result on p3.

func (*Ring) MulCoeffsConstantLvl added in v2.4.0 

func (r *Ring) MulCoeffsConstantLvl(level int, p1, p2, p3 *Poly)

MulCoeffsConstantLvl multiplies p1 by p2 coefficient-wise with a constant-time Barrett modular reduction and writes the result on p3.

func (*Ring) MulCoeffsLvl added in v2.4.0 

func (r *Ring) MulCoeffsLvl(level int, p1, p2, p3 *Poly)

MulCoeffsLvl multiplies p1 by p2 coefficient-wise, performs a Barrett modular reduction and writes the result on p3.

func (*Ring) MulCoeffsMontgomery 

func (r *Ring) MulCoeffsMontgomery(p1, p2, p3 *Poly)

MulCoeffsMontgomery multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and returns the result on p3.

func (*Ring) MulCoeffsMontgomeryAndAdd 

func (r *Ring) MulCoeffsMontgomeryAndAdd(p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndAdd multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and adds the result to p3.

func (*Ring) MulCoeffsMontgomeryAndAddLvl 

func (r *Ring) MulCoeffsMontgomeryAndAddLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndAddLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction for the moduli from q_0 up to q_level and adds the result to p3.

func (*Ring) MulCoeffsMontgomeryAndAddNoMod 

func (r *Ring) MulCoeffsMontgomeryAndAddNoMod(p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndAddNoMod multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and adds the result to p3 without modular reduction.

func (*Ring) MulCoeffsMontgomeryAndAddNoModLvl 

func (r *Ring) MulCoeffsMontgomeryAndAddNoModLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndAddNoModLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction for the moduli from q_0 up to q_level and adds the result to p3 without modular reduction.

func (*Ring) MulCoeffsMontgomeryAndSub 

func (r *Ring) MulCoeffsMontgomeryAndSub(p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndSub multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and subtracts the result from p3.

func (*Ring) MulCoeffsMontgomeryAndSubLvl added in v2.2.0 

func (r *Ring) MulCoeffsMontgomeryAndSubLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndSubLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and subtracts the result from p3.

func (*Ring) MulCoeffsMontgomeryAndSubNoMod 

func (r *Ring) MulCoeffsMontgomeryAndSubNoMod(p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndSubNoMod multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and subtracts the result from p3 without modular reduction.

func (*Ring) MulCoeffsMontgomeryAndSubNoModLvl added in v2.4.0 

func (r *Ring) MulCoeffsMontgomeryAndSubNoModLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndSubNoModLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and subtracts the result from p3 without modular reduction.

func (*Ring) MulCoeffsMontgomeryConstant 

func (r *Ring) MulCoeffsMontgomeryConstant(p1, p2, p3 *Poly)

MulCoeffsMontgomeryConstant multiplies p1 by p2 coefficient-wise with a constant-time Montgomery modular reduction and writes the result on p3.

func (*Ring) MulCoeffsMontgomeryConstantAndAddNoMod added in v2.1.0 

func (r *Ring) MulCoeffsMontgomeryConstantAndAddNoMod(p1, p2, p3 *Poly)

MulCoeffsMontgomeryConstantAndAddNoMod multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and adds the result to p3 without modular reduction. Return values in [0, 3q-1]

func (*Ring) MulCoeffsMontgomeryConstantAndAddNoModLvl 

func (r *Ring) MulCoeffsMontgomeryConstantAndAddNoModLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryConstantAndAddNoModLvl multiplies p1 by p2 coefficient-wise with a constant-time Montgomery modular reduction for the moduli from q_0 up to q_level and adds the result to p3 without modular reduction. Return values in [0, 3q-1]

func (*Ring) MulCoeffsMontgomeryConstantAndNegLvl added in v2.4.0 

func (r *Ring) MulCoeffsMontgomeryConstantAndNegLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryConstantAndNegLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction for the moduli from q_0 up to q_level and returns the negative result on p3.

func (*Ring) MulCoeffsMontgomeryConstantAndSubNoModLvl added in v2.4.0 

func (r *Ring) MulCoeffsMontgomeryConstantAndSubNoModLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryConstantAndSubNoModLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and subtracts the result from p3 without modular reduction. Return values in [0, 3q-1]

func (*Ring) MulCoeffsMontgomeryConstantLvl added in v2.1.0 

func (r *Ring) MulCoeffsMontgomeryConstantLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryConstantLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction for the moduli from q_0 up to q_level and returns the result on p3.

func (*Ring) MulCoeffsMontgomeryLvl 

func (r *Ring) MulCoeffsMontgomeryLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction for the moduli from q_0 up to q_level and returns the result on p3.

func (*Ring) MulScalar 

func (r *Ring) MulScalar(p1 *Poly, scalar uint64, p2 *Poly)

MulScalar multiplies each coefficient of p1 by a scalar and writes the result on p2.

func (*Ring) MulScalarBigint 

func (r *Ring) MulScalarBigint(p1 *Poly, scalar *big.Int, p2 *Poly)

MulScalarBigint multiplies each coefficient of p1 by a big.Int scalar and writes the result on p2.

func (*Ring) MulScalarBigintLvl 

func (r *Ring) MulScalarBigintLvl(level int, p1 *Poly, scalar *big.Int, p2 *Poly)

MulScalarBigintLvl multiplies each coefficient of p1 by a big.Int scalar for the moduli from q_0 up to q_level and writes the result on p2.

func (*Ring) MulScalarLvl 

func (r *Ring) MulScalarLvl(level int, p1 *Poly, scalar uint64, p2 *Poly)

MulScalarLvl multiplies each coefficient of p1 by a scalar for the moduli from q_0 up to q_level and writes the result on p2.

func (*Ring) MultByMonomial 

func (r *Ring) MultByMonomial(p1 *Poly, monomialDeg int, p2 *Poly)

MultByMonomial multiplies p1 by x^monomialDeg and writes the result on p2.

func (*Ring) MultByMonomialNew 

func (r *Ring) MultByMonomialNew(p1 *Poly, monomialDeg int) (p2 *Poly)

MultByMonomialNew multiplies p1 by x^monomialDeg and writes the result on a new polynomial p2.

func (*Ring) NTT 

func (r *Ring) NTT(p1, p2 *Poly)

NTT computes the NTT of p1 and returns the result on p2.

func (*Ring) NTTLazy added in v2.1.0 

func (r *Ring) NTTLazy(p1, p2 *Poly)

NTTLazy computes the NTT of p1 and returns the result on p2. Output values are in the range [0, 2q-1]

func (*Ring) NTTLazyLvl added in v2.1.0 

func (r *Ring) NTTLazyLvl(level int, p1, p2 *Poly)

NTTLazyLvl computes the NTT of p1 and returns the result on p2. The value level defines the number of moduli of the input polynomials. Output values are in the range [0, 2q-1]

func (*Ring) NTTLvl 

func (r *Ring) NTTLvl(level int, p1, p2 *Poly)

NTTLvl computes the NTT of p1 and returns the result on p2. The value level defines the number of moduli of the input polynomials.

func (*Ring) NTTSingle added in v2.4.0 

func (r *Ring) NTTSingle(level int, p1, p2 []uint64)

NTTSingle computes the NTT of p1 and returns the result on p2. The level-th moduli of the ring NTT params are used.

func (*Ring) NTTSingleLazy added in v2.4.0 

func (r *Ring) NTTSingleLazy(level int, p1, p2 []uint64)

NTTSingleLazy computes the NTT of p1 and returns the result on p2. The level-th moduli of the ring NTT params are used. Output values are in the range [0, 2q-1]

func (*Ring) Neg 

func (r *Ring) Neg(p1, p2 *Poly)

Neg sets all coefficients of p1 to their additive inverse and writes the result on p2.

func (*Ring) NegLvl 

func (r *Ring) NegLvl(level int, p1, p2 *Poly)

NegLvl sets the coefficients of p1 to their additive inverse for the moduli from q_0 up to q_level and writes the result on p2.

func (*Ring) NewPoly 

func (r *Ring) NewPoly() *Poly

NewPoly creates a new polynomial with all coefficients set to 0.

func (*Ring) NewPolyLvl 

func (r *Ring) NewPolyLvl(level int) *Poly

NewPolyLvl creates a new polynomial with all coefficients set to 0.

func (*Ring) Permute 

func (r *Ring) Permute(polIn *Poly, gen uint64, polOut *Poly)

Permute applies the Galois transform on a polynomial outside of the NTT domain. It maps the coefficients x^i to x^(gen*i) It must be noted that the result cannot be in-place.

func (*Ring) PermuteNTT added in v2.4.0 

func (r *Ring) PermuteNTT(polIn *Poly, gen uint64, polOut *Poly)

PermuteNTT applies the Galois transform on a polynomial in the NTT domain. It maps the coefficients x^i to x^(gen*i) It must be noted that the result cannot be in-place.

func (*Ring) PermuteNTTIndex added in v2.4.0 

func (r *Ring) PermuteNTTIndex(galEl uint64) (index []uint64)

PermuteNTTIndex computes the index table for PermuteNTT.

func (*Ring) PermuteNTTLvl added in v2.4.0 

func (r *Ring) PermuteNTTLvl(level int, polIn *Poly, gen uint64, polOut *Poly)

PermuteNTTLvl applies the Galois transform on a polynomial in the NTT domain, up to a given level. It maps the coefficients x^i to x^(gen*i) It must be noted that the result cannot be in-place.

func (*Ring) PermuteNTTWithIndexAndAddNoModLvl added in v2.4.0 

func (r *Ring) PermuteNTTWithIndexAndAddNoModLvl(level int, polIn *Poly, index []uint64, polOut *Poly)

PermuteNTTWithIndexAndAddNoModLvl applies the Galois transform on a polynomial in the NTT domain, up to a given level, and adds the result to the output polynomial without modular reduction. It maps the coefficients x^i to x^(gen*i) using the PermuteNTTIndex table. It must be noted that the result cannot be in-place.

func (*Ring) PermuteNTTWithIndexLvl added in v2.4.0 

func (r *Ring) PermuteNTTWithIndexLvl(level int, polIn *Poly, index []uint64, polOut *Poly)

PermuteNTTWithIndexLvl applies the Galois transform on a polynomial in the NTT domain, up to a given level. It maps the coefficients x^i to x^(gen*i) using the PermuteNTTIndex table. It must be noted that the result cannot be in-place.

func (*Ring) PolyToBigint 

func (r *Ring) PolyToBigint(p1 *Poly, coeffsBigint []*big.Int)

PolyToBigint reconstructs p1 and returns the result in an array of Int.

func (*Ring) PolyToBigintCenteredLvl added in v2.2.0 

func (r *Ring) PolyToBigintCenteredLvl(level int, p1 *Poly, coeffsBigint []*big.Int)

PolyToBigintCenteredLvl reconstructs p1 and returns the result in an array of Int. Coefficients are centered around Q/2

func (*Ring) PolyToBigintLvl added in v2.2.0 

func (r *Ring) PolyToBigintLvl(level int, p1 *Poly, coeffsBigint []*big.Int)

PolyToBigintLvl reconstructs p1 and returns the result in an array of Int.

func (*Ring) PolyToString 

func (r *Ring) PolyToString(p1 *Poly) []string

PolyToString reconstructs p1 and returns the result in an array of string.

func (*Ring) Reduce 

func (r *Ring) Reduce(p1, p2 *Poly)

Reduce applies a modular reduction on the coefficients of p1 and writes the result on p2.

func (*Ring) ReduceConstant added in v2.1.0 

func (r *Ring) ReduceConstant(p1, p2 *Poly)

ReduceConstant applies a modular reduction on the coefficients of p1 and writes the result on p2. Return values in [0, 2q-1]

func (*Ring) ReduceConstantLvl added in v2.1.0 

func (r *Ring) ReduceConstantLvl(level int, p1, p2 *Poly)

ReduceConstantLvl applies a modular reduction on the coefficients of p1 for the moduli from q_0 up to q_level and writes the result on p2. Return values in [0, 2q-1]

func (*Ring) ReduceLvl 

func (r *Ring) ReduceLvl(level int, p1, p2 *Poly)

ReduceLvl applies a modular reduction on the coefficients of p1 for the moduli from q_0 up to q_level and writes the result on p2.

func (*Ring) Rotate 

func (r *Ring) Rotate(p1 *Poly, n int, p2 *Poly)

Rotate applies a Galois automorphism on p1 in NTT form, rotating the coefficients to the right by n positions, and writes the result on p2. It requires the data to be permuted in bit-reversal order before applying the NTT.

func (*Ring) SetCoefficientsBigint 

func (r *Ring) SetCoefficientsBigint(coeffs []*big.Int, p1 *Poly)

SetCoefficientsBigint sets the coefficients of p1 from an array of Int variables.

func (*Ring) SetCoefficientsBigintLvl 

func (r *Ring) SetCoefficientsBigintLvl(level int, coeffs []*big.Int, p1 *Poly)

SetCoefficientsBigintLvl sets the coefficients of p1 from an array of Int variables.

func (*Ring) SetCoefficientsInt64 

func (r *Ring) SetCoefficientsInt64(coeffs []int64, p1 *Poly)

SetCoefficientsInt64 sets the coefficients of p1 from an int64 array.

func (*Ring) SetCoefficientsString 

func (r *Ring) SetCoefficientsString(coeffs []string, p1 *Poly)

SetCoefficientsString parses an array of string as Int variables, and sets the coefficients of p1 with these Int variables.

func (*Ring) SetCoefficientsUint64 

func (r *Ring) SetCoefficientsUint64(coeffs []uint64, p1 *Poly)

SetCoefficientsUint64 sets the coefficients of p1 from an uint64 array.

func (*Ring) Shift 

func (r *Ring) Shift(p1 *Poly, n int, p2 *Poly)

Shift circulary shifts the coefficients of the polynomial p1 by n positions to the left and writes the result on p2.

func (*Ring) StandardRing added in v2.4.0 

func (r *Ring) StandardRing() (*Ring, error)

StandardRing returns the standard ring of the receiver ring. If `r.Type()==Standard`, then the method returns the receiver. if `r.Type()==ConjugateInvariant`, then the method returns a ring with ring degree 2N. The returned Ring is a shallow copy of the receiver.

func (*Ring) Sub 

func (r *Ring) Sub(p1, p2, p3 *Poly)

Sub subtracts p2 to p1 coefficient-wise and writes the result on p3.

func (*Ring) SubLvl 

func (r *Ring) SubLvl(level int, p1, p2, p3 *Poly)

SubLvl subtracts p2 to p1 coefficient-wise and writes the result on p3.

func (*Ring) SubNoMod 

func (r *Ring) SubNoMod(p1, p2, p3 *Poly)

SubNoMod subtracts p2 to p1 coefficient-wise without modular reduction and returns the result on p3.

func (*Ring) SubNoModLvl 

func (r *Ring) SubNoModLvl(level int, p1, p2, p3 *Poly)

SubNoModLvl subtracts p2 to p1 coefficient-wise without modular reduction for the moduli from q_0 up to q_level and writes the result on p3.

func (*Ring) SubScalar 

func (r *Ring) SubScalar(p1 *Poly, scalar uint64, p2 *Poly)

SubScalar subtracts a scalar from each coefficient of p1 and writes the result on p2.

func (*Ring) SubScalarBigint 

func (r *Ring) SubScalarBigint(p1 *Poly, scalar *big.Int, p2 *Poly)

SubScalarBigint subtracts a big.Int scalar from each coefficient of p1 and writes the result on p2.

func (*Ring) SubScalarBigintLvl added in v2.4.0 

func (r *Ring) SubScalarBigintLvl(level int, p1 *Poly, scalar *big.Int, p2 *Poly)

SubScalarBigintLvl subtracts a big.Int scalar from each coefficient of p1 and writes the result on p2.

func (*Ring) SubScalarLvl added in v2.4.0 

func (r *Ring) SubScalarLvl(level int, p1 *Poly, scalar uint64, p2 *Poly)

SubScalarLvl subtracts a scalar from each coefficient of p1 and writes the result on p2.

func (*Ring) Type added in v2.4.0 

func (r *Ring) Type() Type

Type returns the Type of the ring which might be either `Standard` or `ConjugateInvariant`.

func (*Ring) UnfoldConjugateInvariantToStandard added in v2.4.0 

func (r *Ring) UnfoldConjugateInvariantToStandard(level int, polyConjugateInvariant, polyStd *Poly)

UnfoldConjugateInvariantToStandard maps the compressed representation (N/2 coefficients) of Z_Q[X+X^-1]/(X^2N + 1) to full representation in Z_Q[X]/(X^2N+1). Requires degree(polyConjugateInvariant) = 2*degree(polyStd). Requires that polyStd and polyConjugateInvariant share the same moduli.

func (*Ring) UnmarshalBinary 

func (r *Ring) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes a slice of bytes on the target Ring.

type Sampler added in v2.3.0 

type Sampler interface {
	Read(pOut *Poly)
}

Sampler is an interface for random polynomial samplers. It has a single Read method which takes as argument the polynomial to be populated according to the Sampler's distribution.

type Scaler 

type Scaler interface {
	// DivByQOverTRounded returns p1 scaled by a factor t/Q and mod t on the receiver p2.
	DivByQOverTRounded(p1, p2 *Poly)
}

Scaler is an interface that rescales polynomial coefficients by a fraction t/Q.

type SimpleScaler 

type SimpleScaler struct {
	// contains filtered or unexported fields
}

SimpleScaler implements the Scaler interface by performing an RNS reconstruction and scaling by t/Q. This implementation of the Scaler interface is less efficient than the RNSScaler, but uses simple multi-precision arithmetic of the math/big package.

func NewSimpleScaler 

func NewSimpleScaler(t uint64, ringQ *Ring) (ss *SimpleScaler)

NewSimpleScaler creates a new SimpleScaler from t, the modulus under which the reconstruction is returned, and ringQ, the Ring in which the polynomial to reconstruct is represented.

func (*SimpleScaler) DivByQOverTRounded 

func (ss *SimpleScaler) DivByQOverTRounded(p1, p2 *Poly)

DivByQOverTRounded returns p1 scaled by a factor t/Q and mod t on the receiver p2.

type TernarySampler 

type TernarySampler struct {
	// contains filtered or unexported fields
}

TernarySampler keeps the state of a polynomial sampler in the ternary distribution.

func NewTernarySampler 

func NewTernarySampler(prng utils.PRNG, baseRing *Ring, p float64, montgomery bool) *TernarySampler

NewTernarySampler creates a new instance of TernarySampler from a PRNG, the ring definition and the distribution parameters: p is the probability of a coefficient being 0, (1-p)/2 is the probability of 1 and -1. If "montgomery" is set to true, polynomials read from this sampler are in Montgomery form.

func NewTernarySamplerSparse 

func NewTernarySamplerSparse(prng utils.PRNG, baseRing *Ring, hw int, montgomery bool) *TernarySampler

NewTernarySamplerSparse creates a new instance of a fixed-hamming-weight TernarySampler from a PRNG, the ring definition and the desired hamming weight for the output polynomials. If "montgomery" is set to true, polynomials read from this sampler are in Montgomery form.

func (*TernarySampler) Read 

func (ts *TernarySampler) Read(pol *Poly)

Read samples a polynomial into pol.

func (*TernarySampler) ReadLvl added in v2.1.0 

func (ts *TernarySampler) ReadLvl(lvl int, pol *Poly)

ReadLvl samples a polynomial into pol at the speciefied level.

func (*TernarySampler) ReadLvlNew added in v2.1.0 

func (ts *TernarySampler) ReadLvlNew(lvl int) (pol *Poly)

ReadLvlNew allocates and samples a polynomial at the speficied level.

func (*TernarySampler) ReadNew 

func (ts *TernarySampler) ReadNew() (pol *Poly)

ReadNew allocates and samples a polynomial at the max level.

type Type added in v2.4.0 

type Type int

Type is the type of ring used by the cryptographic scheme

func (Type) MarshalJSON added in v2.4.0 

func (rt Type) MarshalJSON() ([]byte, error)

MarshalJSON marshals the receiver Type into a JSON []byte

func (Type) String added in v2.4.0 

func (rt Type) String() string

String returns the string representation of the ring Type

func (*Type) UnmarshalJSON added in v2.4.0 

func (rt *Type) UnmarshalJSON(b []byte) error

UnmarshalJSON reads a JSON byte slice into the receiver Type

type UniformSampler 

type UniformSampler struct {
	// contains filtered or unexported fields
}

UniformSampler wraps a util.PRNG and represents the state of a sampler of uniform polynomials.

func NewUniformSampler 

func NewUniformSampler(prng utils.PRNG, baseRing *Ring) *UniformSampler

NewUniformSampler creates a new instance of UniformSampler from a PRNG and ring definition.

func (*UniformSampler) Read 

func (uniformSampler *UniformSampler) Read(Pol *Poly)

Read generates a new polynomial with coefficients following a uniform distribution over [0, Qi-1].

func (*UniformSampler) ReadLvl added in v2.2.0 

func (uniformSampler *UniformSampler) ReadLvl(level int, Pol *Poly)

ReadLvl generates a new polynomial with coefficients following a uniform distribution over [0, Qi-1].

func (*UniformSampler) ReadLvlNew added in v2.1.0 

func (uniformSampler *UniformSampler) ReadLvlNew(level int) (Pol *Poly)

ReadLvlNew generates a new polynomial with coefficients following a uniform distribution over [0, Qi-1]. Polynomial is created at the specified level.

func (*UniformSampler) ReadNew 

func (uniformSampler *UniformSampler) ReadNew() (Pol *Poly)

ReadNew generates a new polynomial with coefficients following a uniform distribution over [0, Qi-1]. Polynomial is created at the max level.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.