README
¶
Library for arithmetic modulo any 193-bit to 256-bit modulus
This library only supports modular arithmetic.
- No boolean operations or other bitwise operations like shifts are supported.
- Speed is gained by postponing full reduction to canonical (least non-negative) residues.
- Internally any 256-bit representative of each residue class is used.
- Reduction to canonical residue is only performed when converting for external use or testing for equality of residues.
- Residues are treated as being different when their moduli are different. E.g. 2 mod 3 is not the same as 2 mod 4.
- Arrays of uint64 are treated as little-endian. Hence the array [4]uint64{ 1, 0, 0, 0 } contains the value 1.
The library is alloc-free, and code coverage is at 99.9%.
Security
This library is not meant to protect sensitive data like cryptographic keys.
Although some operations should be constant-time on most architectures, the library does not protect from e.g. timing or cache attacks.
Testing
Tests cover most properties of commutative rings. The one exception is transitivity of equality, as no meaningful test for this was found.
Structured as well as random test values are used.
Benchmarks
The speeds achieved in mod256 compared to uint256 below illustrate the performance advantage of designing specifically for modular arithmetic.
Note that the aim of uint256 is to provide a replacement for big.Int for 256-bit integers. Therefore there is only partially overlapping functionality, which is for modular addition and modular multiplication.
Ice Lake 1.5GHz M1 3.2GHz Skylake 2.2GHz Zen 2 3.6GHz Zen 3 3.9GHz
Mod256/Neg 3.94ns ± 0% 3.60ns ± 0% 3.35ns ± 0% 2.16ns ± 0% 1.83ns ± 0%
Mod256/Dbl 13.6ns ± 0% 5.76ns ± 0% 11.2ns ± 0% 5.86ns ± 0% 5.73ns ± 1%
Mod256/Sub 14.1ns ± 0% 6.49ns ± 0% 10.5ns ± 0% 6.73ns ± 0% 5.76ns ± 0%
Mod256/Sqr 104ns ± 0% 24.4ns ± 0% 70.8ns ± 0% 37.3ns ± 0% 36.2ns ± 0%
Mod256/Inv 10.6µs ± 0% 2.79µs ± 0% 8.38µs ± 0% 5.34µs ± 0% 4.50µs ± 0%
Mod256/Exp 34.8µs ± 0% 8.14µs ± 0% 24.4µs ± 0% 12.8µs ± 0% 12.3µs ± 0%
Mod256/ExpPrecomp 10.8µs ± 0% 2.57µs ± 0% 7.28µs ± 0% 3.91µs ± 0% 3.76µs ± 0%
Mod256/Add 13.9ns ± 1% 6.64ns ± 0% 10.7ns ± 0% 6.73ns ± 0% 5.85ns ± 3%
Mod256/Mul 112ns ± 0% 28.0ns ± 0% 77.5ns ± 0% 39.8ns ± 0% 37.8ns ± 0%
AddMod/mod256/uint256 40.4ns ± 0% 15.6ns ± 2% 32.3ns ± 0% 22.2ns ± 0% 19.6ns ± 0%
MulMod/mod256/uint256 328ns ± 0% 90.2ns ± 0% 237ns ± 0% 129ns ± 0% 114ns ± 0%
MulMod/mod256/uint256r 145ns ± 0% 40.3ns ± 0% 94.3ns ± 0% 51.8ns ± 0% 52.8ns ± 0%
Speedup factors:
Mod256/Add vs. AddMod 2.91 2.35 3.02 3.30 3.35
Mod256/Mul vs. MulMod 2.93 3.22 3.06 3.24 3.02
Mod256/Mul vs. MulMod(r) 1.29 1.44 1.22 1.30 1.40
All benchmarks were performed using Go version 1.17.6, and all report 0 B/op and 0 allocs/op, both for mod256 and uint256.
Summary:
- Modular addition is from 2.35 (M1) to 3.35 (Zen 3) times as fast as uint256.
- Modular multiplication is from 2.93 (Ice Lake) to 3.24 (Zen 2) times as fast as multiplication without reciprocal cache in uint256.
- Modular multiplication is from 22% (Skylake) to 44% (M1) faster than multiplication with reciprocal cache in uint256.
Documentation
¶
Overview ¶
Library for arithmetic modulo any 193-bit to 256-bit modulus
Index ¶
- type ExpBase
- type Modulus
- type Residue
- func (z *Residue) Add(x *Residue) *Residue
- func (z *Residue) Copy(x *Residue) *Residue
- func (z *Residue) Double() *Residue
- func (x *Residue) Equal(y *Residue) bool
- func (z *Residue) Exp(x [4]uint64) *Residue
- func (z *Residue) ExpPrecomp(x *ExpBase, y [4]uint64) *Residue
- func (z *Residue) FromUint64(m *Modulus, x [4]uint64) *Residue
- func (z *Residue) Inv() bool
- func (z *Residue) Mul(x *Residue) *Residue
- func (z *Residue) Neg() *Residue
- func (x *Residue) NotEqual(y *Residue) bool
- func (z *Residue) Square() *Residue
- func (z *Residue) Sub(x *Residue) *Residue
- func (z *Residue) ToUint64() [4]uint64
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ExpBase ¶
type ExpBase struct {
// contains filtered or unexported fields
}
The ExpBase type contains lookup tables allowing fast repeated modular exponentiation with the same base value.
func (*ExpBase) FromResidue ¶
FromResidue initialises ExpBase from a residue. It performs 224 squarings and 22 multiplications.
type Modulus ¶
type Modulus struct {
// contains filtered or unexported fields
}
Modulus contains a modulus `m` as well as derived values that help speed up computations. The allowed range for `m` is `2^192` to `2^256-1`.
func NewModulusFromUint64 ¶
NewModulusFromUint64 creates a new modulus object from a little-endian array of uint64.
type Residue ¶
type Residue struct {
// contains filtered or unexported fields
}
Residue contains a representative of a residue class, and the pointer to its modulus. The residue is stored as any 256-bit unsigned integer in the residue class, represented by a 4-element little-endian array of uint64.
func (*Residue) Copy ¶
Copy copies one residue to another. Both the residue value and the modulus pointer are copied.
func (*Residue) Exp ¶
Exp performs modular exponentiation without storing precomputed values for later use. It performs 255 squarings and 74 multiplications.
func (*Residue) ExpPrecomp ¶
ExpPrecomp takes an ExpBase computed from the base value, a 256-bit integer as the exponent, and performs modular exponentiation. It performs 31 squarings and 63 multiplications.
func (*Residue) FromUint64 ¶
FromUint64 sets the residue value from a little-endian array of uint64.
Source Files