fr

package
Version: v0.5.1 Latest Latest
Warning

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

Go to latest
Published: Sep 21, 2021 License: Apache-2.0 Imports: 10 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/@zkteam/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

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

0x4c23a02b586d650d3f7498be97c5eafdec1d01aa27a1ae0421ee5da52bde5026fe802ff40300001 // base 16
39705142709513438335025689890408969744933502416914749335064285505637884093126342347073617133569 // base 10

Index

Constants

View Source
const Bits = 315

Bits number bits needed to represent Element

View Source
const Bytes = Limbs * 8

Bytes number bytes needed to represent Element

View Source
const Limbs = 5

Limbs number of 64 bits words needed to represent Element

Variables

This section is empty.

Functions

func Butterfly

func Butterfly(a, b *Element)

func Modulus

func Modulus() *big.Int

Modulus returns q as a big.Int q =

39705142709513438335025689890408969744933502416914749335064285505637884093126342347073617133569

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 field modulus q =

39705142709513438335025689890408969744933502416914749335064285505637884093126342347073617133569

func BatchInvert

func BatchInvert(a []Element) []Element

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

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

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

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

Inverse z = x^-1 mod q Algorithm 16 in "Efficient Software-Implementation of Finite Fields with Applications to Cryptography" if x == 0, sets and returns z = x

func (*Element) IsUint64 added in v0.5.1

func (z *Element) IsUint64() bool

IsUint64 returns true if z[0] >= 0 and all other words are 0

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 regular (non montgomery) value of z as a big-endian byte slice.

func (*Element) Mul

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

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

func (*Element) Neg

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

Neg z = q - x

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) 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(s string) *Element

SetString creates a big.Int with s (in base 10) and calls SetBigInt on z

func (*Element) SetUint64

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

SetUint64 z = v, sets z LSB to v (non-Montgomery form) and convert z to Montgomery form

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/@zkteam/modular_multiplication

func (*Element) String

func (z *Element) String() string

String returns the string form of an Element in Montgomery form

func (*Element) Sub

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

Sub z = x - y mod q

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

func (Element) ToRegular

func (z Element) ToRegular() Element

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

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 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
t or T : Toggle theme light dark auto
y or Y : Canonical URL