Documentation
¶
Overview ¶
Package felt contains field arithmetic operations for modulus = 0x800000...000001.
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 Felt [4]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
0x800000000000011000000000000000000000000000000000000000000000001 // base 16 3618502788666131213697322783095070105623107215331596699973092056135872020481 // base 10
Index ¶
- Constants
- func Butterfly(a, b *Felt)
- func Modulus() *big.Int
- func MulBy13(x *Felt)
- func MulBy3(x *Felt)
- func MulBy5(x *Felt)
- type Felt
- func (z *Felt) Add(x, y *Felt) *Felt
- func (z *Felt) Bit(i uint64) uint64
- func (z *Felt) BitLen() int
- func (z *Felt) ByteSlice() []byte
- func (z *Felt) Bytes() (res [Limbs * 8]byte)
- func (z *Felt) Cmp(x *Felt) int
- func (z *Felt) CmpCompat(x *Felt) int
- func (z *Felt) Deref() Felt
- func (z *Felt) Div(x, y *Felt) *Felt
- func (z *Felt) Double(x *Felt) *Felt
- func (z *Felt) Equal(x *Felt) bool
- func (z *Felt) Exp(x Felt, exponent *big.Int) *Felt
- func (z *Felt) FitsOnOneWord() bool
- func (z *Felt) FromMont() *Felt
- func (z *Felt) Halve()
- func (z *Felt) Hex() string
- func (z *Felt) Hex0x() string
- func (z *Felt) Inverse(x *Felt) *Felt
- func (z *Felt) IsOne() bool
- func (z *Felt) IsUint64() bool
- func (z *Felt) IsZero() bool
- func (z *Felt) Legendre() int
- func (z *Felt) LexicographicallyLargest() bool
- func (z *Felt) Marshal() []byte
- func (z *Felt) MarshalJSON() ([]byte, error)
- func (z *Felt) Mul(x, y *Felt) *Felt
- func (z *Felt) Neg(x *Felt) *Felt
- func (z *Felt) NotEqual(x *Felt) uint64
- func (z *Felt) Rsh(x *Felt, n uint) *Felt
- func (z *Felt) Select(c int, x0 *Felt, x1 *Felt) *Felt
- func (z *Felt) Set(x *Felt) *Felt
- func (z *Felt) SetBigInt(v *big.Int) *Felt
- func (z *Felt) SetBit(i uint64, j uint64) *Felt
- func (z *Felt) SetBytes(e []byte) *Felt
- func (z *Felt) SetHex(s string) *Felt
- func (z *Felt) SetInt64(v int64) *Felt
- func (z *Felt) SetInterface(i1 interface{}) (*Felt, error)
- func (z *Felt) SetOne() *Felt
- func (z *Felt) SetRandom() (*Felt, error)
- func (z *Felt) SetString(number string) *Felt
- func (z *Felt) SetUint64(v uint64) *Felt
- func (z *Felt) SetZero() *Felt
- func (z *Felt) Sqrt(x *Felt) *Felt
- func (z *Felt) Square(x *Felt) *Felt
- func (z *Felt) String() string
- func (z *Felt) Sub(x, y *Felt) *Felt
- func (z *Felt) Text(base int) string
- func (z *Felt) ToBigInt(res *big.Int) *big.Int
- func (z Felt) ToBigIntRegular(res *big.Int) *big.Int
- func (z *Felt) ToMont() *Felt
- func (z Felt) ToRegular() Felt
- func (z *Felt) ToggleBit(i uint64) *Felt
- func (z *Felt) Uint64() uint64
- func (z *Felt) UnmarshalJSON(data []byte) error
Constants ¶
const Bits = 252
Bits number bits needed to represent Felt
const Bytes = Limbs * 8
Bytes number bytes needed to represent Felt
const Limbs = 4
Limbs number of 64 bits words needed to represent Felt
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Felt ¶
type Felt [4]uint64
Felt represents a field element stored on 4 words (uint64) Felt are assumed to be in Montgomery form in all methods field modulus q =
3618502788666131213697322783095070105623107215331596699973092056135872020481
func BatchInvert ¶
BatchInvert returns a new slice with every element inverted. Uses Montgomery batch inversion trick
func NewFelt ¶
NewFelt returns a new Felt from a uint64 value
it is equivalent to
var v NewFelt v.SetUint64(...)
func (*Felt) Bit ¶
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 (*Felt) BitLen ¶
BitLen returns the minimum number of bits needed to represent z returns 0 if z == 0
func (*Felt) ByteSlice ¶
ByteSlice() is exactly the same as Marshal() except that it returns nil when z is nil. This mimics the behavior of big.Int.Bytes.
func (*Felt) Bytes ¶
Bytes returns the regular (non montgomery) value of z as a big-endian byte array.
func (*Felt) Cmp ¶
Cmp compares (lexicographic order) z and x and returns:
-1 if z < x 0 if z == x +1 if z > x
func (*Felt) CmpCompat ¶
CmpCompat is exactly the same as Cmp except that it returns zero if both z and x are nil.
func (*Felt) FitsOnOneWord ¶
FitsOnOneWord reports whether z words (except the least significant word) are 0
func (*Felt) FromMont ¶
FromMont converts z in place (i.e. mutates) from Montgomery to regular representation sets and returns z = z * 1
func (*Felt) Hex ¶
Hex returns a hex string without the 0x prefix. This function will automatically convert to regular form.
func (*Felt) Inverse ¶
Inverse z = x⁻¹ mod q Implements "Optimized Binary GCD for Modular Inversion" https://github.com/pornin/bingcd/blob/main/doc/bingcd.pdf
func (*Felt) LexicographicallyLargest ¶
LexicographicallyLargest returns true if this element is strictly lexicographically larger than its negation, false otherwise
func (*Felt) Marshal ¶
Marshal returns the regular (non montgomery) value of z as a big-endian byte slice.
func (*Felt) MarshalJSON ¶
MarshalJSON returns json encoding of z (z.Text(10)) If z == nil, returns null
func (*Felt) Mul ¶
Mul z = x * y mod q see https://hackmd.io/@gnark/modular_multiplication
func (*Felt) SetBit ¶
SetBit sets bit i to j on z. Undefined behavior if j is not zero or one. It is the responsibility of the caller to convert to/from regular form if necessary.
func (*Felt) SetBytes ¶
SetBytes interprets e as the bytes of a big-endian unsigned integer, sets z to that value (in Montgomery form), and returns z.
func (*Felt) SetHex ¶
SetHex sets z to the value represented by the hex string s mod q. It makes no difference if there is a leading 0x prefix on s. This function assumes s is in regular form and will convert to Montgomery form.
func (*Felt) SetInterface ¶
SetInterface converts provided interface into Felt returns an error if provided type is not supported supported types: Felt, *Felt, uint64, int, string (interpreted as base10 integer), *big.Int, big.Int, []byte
func (*Felt) SetString ¶
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.
func (*Felt) Sqrt ¶
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 (*Felt) Square ¶
Square z = x * x mod q see https://hackmd.io/@gnark/modular_multiplication
func (*Felt) Text ¶
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 uint64 prefix "-" is added to the string.
func (Felt) ToBigIntRegular ¶
ToBigIntRegular returns z as a big.Int in regular form
func (*Felt) ToggleBit ¶
ToggleBit flips bit i on z and returns z. Returns z if i is greater than the number of bits than Felt can represent. It is the responsibility of the caller to convert to/from regular form if necessary.
func (*Felt) Uint64 ¶
Uint64 returns the uint64 representation of x. If x cannot be represented in a uint64, the result is undefined.
func (*Felt) UnmarshalJSON ¶
UnmarshalJSON accepts numbers and strings as input See Felt.SetString for valid prefixes (0x, 0b, ...)
Source Files
Directories