fr

package
v0.6.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 15, 2022 License: Apache-2.0 Imports: 11 Imported by: 275

Documentation

Overview

Package fr contains field arithmetic operations for modulus = 0x30644e...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/@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 [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 

0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001 // base 16
21888242871839275222246405745257275088548364400416034343698204186575808495617 // base 10

Index

Constants

View Source 
const Bits = 254

Bits number bits needed to represent Element

View Source 
const Bytes = Limbs * 8

Bytes number bytes needed to represent Element

View Source 
const Limbs = 4

Limbs number of 64 bits words needed to represent Element

Variables

This section is empty.

Functions

func Butterfly added in v0.5.0 

func Butterfly(a, b *Element)

func Modulus 

func Modulus() *big.Int

Modulus returns q as a big.Int q =

21888242871839275222246405745257275088548364400416034343698204186575808495617

func MulBy13 added in v0.5.0 

func MulBy13(x *Element)

func MulBy3 

func MulBy3(x *Element)

func MulBy5 

func MulBy5(x *Element)

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 =

21888242871839275222246405745257275088548364400416034343698204186575808495617

func BatchInvert added in v0.5.0 

func BatchInvert(a []Element) []Element

BatchInvert returns a new slice with every element inverted. Uses Montgomery batch inversion trick

func NewElement added in v0.5.3 

func NewElement(v uint64) Element

NewElement returns a new Element from a uint64 value

it is equivalent to 

var v NewElement
v.SetUint64(...)

func One 

func One() Element

One returns 1 (in montgommery form)

func (*Element) Add 

func (z *Element) Add(x, y *Element) *Element

Add z = x + y mod q

func (*Element) Bit added in v0.5.1 

func (z *Element) Bit(i uint64) uint64

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 

func (z *Element) BitLen() int

BitLen returns the minimum number of bits needed to represent z returns 0 if z == 0

func (*Element) Bytes 

func (z *Element) Bytes() (res [Limbs * 8]byte)

Bytes returns the regular (non montgomery) value of z as a big-endian byte array.

func (*Element) Cmp 

func (z *Element) Cmp(x *Element) int

Cmp compares (lexicographic order) z and x and returns: 

-1 if z <  x
 0 if z == x
+1 if z >  x

func (*Element) Div 

func (z *Element) Div(x, y *Element) *Element

Div z = x*y^-1 mod q

func (*Element) Double 

func (z *Element) Double(x *Element) *Element

Double z = x + x mod q, aka Lsh 1

func (*Element) Equal 

func (z *Element) Equal(x *Element) bool

Equal returns z == x; constant-time

func (*Element) EvalPolynomial added in v0.6.1 

func (z *Element) EvalPolynomial(monic bool, coefficients []Element, x *Element)

func (*Element) Exp 

func (z *Element) Exp(x Element, exponent *big.Int) *Element

Exp z = x^exponent mod q

func (*Element) FromMont 

func (z *Element) FromMont() *Element

FromMont converts z in place (i.e. mutates) from Montgomery to regular representation sets and returns z = z * 1

func (*Element) Halve added in v0.5.2 

func (z *Element) Halve()

Halve sets z to z / 2 (mod p)

func (*Element) Inverse 

func (z *Element) Inverse(x *Element) *Element

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 

func (z *Element) IsUint64() bool

IsUint64 reports whether z can be represented as an uint64.

func (*Element) IsZero 

func (z *Element) IsZero() bool

IsZero returns z == 0

func (*Element) Legendre 

func (z *Element) Legendre() int

Legendre returns the Legendre symbol of z (either +1, -1, or 0.)

func (*Element) LexicographicallyLargest 

func (z *Element) LexicographicallyLargest() bool

LexicographicallyLargest returns true if this element is strictly lexicographically larger than its negation, false otherwise

func (*Element) Marshal added in v0.5.0 

func (z *Element) Marshal() []byte

Marshal returns the regular (non montgomery) value of z as a big-endian byte slice.

func (*Element) MarshalJSON added in v0.6.0 

func (z *Element) MarshalJSON() ([]byte, error)

MarshalJSON returns json encoding of z (z.Text(10)) If z == nil, returns null

func (*Element) Mul 

func (z *Element) Mul(x, y *Element) *Element

Mul z = x * y mod q see https://hackmd.io/@gnark/modular_multiplication

func (*Element) Neg 

func (z *Element) Neg(x *Element) *Element

Neg z = q - x

func (*Element) NotEqual added in v0.6.1 

func (z *Element) NotEqual(x *Element) uint64

NotEqual returns 0 if and only if z == x; constant-time

func (*Element) Select added in v0.6.1 

func (z *Element) Select(c int, x0 *Element, x1 *Element) *Element

Select is a constant-time conditional move. If c=0, z = x0. Else z = x1

func (*Element) Set 

func (z *Element) Set(x *Element) *Element

Set z = x

func (*Element) SetBigInt 

func (z *Element) SetBigInt(v *big.Int) *Element

SetBigInt sets z to v (regular form) and returns z in Montgomery form

func (*Element) SetBytes 

func (z *Element) SetBytes(e []byte) *Element

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) SetInt64 added in v0.6.0 

func (z *Element) SetInt64(v int64) *Element

SetInt64 sets z to v and returns z

func (*Element) SetInterface 

func (z *Element) SetInterface(i1 interface{}) (*Element, error)

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) SetOne 

func (z *Element) SetOne() *Element

SetOne z = 1 (in Montgomery form)

func (*Element) SetRandom 

func (z *Element) SetRandom() (*Element, error)

SetRandom sets z to a random element < q

func (*Element) SetString 

func (z *Element) SetString(number string) *Element

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) SetUint64 

func (z *Element) SetUint64(v uint64) *Element

SetUint64 sets z to v and returns z

func (*Element) SetZero 

func (z *Element) SetZero() *Element

SetZero z = 0

func (*Element) Sqrt 

func (z *Element) Sqrt(x *Element) *Element

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 

func (z *Element) Square(x *Element) *Element

Square z = x * x mod q see https://hackmd.io/@gnark/modular_multiplication

func (*Element) String 

func (z *Element) String() string

String returns the decimal representation of z as generated by z.Text(10).

func (*Element) Sub 

func (z *Element) Sub(x, y *Element) *Element

Sub z = x - y mod q

func (*Element) Text added in v0.6.0 

func (z *Element) Text(base int) string

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) ToBigInt 

func (z *Element) ToBigInt(res *big.Int) *big.Int

ToBigInt returns z as a big.Int in Montgomery form

func (Element) ToBigIntRegular 

func (z Element) ToBigIntRegular(res *big.Int) *big.Int

ToBigIntRegular returns z as a big.Int in regular form

func (*Element) ToMont 

func (z *Element) ToMont() *Element

ToMont converts z to Montgomery form sets and returns z = z * r²

func (Element) ToRegular 

func (z Element) ToRegular() Element

ToRegular returns z in regular form (doesn't mutate z)

func (*Element) UnmarshalJSON added in v0.6.0 

func (z *Element) UnmarshalJSON(data []byte) error

UnmarshalJSON accepts numbers and strings as input See Element.SetString for valid prefixes (0x, 0b, ...)

Source Files

View all 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 permutation provides an API to build permutation proofs.
 Package permutation provides an API to build permutation proofs.
Package plookup provides an API to build plookup proofs.
 Package plookup provides an API to build plookup proofs.
Package polynomial provides polynomial methods and commitment schemes.
 Package polynomial provides polynomial methods and commitment schemes.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.