fr

package
v0.13.0 Latest Latest
Warning

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

 Go to latest Published: Jul 18, 2024 License: Apache-2.0 Imports: 20 Imported by: 124

Documentation

Overview

Package fr contains field arithmetic operations for modulus = 0x4c23a0...300001.

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 [5]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] = 39705142709513438335025689890408969744933502416914749335064285505637884093126342347073617133569
q[base16] = 0x4c23a02b586d650d3f7498be97c5eafdec1d01aa27a1ae0421ee5da52bde5026fe802ff40300001

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

View Source 
const (
	Limbs = 5   // number of 64 bits words needed to represent a Element
	Bits  = 315 // number of bits needed to represent a Element
	Bytes = 40  // number of bytes needed to represent a Element
)

Variables

View Source 
var BigEndian bigEndian

BigEndian is the big-endian implementation of ByteOrder and AppendByteOrder.

View Source 
var LittleEndian littleEndian

LittleEndian is the little-endian implementation of ByteOrder and AppendByteOrder.

Functions

func Butterfly 

func Butterfly(a, b *Element)

Butterfly sets 

a = a + b (mod q)
b = a - b (mod q)

func Modulus 

func Modulus() *big.Int

Modulus returns q as a big.Int 

q[base10] = 39705142709513438335025689890408969744933502416914749335064285505637884093126342347073617133569
q[base16] = 0x4c23a02b586d650d3f7498be97c5eafdec1d01aa27a1ae0421ee5da52bde5026fe802ff40300001

func MulBy13 

func MulBy13(x *Element)

func MulBy3 

func MulBy3(x *Element)

func MulBy5 

func MulBy5(x *Element)

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 [5]uint64

Element represents a field element stored on 5 words (uint64)

Element are assumed to be in Montgomery form in all methods.

Modulus q = 

q[base10] = 39705142709513438335025689890408969744933502416914749335064285505637884093126342347073617133569
q[base16] = 0x4c23a02b586d650d3f7498be97c5eafdec1d01aa27a1ae0421ee5da52bde5026fe802ff40300001

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 

func BatchInvert(a []Element) []Element

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

func Generator added in v0.13.0 

func Generator(m uint64) (Element, error)

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 

func Hash(msg, dst []byte, count int) ([]Element, error)

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 

func NewElement(v uint64) Element

NewElement returns a new Element from a uint64 value

it is equivalent to 

var v Element
v.SetUint64(...)

func One 

func One() Element

One returns 1

func (*Element) Add 

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

Add z = x + y (mod q)

func (*Element) BigInt added in v0.9.0 

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

BigInt sets and return z as a *big.Int

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) Bits added in v0.9.0 

func (z *Element) Bits() [5]uint64

Bits provides access to z by returning its value as a little-endian [5]uint64 array. Bits is intended to support implementation of missing low-level Element functionality outside this package; it should be avoided otherwise.

func (*Element) Bytes 

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

Bytes returns the 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⁻¹ (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) Exp 

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

Exp z = xᵏ (mod q)

func (*Element) FitsOnOneWord added in v0.7.0 

func (z *Element) FitsOnOneWord() bool

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) Halve added in v0.5.2 

func (z *Element) Halve()

Halve sets z to z / 2 (mod q)

func (*Element) Inverse 

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

Inverse z = x⁻¹ (mod q)

if x == 0, sets and returns z = x

func (*Element) IsOne added in v0.7.0 

func (z *Element) IsOne() bool

IsOne returns z == 1

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 

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

Marshal returns the 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)

x and y must be less than q

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 and returns z

func (*Element) SetBigInt 

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

SetBigInt sets z to v and returns z

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, and returns z.

func (*Element) SetBytesCanonical added in v0.9.0 

func (z *Element) SetBytesCanonical(e []byte) error

SetBytesCanonical interprets e as the bytes of a big-endian 40-byte integer. If e is not a 40-byte slice or encodes a value higher than q, SetBytesCanonical returns an error.

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 (see SetString for valid formats)
*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 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 

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

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

x must be less than q

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 uint16 prefix "-" is added to the string.

func (Element) ToBigIntRegular deprecated 

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

ToBigIntRegular returns z as a big.Int in regular form

Deprecated: use BigInt(*big.Int) instead

func (*Element) Uint64 added in v0.7.0 

func (z *Element) Uint64() uint64

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 

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

Unmarshal is an alias for SetBytes, it sets z to the value of e.

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, ...)

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 

func (vector *Vector) AsyncReadFrom(r io.Reader) (int64, error, chan error)

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) Len added in v0.9.1 

func (vector Vector) Len() int

Len is the number of elements in the collection.

func (Vector) Less added in v0.9.1 

func (vector Vector) Less(i, j int) bool

Less reports whether the element with index i should sort before the element with index j.

func (*Vector) MarshalBinary added in v0.9.1 

func (vector *Vector) MarshalBinary() (data []byte, err error)

MarshalBinary implements encoding.BinaryMarshaler

func (*Vector) ReadFrom added in v0.9.1 

func (vector *Vector) ReadFrom(r io.Reader) (int64, error)

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) String added in v0.9.1 

func (vector Vector) String() string

String implements fmt.Stringer interface

func (Vector) Swap added in v0.9.1 

func (vector Vector) Swap(i, j int)

Swap swaps the elements with indexes i and j.

func (*Vector) UnmarshalBinary added in v0.9.1 

func (vector *Vector) UnmarshalBinary(data []byte) error

UnmarshalBinary implements encoding.BinaryUnmarshaler

func (*Vector) WriteTo added in v0.9.1 

func (vector *Vector) WriteTo(w io.Writer) (int64, error)

WriteTo implements io.WriterTo and writes a vector of big endian encoded Element. Length of the vector is encoded as a uint32 on the first 4 bytes.

Source Files

View all 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 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.