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/@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
Usage ¶
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 q =
q[base10] = 52435875175126190479447740508185965837690552500527637822603658699938581184513 q[base16] = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
Warning ¶
This code has not been audited and is provided as-is. In particular, there is no security guarantees such as constant time implementation or side-channel attack resistance.
Index ¶
- Constants
- Variables
- func Butterfly(a, b *Element)
- func Modulus() *big.Int
- func MulBy13(x *Element)
- func MulBy3(x *Element)
- func MulBy5(x *Element)
- type ByteOrder
- type Element
- func (z *Element) Add(x, y *Element) *Element
- func (z *Element) BigInt(res *big.Int) *big.Int
- func (z *Element) BitLen() int
- func (z *Element) Bits() [4]uint64
- func (z *Element) Bytes() (res [Bytes]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, k *big.Int) *Element
- func (z *Element) FitsOnOneWord() bool
- func (z *Element) Halve()
- func (z *Element) Inverse(x *Element) *Element
- func (z *Element) IsOne() bool
- 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) 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) SetBytesCanonical(e []byte) error
- 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, error)
- 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) ToBigIntRegular(res *big.Int) *big.Intdeprecated
- func (z *Element) Uint64() uint64
- func (z *Element) Unmarshal(e []byte)
- func (z *Element) UnmarshalJSON(data []byte) error
- type Vector
- func (vector *Vector) AsyncReadFrom(r io.Reader) (int64, error, chan error)
- func (vector Vector) Len() int
- func (vector Vector) Less(i, j int) bool
- func (vector *Vector) MarshalBinary() (data []byte, err error)
- func (vector *Vector) ReadFrom(r io.Reader) (int64, error)
- func (vector Vector) String() string
- func (vector Vector) Swap(i, j int)
- func (vector *Vector) UnmarshalBinary(data []byte) error
- func (vector *Vector) WriteTo(w io.Writer) (int64, error)
Constants ¶
const ( Limbs = 4 // number of 64 bits words needed to represent a Element Bits = 255 // number of bits needed to represent a Element Bytes = 32 // number of bytes needed to represent a Element )
Variables ¶
var BigEndian bigEndian
BigEndian is the big-endian implementation of ByteOrder and AppendByteOrder.
var LittleEndian littleEndian
LittleEndian is the little-endian implementation of ByteOrder and AppendByteOrder.
Functions ¶
func Butterfly ¶ added in v0.5.0
func Butterfly(a, b *Element)
Butterfly sets
a = a + b (mod q) b = a - b (mod q)
Types ¶
type ByteOrder ¶ added in v0.9.0
type ByteOrder interface {
Element(*[Bytes]byte) (Element, error)
PutElement(*[Bytes]byte, Element)
String() string
}
A ByteOrder specifies how to convert byte slices into a Element
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.
Modulus q =
q[base10] = 52435875175126190479447740508185965837690552500527637822603658699938581184513 q[base16] = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
Warning ¶
This code has not been audited and is provided as-is. In particular, there is no security guarantees such as constant time implementation or side-channel attack resistance.
func BatchInvert ¶ added in v0.5.0
BatchInvert returns a new slice with every element inverted. Uses Montgomery batch inversion trick
func Generator ¶ added in v0.13.0
Generator returns a generator for Z/2^(log(m))Z or an error if m is too big (required root of unity doesn't exist)
func Hash ¶ added in v0.9.0
Hash msg to count prime field elements. https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#section-5.2
func NewElement ¶ added in v0.5.3
NewElement returns a new Element from a uint64 value
it is equivalent to
var v Element v.SetUint64(...)
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) Bits ¶ added in v0.9.0
Bits provides access to z by returning its value as a little-endian [4]uint64 array. Bits is intended to support implementation of missing low-level Element functionality outside this package; it should be avoided otherwise.
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) FitsOnOneWord ¶ added in v0.7.0
FitsOnOneWord reports whether z words (except the least significant word) are 0
It is the responsibility of the caller to convert from Montgomery to Regular form if needed.
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) MarshalJSON ¶ added in v0.6.0
MarshalJSON returns json encoding of z (z.Text(10)) If z == nil, returns null
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, and returns z.
func (*Element) SetBytesCanonical ¶ added in v0.9.0
SetBytesCanonical interprets e as the bytes of a big-endian 32-byte integer. If e is not a 32-byte slice or encodes a value higher than q, SetBytesCanonical returns an error.
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 (see SetString for valid formats) *big.Int big.Int []byte
func (*Element) SetRandom ¶
SetRandom sets z to a uniform random value in [0, q).
This might error only if reading from crypto/rand.Reader errors, in which case, value of z is undefined.
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.
If the number is invalid this method leaves z unchanged and returns nil, error.
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) 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 uint16 prefix "-" is added to the string.
func (*Element) Uint64 ¶ added in v0.7.0
Uint64 returns the uint64 representation of x. If x cannot be represented in a uint64, the result is undefined.
func (*Element) Unmarshal ¶ added in v0.11.2
Unmarshal is an alias for SetBytes, it sets z to the value of e.
func (*Element) UnmarshalJSON ¶ added in v0.6.0
UnmarshalJSON accepts numbers and strings as input See Element.SetString for valid prefixes (0x, 0b, ...)
type Vector ¶ added in v0.9.1
type Vector []Element
Vector represents a slice of Element.
It implements the following interfaces:
- Stringer
- io.WriterTo
- io.ReaderFrom
- encoding.BinaryMarshaler
- encoding.BinaryUnmarshaler
- sort.Interface
func (*Vector) AsyncReadFrom ¶ added in v0.11.2
AsyncReadFrom reads a vector of big endian encoded Element. Length of the vector must be encoded as a uint32 on the first 4 bytes. It consumes the needed bytes from the reader and returns the number of bytes read and an error if any. It also returns a channel that will be closed when the validation is done. The validation consist of checking that the elements are smaller than the modulus, and converting them to montgomery form.
func (Vector) Less ¶ added in v0.9.1
Less reports whether the element with index i should sort before the element with index j.
func (*Vector) MarshalBinary ¶ added in v0.9.1
MarshalBinary implements encoding.BinaryMarshaler
func (*Vector) ReadFrom ¶ added in v0.9.1
ReadFrom implements io.ReaderFrom and reads a vector of big endian encoded Element. Length of the vector must be encoded as a uint32 on the first 4 bytes.
func (*Vector) UnmarshalBinary ¶ added in v0.9.1
UnmarshalBinary implements encoding.BinaryUnmarshaler
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
Package fft provides in-place discrete Fourier transform on powers-of-two subgroups of 𝔽ᵣˣ (the multiplicative group (ℤ/rℤ, x) ).
|
Package fft provides in-place discrete Fourier transform on powers-of-two subgroups of 𝔽ᵣˣ (the multiplicative group (ℤ/rℤ, x) ). |
|
Package fri provides the FRI (multiplicative) commitment scheme.
|
Package fri provides the FRI (multiplicative) commitment scheme. |
|
Package htf provides hasher based on RFC 9380 Section 5.
|
Package htf provides hasher based on RFC 9380 Section 5. |
|
Package iop provides an API to computations common to iop backends (permutation, quotient).
|
Package iop provides an API to computations common to iop backends (permutation, quotient). |
|
Package mimc provides MiMC hash function using Miyaguchi–Preneel construction.
|
Package mimc provides MiMC hash function using Miyaguchi–Preneel construction. |
|
Package pedersen allows to compute and verify Pedersen vector commitments
|
Package pedersen allows to compute and verify Pedersen vector commitments |
|
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. |