Documentation
¶
Overview ¶
Package fr contains field arithmetic operations for modulus = 0x73eda7...000001.
The API is similar to math/big (big.Int), but the operations are significantly faster (up to 20x for the modular multiplication on amd64, see also https://hackmd.io/@zkteam/modular_multiplication)
The modulus is hardcoded in all the operations.
Field elements are represented as an array, and assumed to be in Montgomery form in all methods:
type Element [4]uint64
Example API signature
// Mul z = x * y mod q func (z *Element) Mul(x, y *Element) *Element
and can be used like so:
var a, b Element
a.SetUint64(2)
b.SetString("984896738")
a.Mul(a, b)
a.Sub(a, a)
.Add(a, b)
.Inv(a)
b.Exp(b, new(big.Int).SetUint64(42))
Modulus
0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001 // base 16 52435875175126190479447740508185965837690552500527637822603658699938581184513 // base 10
Index ¶
- Constants
- func Butterfly(a, b *Element)
- func Modulus() *big.Int
- func MulBy13(x *Element)
- func MulBy3(x *Element)
- func MulBy5(x *Element)
- type Element
- func (z *Element) Add(x, y *Element) *Element
- func (z *Element) Bytes() (res [Limbs * 8]byte)
- func (z *Element) Cmp(x *Element) int
- func (z *Element) Div(x, y *Element) *Element
- func (z *Element) Double(x *Element) *Element
- func (z *Element) Equal(x *Element) bool
- func (z *Element) Exp(x Element, exponent *big.Int) *Element
- func (z *Element) FromMont() *Element
- func (z *Element) Inverse(x *Element) *Element
- func (z *Element) IsZero() bool
- func (z *Element) Legendre() int
- func (z *Element) LexicographicallyLargest() bool
- func (z *Element) Marshal() []byte
- func (z *Element) Mul(x, y *Element) *Element
- func (z *Element) Neg(x *Element) *Element
- func (z *Element) Set(x *Element) *Element
- func (z *Element) SetBigInt(v *big.Int) *Element
- func (z *Element) SetBytes(e []byte) *Element
- func (z *Element) SetInterface(i1 interface{}) (*Element, error)
- func (z *Element) SetOne() *Element
- func (z *Element) SetRandom() (*Element, error)
- func (z *Element) SetString(s string) *Element
- func (z *Element) SetUint64(v uint64) *Element
- func (z *Element) SetZero() *Element
- func (z *Element) Sqrt(x *Element) *Element
- func (z *Element) Square(x *Element) *Element
- func (z *Element) String() string
- func (z *Element) Sub(x, y *Element) *Element
- func (z *Element) ToBigInt(res *big.Int) *big.Int
- func (z Element) ToBigIntRegular(res *big.Int) *big.Int
- func (z *Element) ToMont() *Element
- func (z Element) ToRegular() Element
Constants ¶
const Bits = 255
Bits number bits needed to represent Element
const Bytes = Limbs * 8
Bytes number bytes needed to represent Element
const Limbs = 4
Limbs number of 64 bits words needed to represent Element
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Element ¶
type Element [4]uint64
Element represents a field element stored on 4 words (uint64) Element are assumed to be in Montgomery form in all methods field modulus q =
52435875175126190479447740508185965837690552500527637822603658699938581184513
func BatchInvert ¶ added in v0.5.0
BatchInvert returns a new slice with every element inverted. Uses Montgomery batch inversion trick
func (*Element) Bytes ¶
Bytes returns the regular (non montgomery) value of z as a big-endian byte array.
func (*Element) Cmp ¶
Cmp compares (lexicographic order) z and x and returns:
-1 if z < x 0 if z == x +1 if z > x
func (*Element) FromMont ¶
FromMont converts z in place (i.e. mutates) from Montgomery to regular representation sets and returns z = z * 1
func (*Element) Inverse ¶
Inverse z = x^-1 mod q Algorithm 16 in "Efficient Software-Implementation of Finite Fields with Applications to Cryptography" if x == 0, sets and returns z = x
func (*Element) LexicographicallyLargest ¶
LexicographicallyLargest returns true if this element is strictly lexicographically larger than its negation, false otherwise
func (*Element) Marshal ¶ added in v0.5.0
Marshal returns the regular (non montgomery) value of z as a big-endian byte slice.
func (*Element) Mul ¶
Mul z = x * y mod q see https://hackmd.io/@zkteam/modular_multiplication
func (*Element) SetBytes ¶
SetBytes interprets e as the bytes of a big-endian unsigned integer, sets z to that value (in Montgomery form), and returns z.
func (*Element) SetInterface ¶
SetInterface converts provided interface into Element returns an error if provided type is not supported supported types: Element, *Element, uint64, int, string (interpreted as base10 integer), *big.Int, big.Int, []byte
func (*Element) SetString ¶
SetString creates a big.Int with s (in base 10) and calls SetBigInt on z
func (*Element) SetUint64 ¶
SetUint64 z = v, sets z LSB to v (non-Montgomery form) and convert z to Montgomery form
func (*Element) Sqrt ¶
Sqrt z = √x mod q if the square root doesn't exist (x is not a square mod q) Sqrt leaves z unchanged and returns nil
func (*Element) Square ¶
Square z = x * x mod q see https://hackmd.io/@zkteam/modular_multiplication
func (Element) ToBigIntRegular ¶
ToBigIntRegular returns z as a big.Int in regular form
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
Package fft provides in-place discrete Fourier transform.
|
Package fft provides in-place discrete Fourier transform. |
|
Package kzg provides a KZG commitment scheme.
|
Package kzg provides a KZG commitment scheme. |
|
Package mimc provides MiMC hash function using Miyaguchi–Preneel construction.
|
Package mimc provides MiMC hash function using Miyaguchi–Preneel construction. |
|
Package polynomial provides polynomial methods and commitment schemes.
|
Package polynomial provides polynomial methods and commitment schemes. |