fr

package
v0.0.0-...-69a8e72 Latest Latest
Warning

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

 Go to latest Published: Nov 11, 2022 License: Apache-2.0 Imports: 11 Imported by: 0

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 = Limbs * 8 // number of bytes needed to represent a Element
)

Variables

This section is empty.

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

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

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 

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

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

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 

func (z *Element) IsOne() bool

IsOne returns z == 1

func (*Element) IsUint64 

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 

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 strictly inferior to q

func (*Element) Neg 

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

Neg z = q - x

func (*Element) NotEqual 

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

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

func (*Element) Select 

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

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 strictly inferior to 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 

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

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

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 fri provides the FRI (multiplicative) commitment scheme.
 Package fri provides the FRI (multiplicative) commitment scheme.
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.