fieldextension

Documentation

Overview

Package fieldextension provides operations over an extension field of the native field.

The operations inside the circuit are performed in the native field. In case of small fields, we need to perform some operations over an extension field to achieve the required soundness level. This package provides some primitives to perform such operations.

NB! This is an experimental package. The API is not stable and may change in backwards incompatible way. We also may change the extension construction for better performance.

Index

• type Element
• type Field
  • func NewExtension(api frontend.API, opts ...Option) (Field, error)
• type Option
  • func WithDegree(degree int) Option
  • func WithExtension(extension []*big.Int) Option

Types

type Element

type Element []frontend.Variable

Element is the extension field element.

type Field

type Field interface {
	// Reduce reduces the extension field element modulo the defining polynomial.
	Reduce(a Element) Element
	// Mul multiplies two extension field elements and reduces the result.
	Mul(a, b Element) Element
	// MulNoReduce multiplies two extension field elements without reducing the result.
	// The degree of the result is the sum of the degrees of the two operands.
	MulNoReduce(a, b Element) Element
	// Add adds two extension field elements. The result is not reduced. The
	// degree of the result is the max of the degrees of the two operands.
	Add(a, b Element) Element
	// Sub subtracts two extension field elements. The result is not reduced. The
	// degree of the result is the max of the degrees of the two operands.
	Sub(a, b Element) Element
	// MulByElement multiplies an extension field element by a native field
	// element. The result is not reduced. The degree of the result is the
	// degree of the extension field element.
	MulByElement(a Element, b frontend.Variable) Element
	// AssertIsEqual asserts that two extension field elements are strictly equal.
	// For equality in the extension field, reduce the elements first.
	AssertIsEqual(a, b Element)
	// Zero returns the zero element of the extension field. By convention it is
	// an empty polynomial.
	Zero() Element
	// One returns the one element of the extension field. By convention it is a
	// polynomial of degree 0.
	One() Element
	// AsExtensionVariable returns the native field element as an extension
	// field element of degree 0.
	AsExtensionVariable(a frontend.Variable) Element
	// Degree returns the degree of the extension field.
	Degree() int
}

Field is the extension field interface over native field. It provides the basic operations over the extension field.

func NewExtension

func NewExtension(api frontend.API, opts ...Option) (Field, error)

NewExtension returns a new extension field object.

NB! This is experimental API. It is not fully implemented and the interface and implementation may change.

type Option

type Option func(*config) error

Option allows to configure the extension field at initialization time.

func WithDegree

func WithDegree(degree int) Option

WithDegree forces the degree of the extension field. If not set then we choose the degree which provides soundness over the native field.

This option is a no-op when the extension is provided with the WithExtension option.

func WithExtension

func WithExtension(extension []*big.Int) Option

WithExtension sets the extension of the field. The input should be a slice of the polynomial coefficients defining the extension in LSB order. The coefficient of the highest degree must be 1.

Example, the extension x^3 + 2x^2 + 3x + 1 is represented as

[1, 3, 2, 1].

This option overrides the WithDegree option.