Documentation
¶
Overview ¶
Package fr contains field arithmetic operations for modulus = 0x1cfb69...76e7e1.
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
0x1cfb69d4ca675f520cce760202687600ff8f87007419047174fd06b52876e7e1 // base 16 13108968793781547619861935127046491459309155893440570251786403306729687672801 // 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) Bit(i uint64) uint64
- func (z *Element) BitLen() int
- func (z *Element) Bytes() (res [Limbs * 8]byte)
- func (z *Element) BytesLE() (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) IsUint64() bool
- 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) SetBytesLE(e []byte) *Element
- func (z *Element) SetBytesLECanonical(e []byte) (*Element, error)
- 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 = 253
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 =
13108968793781547619861935127046491459309155893440570251786403306729687672801
func BatchInvert ¶
BatchInvert returns a new slice with every element inverted. Uses Montgomery batch inversion trick
func Zero ¶
func Zero() Element
Zero returns 0 (in montgommery form) This is not strictly needed, as the default value for u64s is zero
func (*Element) Bit ¶
Bit returns the i'th bit, with lsb == bit 0. It is the responsability of the caller to convert from Montgomery to Regular form if needed
func (*Element) BitLen ¶
BitLen returns the minimum number of bits needed to represent z returns 0 if z == 0
func (*Element) Bytes ¶
Bytes returns the regular (non montgomery) value of z as a big-endian byte array.
func (*Element) BytesLE ¶
Bytes returns the regular (non montgomery) value of z as a little-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 ¶
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) SetBytesLE ¶
SetBytes interprets e as the bytes of a little-endian unsigned integer, sets z to that value (in Montgomery form), and returns z.
func (*Element) SetBytesLECanonical ¶
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