modular

package
v0.1.0 Latest Latest
Warning

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

 Go to latest Published: Feb 16, 2026 License: Apache-2.0 Imports: 10 Imported by: 0

README

modular

Package modular provides CRT-accelerated modular arithmetic for cryptographic applications such as RSA and Paillier.

Overview

This package implements the Arithmetic interface for modular operations, with specialized implementations that use the Chinese Remainder Theorem (CRT) for acceleration when the factorization is known. All operations use constant-time arithmetic from the numct package.

Key Types

SimpleModulus
  • SimpleModulus: Basic modular arithmetic over a single modulus. Used when the factorization is unknown or not applicable.
OddPrimeFactors (RSA-style)
  • OddPrimeFactors: CRT-accelerated arithmetic modulo n = p·q where p and q are distinct odd primes. Operations are parallelized across the two factors and recombined using CRT.
OddPrimeSquareFactors (Paillier-style)
  • OddPrimeSquare: Arithmetic modulo p² for a single odd prime p.
  • OddPrimeSquareFactors: CRT-accelerated arithmetic modulo n² = (p·q)² where p and q are distinct odd primes. Used in Paillier encryption.

Usage Notes

  • MultiBaseExp computes multiple exponentiations with the same exponent in parallel.
  • OddPrimeSquareFactors.ExpToN(out, a) Computes a^n mod n² slightly more efficiently than plain CRT-based modular exponentiation (used in Paillier)
  • All types support CBOR serialization for the Arithmetic interface.

Documentation

Overview

Package modular provides CRT-accelerated modular arithmetic for cryptographic applications such as RSA and Paillier.

See README.md for details.

Index

Constants

View Source 
const (
	SimpleModulusTag         = 5006
	OddPrimeFactorsTag       = 5007
	OddPrimeSquareFactorsTag = 5008
)

Variables

View Source 
var (
	ErrFailed = errs.New("failed")
)

Functions

This section is empty.

Types

type Arithmetic 

type Arithmetic interface {
	// Modulus returns the modulus used in the modular arithmetic.
	Modulus() *numct.Modulus
	// MultiplicativeOrder returns the multiplicative order of the modulus.
	MultiplicativeOrder() algebra.Cardinal
	// ModMul computes out = (a * b) mod m.
	ModMul(out, a, b *numct.Nat)
	// ModDiv computes out = (a / b) mod m.
	ModDiv(out, a, b *numct.Nat) ct.Bool
	// ModExp computes out = (base ^ exp) mod m.
	ModExp(out, base, exp *numct.Nat)
	// ModExpI computes out = (base ^ exp) mod m, where exp is a signed integer.
	ModExpI(out, base *numct.Nat, exp *numct.Int)
	// MultiBaseExp computes out[i] = (bases[i] ^ exp) mod m for all i.
	MultiBaseExp(out []*numct.Nat, bases []*numct.Nat, exp *numct.Nat)
	// ModInv computes out = (a^{-1}) mod m.
	ModInv(out, a *numct.Nat) ct.Bool
}

Arithmetic defines modular arithmetic operations over a modulus. Implementations may use CRT or other optimizations as appropriate.

type OddPrimeFactors 

type OddPrimeFactors struct {
	Params *crt.ParamsExtended // CRT parameters for p and q
	N      *numct.Modulus      // n = p * q
	PhiP   *numct.Modulus      // φ(p) = p - 1
	PhiQ   *numct.Modulus      // φ(q) = q - 1
	Phi    *numct.Modulus      // φ(n) = (p - 1)*(q - 1)
}

OddPrimeFactors implements modular arithmetic modulo n = p * q, where p and q are distinct odd primes.

func NewOddPrimeFactors 

func NewOddPrimeFactors(p, q *numct.Nat) (factors *OddPrimeFactors, ok ct.Bool)

NewOddPrimeFactors constructs an OddPrimeFactors modular arithmetic instance from the given odd prime factors p and q. Returns ct.False if the inputs are invalid (not odd primes or equal).

func (*OddPrimeFactors) Lift 

func (m *OddPrimeFactors) Lift() (lifted *OddPrimeSquareFactors, ok ct.Bool)

Lift constructs an OddPrimeSquareFactors modular arithmetic instance by lifting the modulus n = p * q to n^2 = p^2 * q^2. Returns ct.False if the lift operation fails.

func (*OddPrimeFactors) MarshalCBOR 

func (m *OddPrimeFactors) MarshalCBOR() ([]byte, error)

func (*OddPrimeFactors) ModDiv 

func (m *OddPrimeFactors) ModDiv(out, a, b *numct.Nat) ct.Bool

ModDiv computes out = (a / b) mod n.

func (*OddPrimeFactors) ModExp 

func (m *OddPrimeFactors) ModExp(out, base, exp *numct.Nat)

ModExp computes out = (base ^ exp) mod n.

func (*OddPrimeFactors) ModExpI 

func (m *OddPrimeFactors) ModExpI(out, base *numct.Nat, exp *numct.Int)

ModExpI computes out = (base ^ exp) mod n, where exp is a signed integer.

func (*OddPrimeFactors) ModInv 

func (m *OddPrimeFactors) ModInv(out, a *numct.Nat) ct.Bool

ModInv computes out = (a^{-1}) mod n.

func (*OddPrimeFactors) ModMul 

func (m *OddPrimeFactors) ModMul(out, a, b *numct.Nat)

ModMul computes out = (a * b) mod n.

func (*OddPrimeFactors) Modulus 

func (m *OddPrimeFactors) Modulus() *numct.Modulus

Modulus returns the modulus n = p * q.

func (*OddPrimeFactors) MultiBaseExp 

func (m *OddPrimeFactors) MultiBaseExp(out, bases []*numct.Nat, exp *numct.Nat)

MultiBaseExp computes out[i] = (bases[i] ^ exp) mod n for all i.

func (*OddPrimeFactors) MultiplicativeOrder 

func (m *OddPrimeFactors) MultiplicativeOrder() algebra.Cardinal

MultiplicativeOrder returns the multiplicative order φ(n) = (p-1)*(q-1).

func (*OddPrimeFactors) UnmarshalCBOR 

func (m *OddPrimeFactors) UnmarshalCBOR(data []byte) error

type OddPrimeSquare 

type OddPrimeSquare struct {
	Factor     *numct.Modulus // p
	Squared    *numct.Modulus // p^2
	PhiFactor  *numct.Modulus // φ(p) = p - 1
	PhiSquared *numct.Modulus // φ(p^2) = p * (p - 1)
}

OddPrimeSquare implements modular arithmetic modulo p^2, where p is an odd prime.

func NewOddPrimeSquare 

func NewOddPrimeSquare(oddPrimeFactor *numct.Nat) (m *OddPrimeSquare, ok ct.Bool)

NewOddPrimeSquare constructs an OddPrimeSquare modular arithmetic instance from the given odd prime factor p. Returns ct.False if the input is invalid (not an odd prime).

func (*OddPrimeSquare) Modulus 

func (m *OddPrimeSquare) Modulus() *numct.Modulus

ModExp computes out = (base ^ exp) mod p^2.

func (*OddPrimeSquare) MultiplicativeOrder 

func (m *OddPrimeSquare) MultiplicativeOrder() algebra.Cardinal

ModExp computes out = (base ^ exp) mod p^2.

type OddPrimeSquareFactors 

type OddPrimeSquareFactors struct {
	CrtModN  *OddPrimeFactors    // CRT parameters for p and q
	CrtModN2 *crt.ParamsExtended // CRT parameters for p^2 and q^2
	P        *OddPrimeSquare     // parameters for p
	Q        *OddPrimeSquare     // parameters for q
	N2       *numct.Modulus      // n^2 = (p * q)^2
	NExpP2   *numct.Nat          // Ep2 = p * (N mod (p-1))
	NExpQ2   *numct.Nat          // Eq2 = q * (N mod (q-1))
	PhiN2    *numct.Modulus      // φ(n^2) = φ(p^2)*φ(q^2)
}

OddPrimeSquareFactors implements modular arithmetic modulo n^2 = (p * q)^2, where p and q are distinct odd primes.

func NewOddPrimeSquareFactors 

func NewOddPrimeSquareFactors(firstPrime, secondPrime *numct.Nat) (m *OddPrimeSquareFactors, ok ct.Bool)

NewOddPrimeSquareFactors constructs an OddPrimeSquareFactors modular arithmetic instance from the given odd prime factors p and q. Returns ct.False if the inputs are invalid (not distinct).

func (*OddPrimeSquareFactors) ExpToN 

func (m *OddPrimeSquareFactors) ExpToN(out, a *numct.Nat)

ExpToN computes out = (a ^ N) mod n^2 using direct CRT mod-exp.

func (*OddPrimeSquareFactors) MarshalCBOR 

func (m *OddPrimeSquareFactors) MarshalCBOR() ([]byte, error)

