Documentation
¶
Overview ¶
Package fp contains field arithmetic operations for modulus = 0x122e82...00008b.
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 [12]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
0x122e824fb83ce0ad187c94004faff3eb926186a81d14688528275ef8087be41707ba638e584e91903cebaff25b423048689c8ed12f9fd9071dcd3dc73ebff2e98a116c25667a8f8160cf8aeeaf0a437e6913e6870000082f49d00000000008b // base 16 6891450384315732539396789682275657542479668912536150109513790160209623422243491736087683183289411687640864567753786613451161759120554247759349511699125301598951605099378508850372543631423596795951899700429969112842764913119068299 // 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) MulByNonResidue(x *Element) *Element
- func (z *Element) MulByNonResidueInv(x *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 = 761
Bits number bits needed to represent Element
const Bytes = Limbs * 8
Bytes number bytes needed to represent Element
const Limbs = 12
Limbs number of 64 bits words needed to represent Element
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Element ¶
type Element [12]uint64
Element represents a field element stored on 12 words (uint64) Element are assumed to be in Montgomery form in all methods field modulus q =
6891450384315732539396789682275657542479668912536150109513790160209623422243491736087683183289411687640864567753786613451161759120554247759349511699125301598951605099378508850372543631423596795951899700429969112842764913119068299
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) MulByNonResidue ¶
MulByNonResidue multiplies a fp.Element by -4
func (*Element) MulByNonResidueInv ¶
MulByNonResidueInv multiplies a fp.Element by (-4)**-1
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