tinyfield

package
v0.2.29 Latest Latest
Warning

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

Go to latest
Published: Feb 7, 2024 License: Apache-2.0 Imports: 18 Imported by: 0

Documentation

Overview

Package tinyfield contains field arithmetic operations for modulus = 0x2f.

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 [1]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] = 47
q[base16] = 0x2f

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 = 1 // number of 64 bits words needed to represent a Element
	Bits  = 6 // number of bits needed to represent a Element
	Bytes = 8 // 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] = 47
q[base16] = 0x2f

func MulBy13

func MulBy13(x *Element)

MulBy13 x *= 13 (mod q)

func MulBy3

func MulBy3(x *Element)

MulBy3 x *= 3 (mod q)

func MulBy5

func MulBy5(x *Element)

MulBy5 x *= 5 (mod q)

Types

type ByteOrder

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

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

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

Modulus q =

q[base10] = 47
q[base16] = 0x2f

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 Hash

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

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

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

BigInt sets and return z as a *big.Int

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

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

Bits provides access to z by returning its value as a little-endian [1]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

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

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 less than 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) SetBytesCanonical

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

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

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

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

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

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

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

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

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

type Vector

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

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

func (vector Vector) Len() int

Len is the number of elements in the collection.

func (Vector) Less

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

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

MarshalBinary implements encoding.BinaryMarshaler

func (*Vector) ReadFrom

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

func (vector Vector) String() string

String implements fmt.Stringer interface

func (Vector) Swap

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

Swap swaps the elements with indexes i and j.

func (*Vector) UnmarshalBinary

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

UnmarshalBinary implements encoding.BinaryUnmarshaler

func (*Vector) WriteTo

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL