Documentation
¶
Overview ¶
Package modarith provides modular-arithmetic primitives shared across every Lux cryptographic protocol. Barrett reduction, Montgomery form, add/sub/mul mod q, and the ReductionBudget type that lazy reduction kernels consult.
LP-107 §"Modular arithmetic" — the canonical motivation. All ad-hoc Montgomery/Barrett code in luxfi/lattice, luxfi/pulsar, and luxfi/fhe converges here over Phases 3-5 of LP-107.
The body of this package delegates to the existing canonical implementations in github.com/luxfi/lattice/v7/ring and github.com/luxfi/lattice/v7/types so that v0.1.x callers see no behavior change. v0.2.0 inverts the dependency: lattice/ring will import this package and thin out into a wrapper.
Index ¶
- func AddMod(a, b, q uint64) uint64
- func CondSubtract(x, q uint64) uint64
- func FromMontgomery(xMont uint64, m *Modulus) uint64
- func LazyModeFits(mode ReductionMode, q uint64) bool
- func MontMulMod(a, b uint64, m *Modulus) uint64
- func MulMod(a, b, q uint64) uint64
- func SubMod(a, b, q uint64) uint64
- func ToMontgomery(x uint64, m *Modulus) uint64
- type Modulus
- type ReductionMode
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func CondSubtract ¶
CondSubtract returns x if x < q, else x - q. Branchless.
func FromMontgomery ¶
FromMontgomery returns x_mont * R^-1 mod q, i.e. recovers the standard-form value. Equivalent to MontMulMod(x_mont, 1, m).
func LazyModeFits ¶
func LazyModeFits(mode ReductionMode, q uint64) bool
LazyModeFits reports whether q fits the lazy mode without uint64 overflow.
func MontMulMod ¶
MontMulMod returns Montgomery multiplication: (a * b * R^-1) mod q where R = 2^64. Inputs and output are in Montgomery form. Use ToMontgomery / FromMontgomery for conversion.
func MulMod ¶
MulMod returns (a * b) mod q via 128-bit multiply + Div64. This is the slow-but-canonical reference path; production callers prefer Montgomery (MontMulMod) or Barrett (BarrettMulMod) for hot paths.
func ToMontgomery ¶
ToMontgomery returns x * R mod q (R = 2^64). Equivalent to MontMulMod(x, R2, m) where R2 = R^2 mod q.
Types ¶
type Modulus ¶
type Modulus struct {
// Q is the prime modulus.
Q uint64
// QInv = -1 / Q mod 2^64; used by Montgomery reduction.
QInv uint64
// R2 = 2^128 mod Q; Montgomery form of 1.
R2 uint64
// Barrett[0..1] are the high/low 64-bit parts of floor(2^128 / Q);
// used by Barrett reduction.
Barrett [2]uint64
// Bits is the bit-length of Q (1..64).
Bits uint8
// Name is a stable human-readable name (e.g. "pulsar-q").
Name string
}
Modulus is a single prime modulus q with all derived constants the substrate needs to do fast modular arithmetic. Constructed once at parameter-set load time and reused.
Layout matches lattice/types.ReductionBudget so that future migration is byte-stable (LP-107 Phase 3).
type ReductionMode ¶
type ReductionMode uint8
ReductionMode mirrors lattice/types.ReductionMode for the lazy reduction budget. See package backend for the budget tracker.
Values are byte-equal to luxfi/lattice/v7/types.ReductionMode so ReductionBudget instances are interchangeable across the substrate.
const ( // ReductionStrictEveryOp normalises after every modular operation. ReductionStrictEveryOp ReductionMode = 0 // ReductionLazy2 allows result range [0, 2q). q < 2^63. ReductionLazy2 ReductionMode = 1 // ReductionLazy4 allows result range [0, 4q). q < 2^62. ReductionLazy4 ReductionMode = 2 // ReductionLazy8 allows result range [0, 8q). q < 2^61. ReductionLazy8 ReductionMode = 3 )
Source Files