fr

package
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: 91

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)

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