subring

package
v1.4.1 Latest Latest
Warning

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

 Go to latest Published: May 13, 2026 License: BSD-3-Clause Imports: 7 Imported by: 0

Documentation

Overview

Package subring owns the Lattigo-derived Montgomery NTT body — SubRing layout, root-table generator, scalar primitives (MRed/MRedLazy/MForm/BRed/CRed/...), the loop-unrolled-by-16 NTT kernel, and the SIMD AVX2 dispatch hooks.

LP-107 Phase 3: this package is the single source of truth for the Montgomery NTT body. luxfi/lattice/v7/ring re-exports it as a thin shim so its downstream consumers (luxfi/pulsar, luxfi/fhe, luxfi/threshold, ...) compile unchanged. Application callers should route through one of:

  • github.com/luxfi/math/ntt — the Service / Backend interface (recommended for new code).
  • github.com/luxfi/lattice/v7/ring — the historical SubRing API for FHE-flavoured callers.

This package is NOT a general-purpose import target: its surface is optimized for the two consumers above and is not part of the public luxfi/math semver contract for downstream code.

Index

Constants

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

Standard and ConjugateInvariant are two types of Rings.

View Source 
const (
	// MinimumRingDegreeForLoopUnrolledNTT is the minimum ring degree
	// necessary for memory safe loop unrolling
	MinimumRingDegreeForLoopUnrolledNTT = 16
)
View Source 
const MinimumRingDegreeForLoopUnrolledOperations = 8

MinimumRingDegreeForLoopUnrolledOperations is the minimum ring degree required to safely perform loop-unrolled operations.

Variables

This section is empty.

Functions

func BRed 

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

BRed computes x*y mod q.

func BRedAdd 

func BRedAdd(a, q uint64, bredconstant [2]uint64) (r uint64)

BRedAdd computes a mod q.

func BRedAddLazy 

func BRedAddLazy(x, q uint64, bredconstant [2]uint64) uint64

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

func BRedLazy 

func BRedLazy(x, y, q uint64, bredconstant [2]uint64) (r uint64)

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

func BitReverse64 

func BitReverse64(index uint64, bitLen int) uint64

BitReverse64 returns the bit-reverse value of the input value, within a context of 2^bitLen.

func CRed 

func CRed(a, q uint64) uint64

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

func CheckFactors 

func CheckFactors(m uint64, factors []uint64) (err error)

CheckFactors checks that the given list of factors contains all the unique primes of m.

func CheckPrimitiveRoot 

func CheckPrimitiveRoot(g, q uint64, factors []uint64) (err error)

CheckPrimitiveRoot checks that g is a valid primitive root mod q, given the factors of q-1.

func GenBRedConstant 

func GenBRedConstant(q uint64) [2]uint64

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

func GenMRedConstant 

func GenMRedConstant(q uint64) (mredconstant uint64)

GenMRedConstant computes the constant mredconstant = (q^-1) mod 2^64 required for MRed.

func GetFactorECM 

func GetFactorECM(N *big.Int) (factor *big.Int)

GetFactorECM finds a factor of N using ECM factorization.

func GetFactorPollardRho 

func GetFactorPollardRho(m *big.Int) (d *big.Int)

GetFactorPollardRho implements Pollard's Rho algorithm for fast prime factorization, but this function only returns one factor per call This function can fail and return m.

func GetFactors 

func GetFactors(m *big.Int) (factors []*big.Int)

GetFactors returns all the prime factors of m. Only the unique primes are returned, not their power.

func IMForm 

func IMForm(a, q, mredconstant uint64) (r uint64)

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

func IMFormLazy 

func IMFormLazy(a, q, mredconstant uint64) (r uint64)

IMFormLazy 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 INTTConjugateInvariant 

func INTTConjugateInvariant(p1, p2 []uint64, N int, NInv, Q, MRedConstant uint64, roots []uint64)

INTTConjugateInvariant evaluates p2 = INTT(p1) in the closed sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1).

func INTTConjugateInvariantLazy 

func INTTConjugateInvariantLazy(p1, p2 []uint64, N int, NInv, Q, MRedConstant uint64, roots []uint64)

INTTConjugateInvariantLazy evaluates p2 = INTT(p1) in the closed sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1) with p2 in the range [0, 2*modulus-1].

