Documentation
¶
Overview ¶
Package fp contains field arithmetic operations for modulus = 0x126633...70000d.
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/@gnark/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 [10]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
0x126633cc0f35f63fc1a174f01d72ab5a8fcd8c75d79d2c74e59769ad9bbda2f8152a6c0fadea490b8da9f5e83f57c497e0e8850edbda407d7b5ce7ab839c2253d369bd31147f73cd74916ea4570000d // base 16 20494478644167774678813387386538961497669590920908778075528754551012016751717791778743535050360001387419576570244406805463255765034468441182772056330021723098661967429339971741066259394985997 // 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) 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) EvalPolynomial(monic bool, coefficients []Element, x *Element)
- func (z *Element) Exp(x Element, exponent *big.Int) *Element
- func (z *Element) FromMont() *Element
- func (z *Element) Halve()
- 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) MarshalJSON() ([]byte, error)
- func (z *Element) Mul(x, y *Element) *Element
- func (z *Element) MulByNonResidue(x *Element) *Element
- func (z *Element) Neg(x *Element) *Element
- func (z *Element) NotEqual(x *Element) uint64
- func (z *Element) Select(c int, x0 *Element, x1 *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) SetInt64(v int64) *Element
- func (z *Element) SetInterface(i1 interface{}) (*Element, error)
- func (z *Element) SetOne() *Element
- func (z *Element) SetRandom() (*Element, error)
- func (z *Element) SetString(number 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) Text(base int) string
- 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
- func (z *Element) UnmarshalJSON(data []byte) error
Constants ¶
const Bits = 633
Bits number bits needed to represent Element
const Bytes = Limbs * 8
Bytes number bytes needed to represent Element
const Limbs = 10
Limbs number of 64 bits words needed to represent Element
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Element ¶
type Element [10]uint64
Element represents a field element stored on 10 words (uint64) Element are assumed to be in Montgomery form in all methods field modulus q =
20494478644167774678813387386538961497669590920908778075528754551012016751717791778743535050360001387419576570244406805463255765034468441182772056330021723098661967429339971741066259394985997
func BatchInvert ¶
BatchInvert returns a new slice with every element inverted. Uses Montgomery batch inversion trick
func NewElement ¶ added in v0.5.3
NewElement returns a new Element from a uint64 value
it is equivalent to
var v NewElement v.SetUint64(...)
func (*Element) Bit ¶ added in v0.5.1
Bit returns the i'th bit, with lsb == bit 0. It is the responsibility of the caller to convert from Montgomery to Regular form if needed
func (*Element) BitLen ¶ added in v0.5.1
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) Cmp ¶
Cmp compares (lexicographic order) z and x and returns:
-1 if z < x 0 if z == x +1 if z > x
func (*Element) EvalPolynomial ¶ added in v0.6.1
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⁻¹ mod q Implements "Optimized Binary GCD for Modular Inversion" https://github.com/pornin/bingcd/blob/main/doc/bingcd.pdf
func (*Element) IsUint64 ¶ added in v0.5.1
IsUint64 reports whether z can be represented as an uint64.
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) MarshalJSON ¶ added in v0.6.0
MarshalJSON returns json encoding of z (z.Text(10)) If z == nil, returns null
func (*Element) Mul ¶
Mul z = x * y mod q see https://hackmd.io/@gnark/modular_multiplication
func (*Element) MulByNonResidue ¶
MulByNonResidue multiplies a fp.Element by 2
func (*Element) Select ¶ added in v0.6.1
Select is a constant-time conditional move. If c=0, z = x0. Else z = x1
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 number and calls SetBigInt on z
The number prefix determines the actual base: A prefix of ”0b” or ”0B” selects base 2, ”0”, ”0o” or ”0O” selects base 8, and ”0x” or ”0X” selects base 16. Otherwise, the selected base is 10 and no prefix is accepted.
For base 16, lower and upper case letters are considered the same: The letters 'a' to 'f' and 'A' to 'F' represent digit values 10 to 15.
An underscore character ”_” may appear between a base prefix and an adjacent digit, and between successive digits; such underscores do not change the value of the number. Incorrect placement of underscores is reported as a panic if there are no other errors.
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/@gnark/modular_multiplication
func (*Element) Text ¶ added in v0.6.0
Text returns the string representation of z in the given base. Base must be between 2 and 36, inclusive. The result uses the lower-case letters 'a' to 'z' for digit values 10 to 35. No prefix (such as "0x") is added to the string. If z is a nil pointer it returns "<nil>". If base == 10 and -z fits in a uint64 prefix "-" is added to the string.
func (Element) ToBigIntRegular ¶
ToBigIntRegular returns z as a big.Int in regular form
func (*Element) UnmarshalJSON ¶ added in v0.6.0
UnmarshalJSON accepts numbers and strings as input See Element.SetString for valid prefixes (0x, 0b, ...)
Source Files