func (*OddPrimeSquareFactors) ModDiv 

func (m *OddPrimeSquareFactors) ModDiv(out, a, b *numct.Nat) ct.Bool

ModDiv computes out = (a / b) mod n^2.

func (*OddPrimeSquareFactors) ModExp 

func (m *OddPrimeSquareFactors) ModExp(out, base, exp *numct.Nat)

ModExp computes out = (base ^ exp) mod n^2.

func (*OddPrimeSquareFactors) ModExpI 

func (m *OddPrimeSquareFactors) ModExpI(out, base *numct.Nat, exp *numct.Int)

ModExpI computes out = (base ^ exp) mod n^2, where exp is a signed integer.

func (*OddPrimeSquareFactors) ModInv 

func (m *OddPrimeSquareFactors) ModInv(out, a *numct.Nat) ct.Bool

ModInv computes out = (a^{-1}) mod n^2.

func (*OddPrimeSquareFactors) ModMul 

func (m *OddPrimeSquareFactors) ModMul(out, a, b *numct.Nat)

ModMul computes out = (a * b) mod n^2.

func (*OddPrimeSquareFactors) Modulus 

func (m *OddPrimeSquareFactors) Modulus() *numct.Modulus

Modulus returns the modulus n^2 = (p * q)^2.

func (*OddPrimeSquareFactors) MultiBaseExp 

func (m *OddPrimeSquareFactors) MultiBaseExp(out, bases []*numct.Nat, exp *numct.Nat)

MultiBaseExp computes out[i] = (bases[i] ^ exp) mod n^2 for all i.

func (*OddPrimeSquareFactors) MultiplicativeOrder 

func (m *OddPrimeSquareFactors) MultiplicativeOrder() algebra.Cardinal

MultiplicativeOrder returns the multiplicative order φ(n^2) = φ(p^2)*φ(q^2).

func (*OddPrimeSquareFactors) UnmarshalCBOR 

func (m *OddPrimeSquareFactors) UnmarshalCBOR(data []byte) error

type SimpleModulus 

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

SimpleModulus implements modular arithmetic modulo a single modulus m.

func NewSimple 

func NewSimple(m *numct.Modulus) (simple *SimpleModulus, ok ct.Bool)

NewSimple constructs a SimpleModulus modular arithmetic instance from the given modulus m. Returns ct.False if the input is invalid (nil).

func (*SimpleModulus) Lift 

func (m *SimpleModulus) Lift() (lifted *SimpleModulus, ok ct.Bool)

Lift constructs a SimpleModulus modular arithmetic instance by lifting the modulus m to m^2. Returns ct.False if the lift operation fails.

func (*SimpleModulus) MarshalCBOR 

func (m *SimpleModulus) MarshalCBOR() ([]byte, error)

func (*SimpleModulus) ModDiv 

func (m *SimpleModulus) ModDiv(out, a, b *numct.Nat) ct.Bool

ModDiv computes out = (a / b) mod m.

func (*SimpleModulus) ModExp 

func (m *SimpleModulus) ModExp(out, base, exp *numct.Nat)

ModExp computes out = (base ^ exp) mod m.

func (*SimpleModulus) ModExpI 

func (m *SimpleModulus) ModExpI(out, base *numct.Nat, exp *numct.Int)

ModExpI computes out = (base ^ exp) mod m, where exp is a signed integer.

func (*SimpleModulus) ModInv 

func (m *SimpleModulus) ModInv(out, a *numct.Nat) ct.Bool

ModInv computes out = (a^{-1}) mod m.

func (*SimpleModulus) ModMul 

func (m *SimpleModulus) ModMul(out, a, b *numct.Nat)

ModMul computes out = (a * b) mod m.

func (*SimpleModulus) Modulus 

func (m *SimpleModulus) Modulus() *numct.Modulus

Modulus returns the modulus m.

func (*SimpleModulus) MultiBaseExp 

func (m *SimpleModulus) MultiBaseExp(out, bases []*numct.Nat, exp *numct.Nat)

MultiBaseExp computes out[i] = (bases[i] ^ exp) mod m for all i.

func (*SimpleModulus) MultiplicativeOrder 

func (*SimpleModulus) MultiplicativeOrder() algebra.Cardinal

MultiplicativeOrder returns an unknown cardinal for SimpleModulus.

func (*SimpleModulus) UnmarshalCBOR 

func (m *SimpleModulus) UnmarshalCBOR(data []byte) error

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.