func INTTStandard 

func INTTStandard(p1, p2 []uint64, N int, NInv, Q, MRedConstant uint64, roots []uint64)

INTTStandard evaluates p2 = INTTStandard(p1) in the given SubRing.

func INTTStandardLazy 

func INTTStandardLazy(p1, p2 []uint64, N int, NInv, Q, MRedConstant uint64, roots []uint64)

INTTStandardLazy evaluates p2 = INTT(p1) in the given SubRing with p2 in [0, 2*modulus-1].

func IsPrime 

func IsPrime(x uint64) bool

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

func MForm 

func MForm(a, q uint64, bredconstant [2]uint64) (r uint64)

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

func MFormLazy 

func MFormLazy(a, q uint64, bredconstant [2]uint64) (r uint64)

MFormLazy 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 MRed 

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

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

func MRedLazy 

func MRedLazy(x, y, q, mredconstant uint64) (r uint64)

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

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 ModExpPow2 

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

ModExpPow2 performs the modular exponentiation x^e mod p, where p is a power of two, x and p are required to be at most 64 bits to avoid an overflow.

func ModexpMontgomery 

func ModexpMontgomery(x uint64, e int, q, mredconstant uint64, bredconstant [2]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 NTTConjugateInvariant 

func NTTConjugateInvariant(p1, p2 []uint64, N int, Q, MRedConstant uint64, BRedConstant [2]uint64, roots []uint64)

NTTConjugateInvariant evaluates p2 = NTT(p1) in the sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1).

func NTTConjugateInvariantLazy 

func NTTConjugateInvariantLazy(p1, p2 []uint64, N int, Q, MRedConstant uint64, roots []uint64)

NTTConjugateInvariantLazy evaluates p2 = NTT(p1) in the sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1) with p2 in the range [0, 6*modulus-2].

func NTTStandard 

func NTTStandard(p1, p2 []uint64, N int, Q, MRedConstant uint64, BRedConstant [2]uint64, roots []uint64)

NTTStandard computes the NTTStandard in the given SubRing.

func NTTStandardLazy 

func NTTStandardLazy(p1, p2 []uint64, N int, Q, MRedConstant uint64, roots []uint64)

NTTStandardLazy computes the NTTStandard in the given SubRing with p2 in [0, 6*modulus-2].

func NewRandomWeierstrassCurve 

func NewRandomWeierstrassCurve(N *big.Int) (Weierstrass, Point)

NewRandomWeierstrassCurve generates a new random Weierstrass curve modulo N, along with a random point that lies on the curve.

func PrimitiveRoot 

func PrimitiveRoot(q uint64, factors []uint64) (uint64, []uint64, error)

PrimitiveRoot computes the smallest primitive root of the given prime q The unique factors of q-1 can be given to speed up the search for the root.

Types

type NTTTable 

type NTTTable struct {
	NthRoot       uint64   // Nthroot used for the NTT
	PrimitiveRoot uint64   // 2N-th primitive root
	RootsForward  []uint64 //powers of the 2N-th primitive root in Montgomery form (in bit-reversed order)
	RootsBackward []uint64 //powers of the inverse of the 2N-th primitive root in Montgomery form (in bit-reversed order)
	NInv          uint64   //[N^-1] mod Modulus in Montgomery form
}

NTTTable store all the constants that are specifically tied to the NTT.

type NumberTheoreticTransformer 

type NumberTheoreticTransformer interface {
	Forward(p1, p2 []uint64)
	ForwardLazy(p1, p2 []uint64)
	Backward(p1, p2 []uint64)
	BackwardLazy(p1, p2 []uint64)
}

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

func NewNumberTheoreticTransformerConjugateInvariant 

func NewNumberTheoreticTransformerConjugateInvariant(r *SubRing, n int) NumberTheoreticTransformer

func NewNumberTheoreticTransformerStandard 

func NewNumberTheoreticTransformerStandard(r *SubRing, n int) NumberTheoreticTransformer

type NumberTheoreticTransformerConjugateInvariant 

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

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 

func (rntt NumberTheoreticTransformerConjugateInvariant) Backward(p1, p2 []uint64)

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

func (NumberTheoreticTransformerConjugateInvariant) BackwardLazy 

func (rntt NumberTheoreticTransformerConjugateInvariant) BackwardLazy(p1, p2 []uint64)

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

func (NumberTheoreticTransformerConjugateInvariant) Forward 

func (rntt NumberTheoreticTransformerConjugateInvariant) Forward(p1, p2 []uint64)

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

func (NumberTheoreticTransformerConjugateInvariant) ForwardLazy 

func (rntt NumberTheoreticTransformerConjugateInvariant) ForwardLazy(p1, p2 []uint64)

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

type NumberTheoreticTransformerStandard 

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

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

func (NumberTheoreticTransformerStandard) Backward 

func (rntt NumberTheoreticTransformerStandard) Backward(p1, p2 []uint64)

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

func (NumberTheoreticTransformerStandard) BackwardLazy 

func (rntt NumberTheoreticTransformerStandard) BackwardLazy(p1, p2 []uint64)

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

func (NumberTheoreticTransformerStandard) Forward 

func (rntt NumberTheoreticTransformerStandard) Forward(p1, p2 []uint64)

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

func (NumberTheoreticTransformerStandard) ForwardLazy 

func (rntt NumberTheoreticTransformerStandard) ForwardLazy(p1, p2 []uint64)

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

type Point 

type Point struct {
	X, Y *big.Int
}

Point represents an elliptic curve point in standard coordinates.

type SubRing 

type SubRing struct {

	// Polynomial nb.Coefficients
	N int

	// Modulus
	Modulus uint64

	// Unique factors of Modulus-1
	Factors []uint64

	// 2^bit_length(Modulus) - 1
	Mask uint64

	// Fast reduction constants
	BRedConstant [2]uint64 // Barrett Reduction
	MRedConstant uint64    // Montgomery Reduction

	*NTTTable // NTT related constants
	// contains filtered or unexported fields
}

SubRing is a struct storing precomputation for fast modular reduction and NTT for a given modulus.

func NewSubRing 

func NewSubRing(N int, Modulus uint64) (s *SubRing, err error)

NewSubRing creates a new SubRing with the standard NTT. NTT constants still need to be generated using .GenNTTConstants(NthRoot uint64).

func NewSubRingWithCustomNTT 

func NewSubRingWithCustomNTT(N int, Modulus uint64, ntt func(*SubRing, int) NumberTheoreticTransformer, NthRoot int) (s *SubRing, err error)

NewSubRingWithCustomNTT creates a new SubRing with degree N and modulus Modulus with user-defined NTT transform and primitive Nth root of unity. Modulus should 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 *SubRing in the case of non NTT-enabling parameters.

func (*SubRing) GenerateNTTConstants 

func (s *SubRing) GenerateNTTConstants() (err error)

GenerateNTTConstants generates the NTT constant for the target SubRing. The fields `PrimitiveRoot` and `Factors` can be set manually to bypass the search for the primitive root (which requires to factor Modulus-1) and speedup the generation of the constants.

func (*SubRing) INTT 

func (s *SubRing) INTT(p1, p2 []uint64)

INTT evaluates p2 = INTT(p1).

func (*SubRing) INTTLazy 

func (s *SubRing) INTTLazy(p1, p2 []uint64)

INTTLazy evaluates p2 = INTT(p1) with p2 in [0, 2*modulus-1].

func (*SubRing) NTT 

func (s *SubRing) NTT(p1, p2 []uint64)

NTT evaluates p2 = NTT(p1).

func (*SubRing) NTTLazy 

func (s *SubRing) NTTLazy(p1, p2 []uint64)

NTTLazy evaluates p2 = NTT(p1) with p2 in [0, 6*modulus-2].

func (*SubRing) Type 

func (s *SubRing) Type() Type

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

type Type 

type Type int

Type is the type of ring used by the cryptographic scheme.

func (Type) String 

func (rt Type) String() string

String returns the string representation of the ring Type.

type Weierstrass 

type Weierstrass struct {
	A, B, N *big.Int
}

Weierstrass is an elliptic curve y^2 = x^3 + ax + b mod N.

func (*Weierstrass) Add 

func (w *Weierstrass) Add(P, Q Point) Point

Add adds two Weierstrass points together with respect to the underlying Weierstrass curve. This method does not check if the points lie on the underlying curve.

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.